Кооперативные игры 2 (стр. 2 из 3)

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

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

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

, а число всевозможных коалиций равно

= 2ⁿ - 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 характеристическую функцию бескоалиционной игры. Эта функция обладает следующими свойствами:

персональность

u_G (Æ) = 0,т.е. коалиция, не содержащая ни одного игрока, ничего не выигрывает;

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

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

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

дополнительность

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

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

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

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

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

= u (N)

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

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

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

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

u¹ (K) = ku (K) +

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

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

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

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

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

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

Решение кооперативной игры при помощи вектора шепли

Аксиомы Шепли:

1. Аксиома эффективности. Если S - любой носитель игры с характеристической функцией u, то

= u (S)

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

2. Аксиома симметрии. Для любой перестановки p и iÎN должно выполняться

(pu) = j_{i (}u), т.е. игроки, одинаково входящие в игру, должны “по справедливости” получать одинаковые выигрыши.

3. Аксиома агрегации. Если есть две игры с характеристическими функциями u¢ и u¢¢, то

j_{i (}u¢ + u¢¢) = j_{i (}u¢) + j_{i (}u¢¢),

т.е. ради “справедливости" необходимо считать, что при участии игроков в двух играх их выигрыши в отдельных играх должны складываться.

Определение. Вектором цен (вектором Шепли) игры с характеристической функцией u называется n-мерный вектор

j ₍u) = (j₁ (u), j₂ (u),..., j_n (u)),

удовлетворяющий аксиомам Шепли.

Существование вектора Шепли вытекает из следующей теоремы

Теорема. Существует единственная функция j, определённая для всех игр и удовлетворяющая аксиомам Шепли.

Определение. Характеристическая функция w_S (T), определённая для любой коалиции S, называется простейшей, если

w_S (T) =

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

Вектор Шепли содержательно можно интерпретировать следующим образом: предельная величина, которую вносит i-й игрок в коалицию T, выражается как u (T) -u (T \{i}) и считается выигрышем i-го игрока; g_{i (}T) - это вероятность того, что i-й игрок вступит в коалицию T \{i}; j_{i (}u) - средний выигрыш i-го игрока в такой схеме интерпретации. В том случае, когда u - простейшая,