Математическая теория игр

Все игры можно  разделить на два типа: коалиционные и бескоалиционные. Коалицией называют любое подмножество множества I. Игра, в которой действия игроков некоторой коалиции направлены на максимизацию выигрыша всей коалиции без последующего его разделения между игроками коалиции и называются коалиционными. В бескоалиционной игре целью каждого участника является получение по возможности большего индивидуального выигрыша.

Среди всех бескоалиционных  игр с нулевой суммой естественным образом выделяется класс антагонистических игр, в которых число игроков равно двум, а значения их функций выигрыша в каждой ситуации равны по величине и противоположны по знаку (1.2)

 

.     (1.2)

 

Пусть каждой стратегии первого игрока взаимооднозначно поставлена в соответствие строка некоторой матрицы А, а каждой стратегии второго игрока взаимооднозначно поставлен в соответствие столбец этой матрицы. Матрицу А называют платежной (или матрицей игры), если её элемент a_ij равен выигрышу первого игрока (т.е. проигрышу второго) при выборе первым игроком i-й стратегии, а вторым –j-й.

Поэтому антагонистическая игра полностью описывается единственной матрицей и в соответствии с этим называется матричной.

Теория игр занимается исследованием математических моделей  принятия оптимальных решений в  конфликтных ситуациях. Формальное описание принятия решений удобно разбить на две части:

1) математическая модель конфликтной ситуации или игра – описание конфликтной ситуации, включающее в себя описание субъектов, принимающих решения, их возможностей и интересов;

2) принцип оптимальности – описание правил рационального поведения игроков.

Оптимальность и неоптимальность  того или иного исхода конфликта  зависит от интересов и возможностей его участников. В этом смысле принцип  оптимальности является функцией игры.

Математическая модель конфликта  и принцип оптимальности дают полное описание принятия решений в условиях конфликта.

В описании игры можно выделить следующие  элементы:

1. Коалиции действий – совокупность действующих совместно в данной конфликтной ситуации субъектов.
2. Коалиции интересов – множество одинаково заинтересованных в исходе конфликта сторон.
3. Множества возможных выборов каждой из коалиций действия.
4. Описание предпочтений каждой из коалиций интересов.
5. Множество возможных исходов конфликта.

Появление слова «коалиция» указывает на тот факт, что участниками конфликта могут быть не только отдельные лица, но и большие, сложно организованные группы лиц. Коалиции действия и интересов могут не совпадать. Например, пассажиры самолета бывают заинтересованы в его скорейшем прибытии к месту назначения и, таким образом, образуют коалицию интересов, однако они не могут предпринять никаких действий, направленных на достижение этой цели, т.е. не являются коалицией действия. Если коалиция действия совпадает с коалицией интересов, то такую монолитную коалицию можно считать одним лицом, поэтому ее называют игроком. Если все коалиции действия совпадают с соответствующими коалициями интересов, то игру называют бескоалиционной, а ее участников – игроками.

Множество возможных  исходов конфликта определяет совместные ограничения на действия участников конфликта. Если такие ограничения задаются формально (в виде прямого произведения множеств), то соответствующую называют игрой без запрещенных ситуаций, если эти ограничения существенны, то — игрой с запрещенными ситуациями.

Заинтересованность j-го субъекта формализуется, как правило, функцией выигрыша, которая определяется отображением , где U - множество исходов. Выбор стратегии или управления определяется принципом оптимальности.

Таким образом, для описания конфликтной ситуации необходимо задать систему (1.3)

 

,    (1.3)

где N -множество игроков,

K_g - множество коалиций действия,

K_и - множество коалиций интересов,

U_i - множество выборов коалиции ,

g_j - функция выигрыша коалиции ,

S - множество возможных исходов игры.

 

В рамках теории игр существуют два основных направления. Теория некооперативных игр изучает принятие решений в предположении, что существует механизм, обеспечивающий выполнение совместно принятого решения. При этом основная проблема — указать множество взаимовыгодных решений с учетом интересов и самостоятельных возможностей отдельных игроков и коалиций, то есть групп совместно действующих игроков. Если это множество включает несколько вариантов решения, то возникает также задача выработки критерия оптимальности, который позволил бы найти единственное, наилучшее в некотором смысле решение.

Некооперативные игры отражают ситуации, в которых игроки действуют самостоятельно, независимо друг от друга, и если какие-то соглашения заключаются, то они не являются обязывающими: каждый игрок может отклониться от договоренности. Таким играм уделяется основное внимание в данном пособии.

Если игроков двое, а интересы их противоположны, то игра называется антагонистической. Типичными примерами антагонистических игр являются шахматы, шашки. При проведении военных операций нападающая сторона обычно стремится нанести противнику максимальный ущерб, а противник стремится этот ущерб минимизировать. Поэтому в таких случаях военную операцию можно изучать как антагонистическую игру.

Неантагонистическим игры. Экономика и социальная сфера дают многочисленные примеры таких игр. Пусть несколько фирм конкурируют на товарном рынке и заинтересованы в увеличении своих доходов. Цена на продукцию определяется спросом на товар и количеством выпущенной продукции. Теория игр предписывает фирмам-игрокам назначать выпуск продукции в таких количествах, при которых каждому отдельно взятому игроку было бы невыгодно отклоняться от предписанного объема. Соответствующий набор стратегий называют равновесием по Нэшу. Другим примером являются иерархические игры, отражающие взаимодействие между верхним и нижним звеньями управления (начальником и подчиненным, заказчиком и производителем продукции и т.п.). Здесь обычно интересуются не равновесием в игре, а наилучшим гарантированным результатом, который может себе обеспечить игрок-лидер, первым сообщающий свою стратегию другому игроку.

1.2 Понятие  и принципы оптимальности в  математической теории игр

 

