Кооперативные игры
Кооперативные игры получаются в тех случаях, когда, в игре n игроков разрешается образовывать определённые коалиции. Обозначим через N множество всех игроков, N={1,2,...,n}, а через K – любое его подмножество. Пусть игроки из K договариваются между собой о совместных действиях и, таким образом, образуют одну коалицию. Очевидно, что число таких коалиций, состоящих из r игроков, равно числу сочетаний из n по r , то есть , а число всевозможных коалиций равно
= 2n
– 1.
Из этой формулы видно, что число всевозможных коалиций значительно растёт в зависимости от числа всех игроков в данной игре. Для исследования этих игр необходимо учитывать все возможные коалиции, и поэтому трудности исследований возрастают с ростом n. Образовав коалицию, множество игроков K действует как один игрок против остальных игроков, и выигрыш этой коалиции зависит от применяемых стратегий каждым из n игроков.
Функция u, ставящая в соответствие каждой коалиции K наибольший, уверенно получаемый его выигрыш u(K), называется характеристической функцией игры. Так, например, для бескоалиционной игры n игроков u(K) может получиться, когда игроки из множества K оптимально действуют как один игрок против остальных NK игроков, образующих другую коалицию (второй игрок).
Характеристическая функция u называется простой, если она принимает только два значения: 0 и 1. Если характеристическая функция u простая, то коалиции K, для которых u(K)=1, называются выигрывающими, а коалиции K, для которых u(K) = 0, – проигрывающими.
Если в простой характеристической функции u выигрывающими являются те и только те коалиции, которые содержат фиксированную непустую коалицию R, то характеристическая функция u, обозначаемая в этом случае через uR
, называется простейшей.
Содержательно простые характеристические функции возникают, например, в условиях голосования, когда коалиция является выигрывающей, если она собирает более половины голосов (простое большинство) или не менее двух третей голосов (квалифицированное большинство).
Более сложным является пример оценки результатов голосования в Совете безопасности ООН, где выигрывающими коалициями являются все коалиции, состоящие из всех пяти постоянных членов Совета плюс ещё хотя бы один непостоянный член, и только они.
Простейшая характеристическая функция появляется, когда в голосующем коллективе имеется некоторое “ядро”, голосующее с соблюдением правила “вето”, а голоса остальных участников оказываются несущественными.
Обозначим через uG
характеристическую функцию бескоалиционной игры. Эта функция обладает следующими свойствами :
персональность
uG
(Æ) = 0,
т.е. коалиция, не содержащая ни одного игрока, ничего не выигрывает;
супераддитивность
uG
(KÈL) ³ uG
(K) + uG
(L), если K, L Ì N, KÇL ¹ Æ,
т.е. общий выигрыш коалиции не меньше суммарного выигрыша всех участников коалиции;
дополнительность
uG
(K) + u(NK) = u(N)
т.е. для бескоалиционной игры с постоянной суммой сумма выигрышей коалиции и остальных игроков должна равняться общей сумме выигрышей всех игроков.
Распределение выигрышей (делёж) игроков должно удовлетворять следующим естественным условиям: если обозначить через xi
выигрыш i-го игрока, то, во-первых, должно удовлетворяться условие индивидуальной рациональности
xi
³ u( i ), для i ÎN
т.е. любой игрок должен получить выигрыш в коалиции не меньше, чем он получил бы, не участвуя в ней (в противном случае он не будет участвовать в коалиции); во-вторых, должно удовлетворяться условие коллективной рациональности
= u(N)
т.е. сумма выигрышей игроков должна соответствовать возможностям (если сумма выигрышей всех игроков меньше, чем u(N), то игрокам незачем вступать в коалицию; если же потребовать, чтобы сумма выигрышей была больше, чем u(N), то это значит, что игроки должны делить между собой сумму большую, чем у них есть).
Таким образом, вектор x = (x1
, ..., xn
), удовлетворяющий условиям индивидуальной и коллективной рациональности, называется дележём в условиях характеристической функции u.
Система {N, u}, состоящая из множества игроков, характеристической функции над этим множеством и множеством дележей, удовлетворяющих соотношениям (2) и (3) в условиях характеристической функции, называется классической кооперативной игрой.
Из этих определений непосредственно вытекает следующая
Теорема. Чтобы вектор x = (x1
, ..., xn
) был дележём в классической кооперативной игре {N, u},
необходимо и достаточно, чтобы
xi
= u( i ) + ai
, (iÎN)
причём
ai
³ 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) + a1
, u(2) + a2
, ... , u(n) +an
)
где
ai
³ 0 ( i Î N ) , u(N) —> 0
Кооперативная игра с множеством игроков N и характеристической функцией u называется стратегически эквивалентной игрой с тем же множеством игроков и характеристической функцией u1
, если найдутся такие к > 0 и произвольные вещественные Ci
( iÎN ), что для любой коалиции К Ì N имеет место равенство:
u1
(K) = k u (K) +
Смысл определения стратегической эквивалентности кооперативных игр (с.э.к.и.) состоит в том что характеристические функции с.э.к.и. отличаются только масштабом измерения выигрышей k и начальным капиталом Ci
. Стратегическая эквивалентность кооперативных игр с характеристическими функциями u и u1
обозначается так u~u1
. Часто вместо стратегической эквивалентности кооперативных игр говорят о стратегической эквивалентности их характеристических функций .
Справедливы следующие свойства для стратегических эквивалентных игр:
1. Рефлексивность, т.е. каждая характеристическая функция эквивалентна себе u~u.
2. Симметрия, т.е. если u~u1
, то u1
~u.
3. Транзитивность, т.е. если u~u1
и u1
~u2
, то u~u2
.
Из свойств рефлексивности, симметрии и транзитивности вытекает, что множество всех характеристических функций единственным образом распадается на попарно непересекающиеся классы, которые называются классами стратегической эквивалентности.
Отношение стратегической эквивалентности игр и их характеристических функций переносится на отдельные дележи :
пусть u~u1
, т.е. выполняется (5), и x = (x1
, ..., xn
) – дележи в условиях характерис- тической функции u; рассмотрим вектор x1
= (, ..., ) , где = k xi
+Ci
; для него выполняется
= k xi
+ Ci
³ k u( i ) + Сi
= u1
( i );
т.е. выполняется условие индивидуальной рациональности, и
== k+= k u(N) += u1
(N)
т.е. выполняется условие коллективной рациональности. Поэтому вектор является дележом в условиях u1
. Говорят, что делёж x1
соответствует дележу x при стратегической эквивалентности u~u1
.
Кооперативная игра называется нулевой, если все значения её характеристической функции равны нулю. Содержательное значение нулевой игры состоит в том, что в ней игроки не имеют никакой заинтересованности .
Всякая несущественная игра стратегически эквивалентна нулевой .
Определение. Кооперативная игра с характеристической функцией u имеет (0,1)-редуцированную форму, если выполняются соотношения :
u( i ) = 0 ( i Î N ),
u(N) = 1.
Теорема. Каждая существенная кооперативная игра стратегически эквивалентна одной и только одной игре в (0,1)-редуцированной форме.
Сформулированная теорема показывает, что мы можем выбрать игру в (0,1)-редуцированной форме для представления любого класса эквивалентности игр. Удобство этого выбора состоит в том, что в такой форме значение u(K) непосредственно демонстрирует нам силу коалиции S (т.е. ту дополнительную прибыль, которую получают члены коалиции, образовав её), а все дележи являются вероятностными векторами.
В игре в (0,1)-редуцированной форме дележём является любой вектор x = (x1
, ..., xn
), для которого
xi
³ 0 (i Î N) = 1.
Перечисление характеристических функций с малым числом игроков.
Как было сказано ранее, для каждого множества игроков N существует единственный класс стратегически эквивалентных несущественных игр с множеством игроков N. Таким образом, остаётся рассмотреть классы существенных кооперативных игр.
Рассмотрим сначала классы игр в (0,1)-редуцированной форме для случая игр с нулевой суммой.
1. Игры 2-х игроков. Всякая кооперативная игра двух игроков с нулевой суммой является несущественной.
Доказательство. Предположим, что имеется существенная кооперативная игра двух игроков с характеристической функцией u, Тогда она должна быть стратегически эквивалентна некоторой игре в (0,1)-редуцированной форме с характеристической функцией u1
, что означает следующее :
u1
(1) = 0, u1
(2) = 0, u1
(1,2) = 1
По свойству дополнительности должно
u1
(2) = u1
(1,2) – u1
(1) = 1 – 0 =1,
что противоречит (*). А это значит, что наше предположение о существенности кооперативной игры двух игроков с нулевой суммой неверно.
Итак, класс кооперативных игр двух игроков с нулевой суммой ограничивается несущественными играми.
2. Игры 3-х игроков. Пусть u – характеристическая функция существенной игры в (0,1)-редуцированной форме, тогда
u(1) = u(2) = u(3) = 0, u(1,2,3) = 1.
По свойству дополнительности имеем :
u(1,2) = u(1,2,3) – u(3) = 1– 0 =1,
u(1,3) = u(1,2,3) – u(2) = 1– 0 =1,
u(2,3) = u(1,2,3) – u(1) = 1– 0 =1,
и, таким образом, характеристическая функция полностью определена. Итак, имеется два класса кооперативных игр трёх игроков с нулевой суммой: класс существенных и класс несущественных игр.
3. Игры 4-х игроков. Рассмотрим все классы стратегической эквивалентности таких игр.
Прежде всего имеется класс несущественных игр в (0,1)-редуцированной форме определим характеристическую функцию u такой игры
u(1) = u(2) = u(3) = u(4) = 0
u(1,2,3,4) = 1.
Исходя из свойства дополнительности, получаем
u(1,2,3) = u(1,2,3,4) – u(4) = 1– 0 =1;
u(1,2,4) = u(1,2,3,4) – u(3) = 1– 0 =1;
u(1,3,4) = u(1,2,3,4) – u(2) = 1– 0 =1;
u(2,3,4) = u(1,2,3,4) – u(1) = 1– 0 =1.
Теперь необходимо определить значения характеристической функции на коалициях двух игроков. Всего таких коалиций шесть
(1,2), (1,3), (1,4), (2,3), (2,4), (3,4).
Характеристическая функция на этих коалициях согласно свойству дополнительности удовлетворяет только следующим соотношениям :
u(1,4) = 1– u(2,3),
u(1,3) = 1– u(2,4),
u(1,2) = 1– u(3,4).
Так как значений неизвестных шесть, а соотношений только три, то значения из шести могут быть выбрана произвольно. Обозначим эти произвольные значения через x1
, x2
, x3
, т.е.
u(1,4) = x1
, u(2,4) = x2
, u(3,4) = x3
,
Тогда
u(2,3) = 1– x1
, u(1,3) = 1– x2
, u(1,2) = 1– x3
.
Кроме того должно быть
0 £ x1
, x2
, x3
£ 1 ,
так как значение характеристической функции на коалиции из двух игроков не может быть меньше, чем значение характеристической функции для одного из этих игроков (равное нулю для одного игрока), и не может быть больше, чем значение характеристической функции для коалиции из трёх игроков (равное 1 для трех игроков). Геометрически (x1
, x2
, x3
) можно изобразить как точку единичного куба, т.е. каждому классу стратегической эквивалентности игр четырёх игроков будет соответствовать точка единичного куба.
Итак, множество классов стратегической эквивалентности существенных игр четырёх игроков бесконечно и зависит от трёх произвольных параметров.
4. Игры, состоящие из более чем 4-х игроков, имеют большее разнообразие классов стратегической эквивалентности существенных игр.
Так, размерность множества классов игр n игроков равна , т.е. имеется произвольных параметров.
Рассмотрим теперь кооперативные игры без условия постоянства суммы.
1. Для игр 2-х игроков множество N={1,2}, условия редуцированности дают
u(Æ) = u(1) = u(2) = u(1,2) = 1.
Таким образом, существенные кооперативные игры двух игроков с ненулевой суммой составляют один класс стратегической эквивалентности.
2. Для игр 3-х игроков множество N={1,2,3}, условия редуцированности дают
u(Æ) = u(1) = u(2) = u(3) = 0; u(1,2,3) = 1.
Значения характеристической функции на множествах коалиций двух игроков произвольные (здесь нет условия дополнительности)
u(1,2) = C3
, u(1,3) = C2
, u(2,3) = C1
,
но удовлетворяющие условию
0 £ C1
, C2
, C3
£ 1.
Таким образом, классы стратегической эквивалентности общих кооперативных игр трёх игроков могут быть поставлены в соответствие точкам трёхмерного единичного куба подобно тому, как это получилось для игр 4-х игроков с нулевой суммой.
Для игр более 3-х игроков с ненулевой суммой рассмотрения аналогичны.
Для исследования игр большое значение имеет возможность учёта предпочтения дележей, который осуществляется с помощью понятия доминирования.
Определение. Пусть имеется два дележа x = (x1
, ..., xn
) и y = (y1
, ..., yn
) в кооперативной игре G = {N,u}, и KÌ N – некоторая коалиция. Тогда делёж x доминирует y по коалиции K, если
1) £ u(K) (свойство эффективности доминирующего платежа)
2) xi
> yi
для всех iÎK (свойство предпочтительности)
Свойство эффективности означает, что сравниваемый коалицией делёж x должен быть, реализуемым этой коалицией: сумма выигрышей каждого из членов коалиции не должна превосходить уверенно получаемое ею количество. В противном случае коалиция, встретившись с дележём, дающим ей столько, сколько она самостоятельно не в состоянии добиться, должна согласиться на него и не заниматься его сравнением с какими либо другими дележами.
Условие предпочтительности отражает необходимость “единодушия” в предпочтении со стороны коалиции: если хотя бы одно из неравенств xi
> yi
будет нарушено, т.е. если хотя бы для одного из членов коалиции K выигрыш в условиях дележа y будет не меньшим, чем в условиях дележа x, то можно будет говорить о предпочтении дележа x дележу y не всей коалицией K, а только теми её членами, для которых соответствующее неравенство xi
> yi
соблюдается.
Соотношение доминирования x над y по коалиции K обозначается через
.
Определение. Делёж x доминирует y, если существует такая коалиция K, для которой делёж x доминирует y. Это доминирование обозначается так:
x > y.
Наличие доминирования x > y означает, что в множестве игроков N найдётся коалиция, для которой x предпочтительнее y. Отношение доминирования не обладает полностью свойствами рефлексивности, симметрии, транзитивности, возможна только частичная симметрия и транзитивность. Соотношение доминирования возможно не по всякой коалиции. Так, невозможно доминирование по коалиции, состоящей из одного игрока или из всех игроков.
Справедлива следующая теорема.
Теорема. Если u и u1
– две стратегически эквивалентные характеристические функции, причём дележам x и y соответствуют дележи и , то из x > y следует >.
Очев
В любой несущественной игре имеется только один делёж, поэтому никаких доминирований в ней нет.
Рассмотрим доминирование дележей в существенной игре на следующем примере.
Пример. Пусть имеется (0,1)-редуцированная форма существенной игры трёх игроков с постоянной суммой (равной 1). Поскольку доминирование невозможно ни по одной из одноэлементных коалиций 1,2,3, а также по коалиции, состоящей из всех трёх игроков, то доминирование возможно только по одной из двухэлементных коалиций {1,2}, {1,3}, {2,3}.
Для наглядности доминирования дележей введём понятие бароцентрических координат. Осями координат служат три оси x1
, x2
, x3
, составляющие между собой одинаковые углы 60о
, ось x3
находится на расстоянии единицы от точки пересечения осей x1
и x2
(рис.1), координаты точки x = (x1
, x2
, x3
) – соответственно расстояния от этой точки до осей x1
, x2
, x3
, взятые с такими знаками, как указано на рис.1. (Например, для точки x на рис.1. x1
< 0, x2
> 0, x3
> 0).
В барицентрической системе координат всегда выполняется равенство
x1
+ x2
+ x3
= 1.
В плоскости всегда имеется точка с координатами x1
, x2
, x3
, удовлетворяющими равенству (6). По этому бароцентрическая система координат автоматически удовлетворяет одному из условий, определяющих исход игры трёх игроков. С другой стороны, поскольку игра в (0, 1)-редуцированной форме, то точка x должна находиться в заштрихованном треугольнике (см. рис. 2). Дележи x1
, x2
, x3
должны удовлетворять неравенствам
x1
+ x2
£ u(1, 2), x1
+ x3
£ u(1, 3), x2
+ x3
£ u(2, 3).
Очевидно, из условия дополнительности, что
x1
+ x2
= 1 - x3
£ 1 = u(1, 2), x1
+ x3
£ 1, x2
+ x3
£ 1.
Делёж x = (x1
, x2
, x3
) доминирует дележ y = (y1
, y2
, y3
)
по коалиции {1, 2}, если x1
> y1
, x2
> y2
;
по коалиции {1, 3}, если x1
> y1
, x3
> y3
;
по коалиции {2, 3}, если x2
> y2
, x3
> y3
,
т.е. если делёж y находится в одном из заштрихованных параллелограммов (за исключением трёх граничных прямых, проходящих через точку x) на рис. 3, то делёж x доминирует делёж y, а всякая точка находящаяся в не заштрихованных треугольниках, является предпочтительнее исхода x.
x3
= - 1 x2
= - 1
x = (x1
, x2
, x3
)
x3
= 1 - C3
x1
= 0
x1
= 1 - C1
x2
= 1 - C2
Рис.3 Рис. 4
Таким образом, если x и y - два исхода и ни один из них не предпочтительнее другого, то соответствующие точки лежат на прямой, параллельной одной из координатных осей.
Пример. Пусть имеется (0, 1)-редуцированная игра трёх игроков с ненулевой суммой.
Рассмотрим сначала условия доминирования дележа x = (x1
, x2
, x3
) над дележём y = (y1
, y2
, y3
) по коалиции {1, 2}. В этом случае имеем :
Поскольку может быть, что C3
< 1 , то первое из условий (7) нельзя отбросить, как это делает- ся в играх с постоянной суммой. Это значит что, x должна быть не ниже прямой
x1
+ x2
= C3
.
Или, учитывая (6), последнее уравнение принимает вид
x3
= 1 + C3
.
Таким образом, если делёж x таков, что
x1
³ 1 - C1
, x2
³ 1 - C2
, x3
³ 1 - C3
,
то имеется три параллелограмма, заштрихованных на рис. 4, находясь в которых, точки x доминируют y.
Если в (8) одно из неравенств, например, третье не имеет места, то есть только 2 парал- лелограмма, заштрихованных на рис. 5, находясь в некоторых точках x доминирует y.
x1
= 1 - C1
x2
= 1 - C2
x2
= 1 - C2
x1
= 1 - C1
x3
= 1 - C3
x
Рис. 5 Рис. 6
Из рассмотренного примера видно, что возможно много вариантов, которые возникают при изучении вопросов, связанных с доминированием дележей в кооперативных играх. С ростом числа игроков чрезвычайно быстро растёт количество таких вариантов. В связи с этим возникает необходимость выделения вполне устойчивых дележей, т.е. таких дележей, которые не доминируются никакими другими дележами. Множество вполне устойчивых дележей в кооперативной игре называется с-ядром этой игры.
Теорема. Для того чтобы делёж x принадлежал с-ядру кооперативной игры с характеристической функцией u, необходимо и достаточно, чтобы для любой коалиции K выполнялось неравенство
Поскольку неравенства (9) линейны относительно x, то из последней теоремы следует, что с-ядро в любой кооперативной игре является выпуклым многогранником.
К особенностям кооперативных игр относительно существования с-ядра относятся :
1) в несущественной игре с-ядро существует и состоит из единственного дележа этой игры;
2) во всякой существенной игре с постоянной суммой с-ядро пусто.
Для общей игры трёх игроков в (0; 1)-редуцированной форме имеем следующее (рис. 7).
Её характеристическая функция имеет вид :
u(Æ) = u(1) = u(2) = u(3) = 0;
u(1, 2, 3) = 1,
u(1, 2) = С3
; u(1, 3) = С2
; u(2, 3) = С1
,
где 0 £ С1
, С2
, С3
£ 1.
На основании последней теоремы для принадлежности дележа x с-ядру необходимо и достаточно выполнение неравенств
x1
+ x2
³ C3
, x1
+ x3
³ C2
, x2
+ x3
³ C1
или, используя равенство x1
+ x2
+ x3
= 1, получим
x3
£ 1 - C3
, x2
£ 1 - C2
, x3
£ 1 - C1
.
3
1 2
Рис. 7
Это означает, что точка x должна лежать ближе к i-й вершине основного треугольника (см. рис. 7), чем прямая
xi
= 1 - Сi
(i = 1,2,3)
Из неравенства (10) путём суммирования получим
x1
+ x2
+ x3
£ 3 - (С1
+ С2
+ С3
)
или, учитывая, что x1
+ x2
+ x3
= 1, получим
С1
+ С2
+ С3
£ 2.
Неравенство (12) является необходимым условием существования непустого с-ядра. С другой стороны, если (12) выполняется, то можно взять такие неотрицательные e1
, e2
, e3
, чтобы
,
и положить
xi
= 1 - Ci
- ei
(i = )
Такие значения xi
и удовлетворяют неравенствам (10), т.е. такой делёж x = (x1
, x2
, x3
) принад- лежит с-ядру.
Геометрически непустое с-ядро является заштрихованным треугольником (рис. 7), со сто- ронами, выраженными уравнениями (11)
3 3
1 2 1 2
Рис. 8 Рис. 9
при условии, что выполняется соотношение
x1
+ x2
+ x3
= 1,
и решения любой пары уравнений (11) являются неотрицательными. Так, например, рассмот- рим систему
x1
= 1 - С1
, x2
= 1 - С2
.
Поскольку 0 £ С1
£ 1, 0 £ С2
£ 1, то x1
, x2
³ 0. Отсюда получаем
x3
= 1 - x1
- x2
= 1 - (1 - С1
) - (1 - С2
) = С1
+ С2
- 1.
Для того, чтобы было x3
³ 0, необходимо чтобы
С1
+ С2
- 1 ³ 0
или
С1
+ С2
³ 1.
В этом случае с-ядро представлено на рис.7 в виде заштрихованного треугольника внутри основного треугольника. Аналогично рассматриваются остальные возможные варианты сочета- ний неравенств. Например, если С1
+ С2
< 1, то с-ядро имеет вид заштрихованного четырёх- угольника внутри основного треугольника (рис.8). Вообще многогранник, представляющий с‑ядро, образуется как выпуклый многогранник пересечением прямых (11) и строк основного треугольника. Если, например, выполняются неравенства
С1
+ С2
< 1; С2
+ С3
< 1; С1
+ С3
< 1,
то с-ядро представляется в виде шестигранника, заштрихованного на рис.9.
Очевидно, в решение кооперативной игры должны входить дележи, лучшие с определён- ной точки зрения. Так, дележи, входящие в с-ядро, являются устойчивыми в несколько пассив- ном смысле, т.е. при этих обстоятельствах нет оснований отклоняться от такого дележа. Одна- ко, найти делёж, который не только не доминировался бы какими-либо другими дележами, но сам доминировал бы любой другой делёж, не удаётся. Поэтому решение отыскивают на пути расширения класса дележей . И это расширение состоит в том, что решением игры должен быть не один делёж, а некоторое их множество.
Дж. фон Нейман и О. Моргенштерн предложили потребовать от множества дележей, которое принимается в качестве решения кооперативной игры следующие два свойства: внут- реннюю устойчивость, состоящую в том, чтобы дележи из решений нельзя было противопоста- вить друг другу, и внешнюю устойчивость, состоящую в возможности каждому отклонению от решения противопоставлять некоторый делёж, принадлежащий решению. В результате мы приходим к следующему определению.
Определение. Решением по Нейману-Моргенштерну (Н-М-решением) кооперативной игры называется множество R дележей в нём, обладающее следующими свойствами :
1) внутренняя устойчивость: никакие два дележа из R не доминируют друг друга;
2) внешняя устойчивость: каков бы ни был делёж S не принадлежащий R, найдётся делёж r, принадлежащий R, который доминировал бы S.
Содержательная интерпретация Н-М-решения состоит в том, что любые две нормы пове- дения, соответствующие Н-М-решению, не могут быть противопоставлены друг другу; каково бы ни было отклонение от допустимых поведений, найдётся такая коалиция, которая будет стремиться к восстановлению нормы.
Теорема. Если в кооперативной игре существует с-ядро C и Н-М-решение R, то CÌ R.
Свойства Н-М-решений.
Н-М-решение кооперативной игры не может состоять только из одного дележа, т.к. в этом случае характеристическая функция игры несущественная.
Недостатки Н-М-решения.
1. Известны примеры кооперативных игр, которые не имеют Н-М-решений. Более того, в настоящее время не известно каких-либо критериев, позволяющих судить о наличии у кооперативных игр Н-М-решений. Тем самым заложенный в Н-М-решении принцип оптимальности не является универсально реализуемым, и область его реализуемости пока остаётся неопределён- ной.
2. Кооперативные игры, если не имеют Н-М-решения, то, как правило, более одного. Поэтому принцип оптимальности, приводящий к Н-М-решению, не является полным: он, вообще говоря, не в состоянии указать игрокам единственной системы норм распределения выигрыша.
3. Решения существенных кооперативных игр состоит более, чем из одного дележа. Таким образом, даже выбор какого-либо конкретного Н-М-решения ещё не определяет выигрыша каждого из игроков.
4. Понятие Н-М-решения отражает только в очень малой степени черты справедливости.
Перечисленные недостатки отражают положение дел в действительности: большинство экономических и социальных проблем допускает множественные решения, и эти решения не всегда поддаются непосредственному сравнению по их предпочтительности.
Перечисленные недостатки Н-М-решения коалиционных игр способствуют поискам новых подходов. Одним из таких подходов является подход Шепли, суть которого в том, что он строиться на основании аксиом, отражающих справедливость дележей.
Определение. Носителем игры с характеристической функцией u называется такая коали-ция T, что
u(S) = u(S Ç T)
для любой коалиции S.
Смысл носителя T состоит в том, что любой игрок, не принадлежащий T, является нейтральным, он не может ничего внести в коалицию и ему ничего не следует выделять из общих средств.
Определение. Пусть u – характеристическая функция кооперативной игры n игроков, p – любая перестановка множества N игроков. Через pu обозначим характеристическую функцию и та- кой игры, что для коалиции S = {i1
, i2
, ..., iS
} будет
u ({p( i1
), p( i2
), ..., p( iS
)}) = u(S).
Содержательный смысл функции pu состоит в том, что если в игре с характеристической функцией u поменять местами игроков согласно перестановке p, то получим игру с характерис- тической функцией pu.
Аксиомы Шепли.
1о
. Аксиома эффективности. Если S – любой носитель игры с характеристической функцией u, то
= u(S)
Иными словами, “справедливость требует”, что при разделении общего выигрыша носителя игры ничего не выделять на долю посторонних, не принадлежащих этому носителю, равно как и ничего не взимать с них.
2о
. Аксиома симметрии. Для любой перестановки p и iÎN должно выполняться
(pu) = ji
(u),
т.е. игроки, одинаково входящие в игру, должны “по справедливости” получать одинаковые выигрыши.
3о
. Аксиома агрегации. Если есть две игры с характеристическими функциями u¢ и u¢¢, то
j i
(u¢ + u¢¢) = j i
(u¢) + j i
(u¢¢),
т.е. ради “справедливости” необходимо считать, что при участии игроков в двух играх их выигрыши в отдельных играх должны складываться.
Определение. Вектором цен (вектором Шепли) игры с характеристической функцией u называется n-мерный вектор
j (u) = (j1
(u), j2
(u), ..., jn
(u)),
удовлетворяющий аксиомам Шепли.
Существование вектора Шепли вытекает из следующей теоремы
Теорема. Существует единственная функция j, определённая для всех игр и удовлетворяющая аксиомам Шепли.
Определение. Характеристическая функция wS
(T), определённая для любой коалиции S, называется простейшей, если
wS
(T) =
Содержательно простейшая характеристическая функция описывает такое положение дел, при котором множество игроков S выигрывает единицу тогда и только тогда, когда оно содержит некоторую основную минимальную выигрывающую коалицию S.
Можно доказать, что компоненты вектора Шепли в явном виде запишутся следующим образом
где t – число элементов в T.
Вектор Шепли содержательно можно интерпретировать следующим образом: предельная величина, которую вносит i-й игрок в коалицию T, выражается как
u(T) - u(T {i})
и считается выигрышем i-го игрока; gi
(T) – это вероятность того, что i-й игрок вступит в коалицию T {i}; ji
(u) – средний выигрыш i-го игрока в такой схеме интерпретации. В том случае, когда u – простейшая,
Следовательно
,
где суммирование по T распространяется на все такие выигрывающие коалиции T, что коалиция T {i}не является выигрывающей.
Пример. Рассматривается корпорация из четырёх акционеров, имеющих акции соответственно в следующих размерах
a1
= 10, a2
= 20, a3
= 30, a4
= 40.
Любое решение утверждается акционерами, имеющими в сумме большинство акций. Это решение считается выигрышем, равным 1. Поэтому данная ситуация может рассматриваться как простая игра четырёх игроков, в которой выигрывающими коалициями являются следующие:
{2; 4}, {3; 4},
{1; 2; 3}, {1; 2; 4}, {2; 3; 4}, {1; 3; 4},
{1; 2; 3; 4}.
Найдём вектор Шепли для этой игры.
При нахождении j1
необходимо учитывать, что имеется только одна коалиция 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-го игрока ситуация естественная, отвечающая силе их капитала.