Кооперативные игры

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

Игра называется кооперативной, или коалиционной, если игроки объединяются в группы, беря на себя некоторые обязательства перед другими игроками и координируя свои действия. Этим она отличается от некооперативных игр, в которых каждый играет сам за себя. Развлекательные игры обычно не являются кооперативными, однако есть исключения и такие механизмы нередки в повседневной жизни.

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

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

Гибридные игры включают в себя элементы некооперативных и кооперативных игр. Например, игроки могут создавать группы, но ход игры будет вестись в некооперативном стиле. Это означает, что каждый игрок будет стараться достичь личной выгоды и одновременно преследовать интересы своей группы.

Кооперативные игры получаются в тех случаях, когда, в игре из n игроков разрешается образовывать определённые коалиции. Множество всех игроков обозначим через N, N ={1, 2,..., n }, а через K - любое его подмножество. Пусть игроки из подмножества K договариваются между собой о совместных действиях и, таким образом, образуют одну коалицию. Отсюда видно, что число таких коалиций, состоящих из r игроков, равно числу сочетаний из n по r, то есть , а число всевозможных коалиций равно

= 2 n - 1.

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

Функция u, которая каждой коалиции K ставит в соответствие наибольший, уверенно получаемый его выигрыш u (K), называется характеристической функцией игры. Так, например, для бескоалиционной игры n игроков u (K) может получиться, когда игроки из множества K оптимально действуют как один игрок против остальных N\K игроков, образующих другую коалицию (второй игрок).

Характеристическая функция u называется простой, если она принимает только два значения: 0 и 1. Если характеристическая функция u простая, то коалиции K, для которых u (K) =1, называются выигрывающими, а коалиции K, для которых u (K) = 0, -соответственно проигрывающими.

Если в простой характеристической функции u выигрывающими являются такие коалиции, содержащие фиксированную непустую коалицию R, то характеристическая функция u, обозначаемая в таком случае через u _R, называется простейшей.

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

Более сложным является пример оценки результатов голосования в Совете безопасности ООН, где выигрывающими коалициями являются все коалиции, состоящие из всех пяти постоянных членов Совета плюс ещё хотя бы один непостоянный член, и только они.

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

Обозначим через u _G характеристическую функцию бескоалиционной игры. Эта функция имеет следующие свойства:

1) Персональность

u _G (Æ) = 0, т.е. коалиция, не имеющая ни одного игрока, ничего не выигрывает;

2) Супераддитивность

u _G (K È L) ³ u _G (K) + u _G (L), если K, L Ì N, K Ç L ¹ Æ,

т.е. общий выигрыш коалиции больше или равен суммарному выигрышу всех участников коалиции;

3) Дополнительность

u _G (K) + u (N \ K) = u (N)

т.е. для бескоалиционной игры с постоянной суммой сумма выигрышей для коалиции и для остальных игроков равняется общей сумме выигрышей всех игроков.

Распределение выигрышей (делёж) игроков должно удовлетворять следующим двум естественным условиям: если выигрыш i- го игрока обозначить через x_i, то, во-первых, должно удовлетворяться условие индивидуальной рациональности

x_i ³ u (i), для i ÎN

т.е. любой игрок должен получить выигрыш в коалиции не меньше того, какой он получил бы не участвуя в ней (иначе он не будет участвовать в коалиции); во-вторых, должно удовлетворяться условие коллективной рациональности

= u (N)

т.е. сумма выигрышей игроков должна соответствовать возможностям (если сумма выигрышей всех игроков меньше, чем u (N), то игрокам не нужно вступать в коалицию; если же допустить, чтобы сумма выигрышей была больше, чем u (N), то это значит, что игроки должны делить между собой сумму большую, чем у них есть).

Таким образом, вектор x = (x₁,..., x_n), удовлетворяющий условиям коллективной и индивидуальной рациональности, называется дележом в условиях характеристической функции u.

Система { N, u}, которая состоит из множества игроков, характеристической функции над данным множеством и множеством дележей, удовлетворяющих соотношениям (2) и (3) в условиях характеристической функции, называется классической кооперативной игрой.

Исходя из этих определений, появляется следующая теорема.

Теорема. Чтобы вектор x = (x₁,..., x_n) был дележом в классической кооперативной игре {N, u},

необходимо и достаточно, чтобы

x_i = u(i) + a_i, (iÎN)

причём

a_i ³ 0 (iÎN)
= u(N) –
В бескоалиционных играх исход формируется в результате действий тех игроков, которые в этой ситуации получают свои выигрыши. Исходом в кооперативной игре является делёж, который возникает как результат соглашений игроков, а не как следствие их действий. Поэтому в кооперативных играх сравниваются не ситуации, как это происходит в бескоалиционных играх, а дележи, и такое сравнение носит более сложный характер.

Кооперативные игры считаются существенными, если для любых коалиций K и L выполняется неравенство

u(K) + u(L) < u(KÈL),

т.е. в условии супераддитивности выполняется строгое неравенство. Если же в условии супераддитивности выполняется равенство

u(K) + u(L) = u(KÈL),

т.е. выполняется свойство аддитивности, то такие игры называются несущественными.

Справедливы следующие свойства:

1) для того чтобы характеристическая функция была аддитивной (кооперативная игра – несущественной), необходимо и достаточно выполнение следующего равенства:

= u(N)

2) в несущественной игре имеется только один делёж

{u(1), u(2),..., u(n) };

3) в существенной игре с более чем одним игроком множество дележей бесконечно

(u(1) + a₁, u(2) + a₂,..., u(n) +a_n )

где

a_i ³ 0 (i Î N), u(N) — > 0

Кооперативная игра с множеством игроков N и характеристической функцией u называется стратегически эквивалентной игрой с таким же множеством игроков и характеристической функцией u¹, если найдутся такие к > 0 и произвольные вещественные C_i (iÎN), что для любой коалиции К Ì N имеет место равенство:

u ¹ (K) = k u (K) +

Смысл определения стратегической эквивалентности кооперативных игр (с. э. к. и.) состоит в том, что характеристические функции с. э. к. и. отличаются только масштабом измерения выигрышей k и начальным капиталом C_i. Стратегическая эквивалентность кооперативных игр с характеристическими функциями u и u¹ обозначается так u~u¹. Также вместо стратегической эквивалентности кооперативных игр говорят о стратегической эквивалентности их характеристических функций.

Справедливы следующие свойства для стратегических эквивалентных игр:

1) Рефлексивность, т.е. каждая характеристическая функция эквивалентна себе u~u.

2) Симметрия, т.е. если u~u¹, то u¹~u.

3) Транзитивность, т.е. если u~u¹ и u¹~u², то u~u².

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

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

пусть u~u¹, т.е. выполняется (5), и x = (x₁,..., x_n) – дележи в условиях характеристической функции u; рассмотрим вектор x¹ = (,..., ), где = k x_i+C_i ; для него выполняется

= k x_i + C_i ³ k u(i) + С_i = u¹(i);

т.е. выполняется условие индивидуальной рациональности, и

= = k + = k u(N) + = u¹(N)

т.е. выполняется условие коллективной рациональности. Поэтому вектор является дележом в условиях u¹. Говорят, что делёж x¹ соответствует дележу x при стратегической эквивалентности u~u¹.

Если все значения характеристической функции кооперативной игры равны нулю, то она называется нулевой. Содержательное значение нулевой игры состоит в том, что в ней игроки не имеют никакой заинтересованности.

Всякая несущественная игра стратегически эквивалентна нулевой.

Одними из наиболее интересных способов решения коалиционных игр являются решения с применением аксиом Шелли.

Дата добавления: 2015-10-24