Игры с ненулевой суммой и кооперативные

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

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

     

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

     Первое допущение симметрия: предполагается, что решение не зависит от того, какие номера присвоены игрокам.

      Второе допущение - инвариантность относительно линейных преобразований: решение не зависит от монотонных линейных преобразований платежей.

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

     Четвертое допущение оптимальность по Парето: не может быть решением такой набор платежей, помимо которого существует какой-нибудь другой набор платежей, более выгодный хотя бы для одного игрока. Если эти условия выполнены, то единственным решением является пара платежей (П^1*,П²*), которые максимизируют произведение превышений этих платежей над платежами при угрозе

     max (П¹-Т¹) (П²-Т²)

                                                  П¹,П²

     Здесь П¹, П^{2 -} выигрыш каждого игрока; Т¹, Т² выигрыши каждого игрока в точке угрозы. На рис. 3 решение представлено в геометрической форме. Заштрихованная часть плоскости соответствует множеству возможных платежей это множество выпукло, так как игроки могут применять смешанные стратегии.

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

      П² Выигрыш игрока 2

       (П¹ –Т¹)(П²-Р²) = const

       Направление наискорейшего роста

      ……..

      Т^{2      S}

      ………… Т точка угрозы                 _{Решение Нэша}

      …………………..

      ……... Т¹ П¹

                       …….                                               Выигрыш игрока 1 

     Рис. 3 Решение Нэша в задаче торгов

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

N = {1,2,..,п},

то любое подмножество S множества N является коалицией; характеристическая функция указывает, чему равен гарантированный выигрыш для S. Таким образом, характеристическая функция представляет собой вещественную функцию, область определения которой состоит из 2ⁿ возможных подмножеств множества N*. Запишем эту функцию в виде

     v(S),     где   S С N.

                v( Ø) = 0;

                v(1) = 0,      v(2) = 0, v (3) = 0;

                v (l,2) = 0,   v (1,3) = 0,2,   v (2,3) = 0,2;

                 v ( 1,2,3) = v (N) = 1

     Рис. 4. Характеристическая функция для игры трех участников

     Пример характеристической функции для игры трех лиц представлен на рис. 4. Здесь каждая из четырех строк соответствует значениям характеристической функции для коалиций, число игроков в которых равно соответственно 0, 1, 2, 3. Первая строка отражает предположение, что максимальный выигрыш для пустого множества равен нулю. Вторая строка показывает, что выигрыш любого игрока, действующего в одиночку, равен нулю. В третьей строке указаны выигрыши трех коалиций, которые могут быть составлены из двух игроков. Если игроки 1 и 2 действуют совместно, они могут гарантировать себе выигрыш в размере 0,1: коалициям игроков 1 и 3 или 2 и 3 гарантирован выигрыш, равный 0.2. Наконец последняя строка показывает, что если все игроки объединяются в «большую коалицию», то выигрыш равен 1. Рассматриваемая игра представлена в нормализованной форме 0-1:

                            v(i) = 0,    при любом i € N.

v(N) = 1.    где N = {1,…, n},

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

v(АỤВ)≥ v (А) + v(В),

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

     Вектор П n-мерного евклидова пространства, компонентами которого являются суммарные выигрыши каждого отдельного игрока, называется «дележом»:

П = (П¹, П² ,..Пⁿ),

     где Пⁱ    -   выигрыш i-го игрока (i  = 1,2, …п).

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

                             _n

^{v(N) =   ∑ Пi = ∑ Пi}

        ^{i€N                 i=0}

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

^{Пi ≥ v(}{i}) при любом   i € N.

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

     Одним из слабых критериев доминирования на множестве 
дележей является критерий, называемый решением по фон Ней- 
манну-Моргенштерну. Множество игроков называется эффек- 
тивным при данном дележе, если их общий выигрыш после 
объединения в коалицию будет по меньшей мере равен сумме 
выигрышей, получаемых каждым игроком в отдельности. Следовательно, коалиция S является эффективной при дележе П = 
= (П¹, …Пⁿ), если

v(S) ≥ ∑Пⁱ.

            ^i€S

     В качестве примера рассмотрим игру, изображенную на рис. 4. 
В этой игре множество, состоящее из игрока 2 и игрока 3 является эффективным при дележе (0,95; 0; 0,05). Действительно, если 
они образуют коалицию, то их общий выигрыш составит 0,2. 
а это больше того, что можно получить согласно данному де- 
лежу. Дележ П₁ = (П₁¹, П₁², .. ,П₁ⁿ)  доминирует, над дележом П₂ = (П₁¹, П₂², .. ,П₂ⁿ)  , если существует такая коалиция игроков, эффективная при П₁, что каждый из игроков, вступивших в коалицию, получает при П₁ больше, чем при П₂. Иначе говоря, имеется некоторая коалиция S, такая, что

v(S) ≥ ∑П₁ ⁱ.

         ^{все  i€S}

     причем каждый член этой коалиции получает при П₁ больше, чем при П₂

П₁ ⁱ> П₂ ⁱ при всех i€S

     Так, например, в игре, изображенной на риc. 4. дележ П₁ = (0,1;0,8;0,1) доминирует над П₂ = (0.05:0.9:0,05). Действительно, коалиция (1,3) является эффективной при П₁ и оба игрока 1 и 3 получают при П₁ больше, чем при П₂. Если удастся воспрепятствовать независимым действиям игроков, то возможность образования коалиции (1,3) служит гарантией того, что дележ (0,05;0,9;0,05) может никогда не использоваться в игре.

     Решением игры по фон Нейману и Моргенштерну называется множество дележей со следующими свойствами: ни один из дележей этого множества не доминирует над другим дележом из того же множества; для любого дележа, не входящего в множество, существует доминирующий дележ, принадлежащий данному множеству. Этот слабый критерий доминирования обычно несколько сужает множество дележей, однако он не приводит, как правило, к множеству, состоящему из одного дележа. В действительности, решение фон Неймана - Моргенштерна часто содержит бесконечное число дележей. В игре более чем с двумя участниками даже и число решений фон Неймана- Моргенштерна (т.е. число множеств дележей, каждое из которых является решением фон Неймана Моргенштерна) может быть либо очень большим, либо бесконечным. Кроме того, существует ряд примеров игр, которые не обладают решениями фон Неймана-Моргенштерна [5].

     Более сильный критерий доминирования на множестве де- 
лежей можно задать с помощью понятия «ядра» игры. Ядро — 
это некоторое подмножество каждого решения фон Неймана- 
Моргенштерна (если такие решения существуют). Число дележей, входящих в ядро, значительно меньше, чем в решении 
фон Неймана-Моргенштерна, поскольку дележи, входящие в 
ядро, должны удовлетворять следующему условию: каждая из 
коалиций при данном дележе получает по меньшей мере столько, сколько могли бы получить в сумме входящие в нее игроки, 
действуя самостоятельно. Ядром называется множество всех недоминируемых дележей, т.e. таких дележей П= (П¹, .. ,Пⁿ) , которые удовлетворяют условию

     ∑П ⁱ ≥ v(S)   для любого подмножества S из N.

                                                    ^i€S