Теория игр как математическая дисциплина в ее современном состоянии  занимается нормативным изучением  игр, т.е. считает своей задачей  установить какое поведение игроков следует считать оптимальным (разумным, целесообразным).

Оптимальность стратегии очевидно можно понимать по-разному. То есть понятия оптимальности в теории игр и оптимального решения игры не являются однозначными, априорными, абсолютными. Вместе с тем эти понятия являются объективными, т.е. каждый вариант оптимальности поддается точному описанию при помощи недвусмысленных математических формулировок. Тем самым различные содержательные представления об оптимальности могут приводить к отличающимся математическим моделям.

Основными содержательными  чертами оптимальности в применении к исходу или к множеству исходов конфликта можно считать интуитивные представления о выгодности и справедливости [21, c. 42].

Важнейшей характеристикой  выбранного решения является целесообразность, или в более строгой формулировке, оптимальность этого решения. Под принципом оптимальности φ понимается отображение              φ , которое ставит в соответствие игре Г (или некоторому классу игр) подмножество множества ее исходов. При этом  φ(Г) обозначает решение задачи или реализацию принципа оптимальности. При анализе игры существуют две взаимосвязанные проблемы:

1. Сделать оптимальный выбор.
2. Оценить результат при сделанном выборе.

Для конфликта, в котором участвуют не менее  двух игроков, понятие оптимального решения не может быть определено однозначно, т.е. в общем случае игр n лиц отсутствует единое и объективное понятие оптимальности. Таким образом, целесообразно анализировать конкретные, более частные виды конфликта, где такое понятие оптимальности формализуется полностью, либо удается максимально расширить возможности формализации этого понятия.

Рассмотрим примеры  полной формализации принципа оптимальности. Для игры в случае полной независимости  игроков функции выигрышей имеют вид . При этом множество исходов равняется прямому произведению   множеств   выборов .    Тогда   для   любого   игрока оптимальным   выбором   естественно   считать   только   выбор   из   множества элементов (1.4)

 

,      (1.4)

 

реализующих максимум функций  . Данная игра эквивалентна задаче оптимизации.

Так же единственным образом определяется оптимальность  в играх многих лиц, для которых для всех i, т.е. в играх с совпадающими интересами игроков. При разумном поведении игроков (обмене информации, координации усилий по выбору соответствующих стратегий) задача также сводится к задаче оптимизации.

Термин «оптимальный выбор» однозначно понимается при исследовании антагонистической игры , в которой существует седловая точка, т.е. выполняется равенство (1.5)

 

.   (1.5)

В общем случае игры многих лиц однозначность отсутствует, что не только усложняет решение  игры, но и привносит принципиальную трудность в определение оптимального, или рационального выбора.

Отсутствие однозначного соответствия между выбранными стратегиями  и оцениваемым выигрышем иллюстрирует следующий пример. Пусть функция  выигрыша имеет вид (1.6)

 

.    (1.6)

 

Пусть игроки стремятся максимизировать свои функции выигрыша и не имеют информации о действиях партнеров. Тогда выбор оптимальной стратегии не представляет труда и в некотором смысле однозначен. Но оценка получаемого выигрыша не однозначна. Действительно, выигрыш игрока будет зависеть от выбора всех оставшихся.

Таким образом, принцип  оптимальности является наиболее сложным  и важным при принятии решений. Выбор  того или иного принципа оптимальности  неоднозначен. Причины этой неоднозначности  заключаются в природе конфликтной ситуации. В связи с этим принцип оптимальности должен отвечать следующим условиям:

1. Должен быть таким, чтобы существовал оптимальный выбор, т.е. отображение φ не приводило к пустому множеству рациональных выборов.
2. Должен максимально сужать степень неопределенности, как во множестве выборов, так и в оценке ожидаемого результата.
3. Должен быть прост и понятен, чтобы можно было практически вычислить множество рациональных решений и оценить с большой степенью точности ожидаемый выигрыш; полученные результаты должны хорошо интерпретироваться на содержательном уровне.
4. Должен обладать устойчивостью, т.е. решение игры должно мало меняться при небольшом изменении параметров модели конфликтной ситуации.

При выборе принципа оптимальности  проявляются тенденции изоляционизма и коллективизма. Изоляционизм заключается в стремлении каждого игрока к тому, чтобы выбор его оптимального решения в минимальной степени зависел от других игроков. Как правило, это достигается введением нового вспомогательного критерия эффективности игрока i, в минимальной степени зависящей от . В идеале вспомогательный критерий имеет вид .

Коллективизм основан на координации  усилий с целью получения большего выигрыша каждым игроком. Координация  усилий может заключаться, например, в выборе общей цели — общего критерия эффективности для коалиции игроков.

В случае антагонистической  игры или игры с природой игрок  вместо функции максимизирует  . Такой принцип оптимальности принято называть принципом максимина. Принципу максимина, или принципу максимального гарантированного результата, можно придать более широкий содержательный смысл. Так называемый обобщенный принцип максимального гарантированного результата в полной мере учитывает имеющуюся информацию, а также информацию, которая может поступить в процессе принятия решений. В этих условиях независимо от функции выигрыша партнера игрок 1 гарантированно может получить (1.7)

 

.      (1.7)

 

Основными свойствами рациональности коллективных принципов оптимальности  являются:

1. Выгодность (индивидуальная выгодность). По крайней мере, необходимо, чтобы каждому игроку в коалиции был дан выигрыш не меньший, чем , который он может гарантировать себе сам.
2. Устойчивость. Устойчивость понимается в том смысле, что никому из игроков не выгодно уклоняться от принятых на себя обязательств.
3. Справедливость. Справедливость понимается как некоторая симметричность в положении игроков, т.е. в некотором смысле их равноправие.