6.6. Дополнение. Выпуклые игры

+ + (6.1)

Множество всех выпуклых игр мы будем обозначать через С . Оправданием такому названию может служить тот факт, что для выпуклой игры «первые разности»

v(S + T)-v(S) (6.2)

при фиксированном Т монотонно возрастают по S.

/ : R+ R+

выпуклая функция, т.е.

f(ax + (1 - а) у) й af(x) + (1 - a)f(y)

при всех х,у G R+ и 0 ^ а ^ 1, то «первые разности» этой функции

f(x + y)-f(x) (х,уе R+)

при фиксированном у монотонно возрастают по х .)

Соотношение (6.2) наводит на мысль, что с-ядро выпуклой игры непусто. Действительно, можно заметить, что условие57

(-v(S+{t})-v(S))b (6.3)

равносильно монотонности (6.2). Утверждение же (6.3) означает, что игроку i целесообразно присоединяться к все большим коалициям; отсюда вытекает стремление к образованию большой коалиции, охватывающей вообще всех игроков. Поэтому естественно ожидать, что образуется максимальная коалиция, а меньшие коалиции этому не будут препятствовать. Следовательно, можно ожидать, что с-ядро непусто. Теорема 6.6.1. Если v ? С , то C(v) ф 0 .

Доказательство ведется по индукции. Для га = 1 доказывать нечего. Предположим, что теорема доказана для га — 1 игроков. Пусть / ={1,...,га},а Т — коалиция из га — 1 игроков. Тогда в силу индуктивного предположения функция имеет непустое с-ядро, т.е. существует такой вектор т° ?

v°(S) = v(SnT)

1устое с-ядр

IRT, что m0(S)b°(S),VScT (6.4)

то0 (Г) = т°(7) = v°(T) = v°(I). Определим вектор m ? IR^, положив

Г 777,9 Z (z Т

m = Ui)-v(n ЦТ. (6-5)

Тогда мы имеем

т(!) = Еге/ тг = Егет т°г + V(I) - V(T) =

(6.6)

= m°(T)+v(I)-v(T) = v(I)

и для S С Т в силу (6.4)

777(5) = m°(S) ^ v°(S) = v{S).

Кроме того, для S 777(5*) = m°(S П Г) + того ^

^ v°(Sr\T) + ml0 =v(Sr\T)+v(I)-v{T) =

= v(S\{i0}) + v(I)-v(I\{i0})Zv(S),

причем последнее неравенство в цепочке следует из (6.3).

Идея доказательства здесь достаточно прозрачна: выигрыш делится между членами коалиции Т соответственно некоторому дележу из C(v°) , а вновь присоединяющемуся игроку го выплачивается все то, что он приносит большой коалиции.

А это позволяет подойти к следующей конструкции. Теорема 6.6.2. Пусть

q> = s0cs1cs2c---csn = i — (6.7)

строго возрастающая последовательность коалиций из I, для которой ^ \ = 1 при всех i = 1,..., п . Тогда ра

венства

x(Si \ Si-!) = v(Si) - v(Si-1) (6.8)

определяют некоторый дележ х ? C(v) .

Доказательство аналогично доказательству предыдущей теоремы.

Процесс, описываемый цепочкой (6.7), достаточно нагляден: пустая коалиция So за счет вступления в нее новых игроков последовательно увеличивается каждый раз на одного игрока. Этот порядок вступления определяет некоторую перестановку игроков ТГ . Перестановка ТГ, соответствующая (6.7), однозначно определяется равенством

тг (Si \ Si-i) = i (i = l,...,n). (6.9)

Пусть теперь тг :/—>?/ — некоторая перестановка. Ясно, что она порождает некоторый порядок игроков. Обозначим множество первых (согласно этому порядку) i игроков через

S7 = {к : тг (к) й г}.

Если тг получено из соотношения (6.7) на основании (6.9), то из к G Si , к G Sj \ Sj-i (для некоторого j ^ i) вытекает

тг (к) = тг (Sj \ Sj—i) Отсюда

Q7T с.

iJ i — iJ i .

Поэтому справедлива следующая теорема.

Теорема 6.6.3. (Shapley, 1979). Для любой перестановки тг : I —> I дележ ж71", задаваемый равенством

xZ-4i) = v(Si)-v(Si-1), (6.10)

