Характеристическая функция

Функция 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, обозначаемая в этом случае через uR, называется простейшей.

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

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

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

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

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

uG(Æ) = 0,

т.е. коалиция, не содержащая ни одного игрока, ничего не выигрывает;

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

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

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

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

uG(K) + u(N\K) = 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.

Дата добавления: 2014-01-05