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

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

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

     Обозначим через 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) = 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².

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

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

 

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

     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 - простейшая, 

       

     Следовательно 

      , 

     где суммирование по T распространяется на все такие выигрывающие коалиции T, что коалиция T \{i}не является выигрывающей.

     Пример. Рассматривается корпорация из четырёх  акционеров, имеющих акции соответственно в следующих размерах 

     a₁ = 10, a₂ = 20, a₃ = 30, a₄ = 40. 

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

     {2; 4}, {3; 4},

     {1; 2; 3}, {1; 2; 4}, {2; 3; 4}, {1; 3; 4},

     {1; 2; 3; 4}. 

     Найдём  вектор Шепли для этой игры.

     При нахождении j₁ необходимо учитывать, что имеется только одна коалиция T = {1; 2; 3}, которая выигрывает, а коалиция T \{1} = {2; 3} не выигрывает. В коалиции T имеется t = 3 игрока, поэтому 

      . 

     Далее, определяем все выигрывающие коалиции, но не выигрывающие без 2-го игрока: {2; 4}, {1; 2; 3}, {2; 3; 4}. Поэтому 

      . 

     Аналогично  получаем, что  , .

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

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

 

Заключение

 

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

     Есть в современной математике одна область, она носит безобидное название теории игр, но ей, несомненно, суждено сыграть очень важную роль в человековедении самого ближайшего будущего, - говорил Джон фон Нейман, один из основоположников кибернетики. - Она занимается вопросами оптимального поведения людей при наличии противодействующего противника. Для ученого противник - это природа со всеми ее явлениями; экспериментатор борется со средой; математик - с загадками математического мира; инженер - с сопротивлением материалов".