принадлежит C(v).

Замечание 6.6.1. Легко видеть, что

xl = v(sv(k)) - w(sv(fc)_i). (б.н)

Теорема 6.6.4. (Shapley, 1979). Каждый дележ ж71", описываемый равенством вида (6.10), является крайней точкой58множества C(v), и все крайние точки могут быть получены таким путем.

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

В силу равенства (6.8) для заданных ж71" = ж и Sf = Si мы имеем

ж (Si) = x(Si \ Si-1) + x(Si-i \ Si-2) H h x(S 1 \ S0) = v(Si),

т.е. ж является решением системы п уравнений. Из равенства (6.10) следует, что ж является единственным решением этой системы. Наконец, по теореме 6.6.3 х ? С , так что х является крайней точкой с-ядра.

Пусть, наоборот, х — некоторая крайняя точка с-ядра. Рассмотрим систему коалиций

а = а(х) = {S С I\x(S) = v(S)}. (6.12)

Эта система замкнута относительно операций объединения и пересечения. Действительно, пусть S, Т ? <7 ; тогда

v(SUT) й x(SUT) = x(S) + х(Т) - x(SnT) й

(6.13)

^ v(S) + v(T) - v(SnT) < v(SUT)

и, следовательно, S U T ? a .

Точно так же доказывается, что и S П Т ? а . Пусть

0 = So С Si С • • • С Sm = I — (6.14)

строго возрастающая последовательность коалиций из а , имеющая наибольшую длину. Если тп = п , то наша теорема доказана. Если тп < п, то найдется такое Sk , что

\Sk+i \ Sfc| ^ 2.

Пусть, например, {i,j} С Sfc+i \ Sk ?

Ввиду того, что х как крайняя точка является единственным решением системы

= (S ? <т), (6.15)

ies

существует хотя бы одно такое S ? а , что (не нарушая общности)

i е S, j?S.

Множество Т= (SUS^) nSfc+i является элементом а ввиду замкнутости семейства а относительно операций объединения и пересечения. Кроме того, для Т имеет место включение

Sk с т с Sk+i, а это невозможно в силу того, что (6.14) — последовательность наибольшей длины. Поэтому случай то < га невозможен, и теорема доказана.

Теорема 6.6.5. Пусть функция v ? С такова, что для S,T ? В, для которых S \ Т ф 0 и Т \ S ф Ф, всегда имеет место

v(S) + v(T) < v(SUT) + v(SnT). (6.16)

Тогда все дележи ж71" различны. В этом случае С имеет ровно nl крайних точек.

Доказательство. Пусть множества S и Т удовлетворяют условиям теоремы, а ж — некоторая крайняя точка С . Покажем, что если ж — крайняя точка С , a S,T ? <т(ж) , то либо S С Т, либо S Э Т .

Действительно, из x(S) = v(S) и х(Т) = v(T) на основании свойств а(х) следовало бы, что x(S U Г) = v(S U Г) и x(S Г) Т) = v(S П Г) . Отсюда, в свою очередь, вытекало бы

и(5) + v(T) = x(S) + ж (Г) = x(S U Г) + x(S П Г) = = «(SUT) + o(5nr),

а это противоречит (6.16).

Поэтому множества из <т(ж) можно упорядочить так:

0 = SO С SI С ? ? ? С SM = I.

Мы уже видели, что должно быть то = га и, следовательно, соответствие между крайней точкой ж и системой (6.7) является взаимно однозначным.

Следствие 6.6.1. Если v ? С и выполнено (6.16), то значение Шепли игры v есть центр тяжести с-ядра C(v) .

Доказательство немедленно следует из теоремы и формулы, определяющей значение Шепли.