назад Оглавление вперед


[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [ 78 ] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90]


78

Рис. 4.7

Рис. 4.8

Рис. 4.9

то имеются три параллелограмма доминируемых им дележей (рис. 4.8); если одно из неравенств в (12.1) не имеет места (пусть это будет для определенности третье неравенство), то имеются два параллелограмма (рис. 4.9); наконец, если не имеют места два неравенства из (12.1) (скажем, последние два), то - лишь один параллелограмм (рис. 4.10).

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

12.6*. Комбинаторное разнообразие вариантов доминирования дележей в игре возрастает с увеличением числа игроков весьма быстро. Ограничимся кратким описанием положения дел в случае игр четырех лиц.

Пусть V - характеристическая функция над /= (1, 2, 3, 4}. Согласно сказанному в п. 11.4, доминирование возможно здесь лишь по двухэлементным и трехэлементным коалициям, т.е. всего здесь может быть до С4 + cl = = 10 типов доминирования.



Будем считать, что v задана в О - 1-редуцированной форме, и для любых попарно различных /, /, к,1 из /

v(ij\k) = cj,(12.2)

v(i,ndj,i.(12.3)

Заметим попутно, что согласно монотонности характеристической функции V (см., например, п. 7.1) здесь должно быть di <Ck и di (всего наберется, очевидно, 12 таких неравенств).

12.7*. Возможность х > у наступает тогда, когда дележ х для коалиции

{1, 2, 3 } эффективен, т.е. когда Xi +л:2 +л:з <, С4. Геометрически это означает, что в симплексе дележей соответствующая дележу х точка должна находиться в тетраэдре, отсекаемом от всего симплекса плоскостью + + ?2 + ?з = > где / - барицентрические координаты в этом симплексе. В этом случае х > у будет иметь место, если Xi >yi, х >у2 илгз >Уз,

т.е. если дележ у находится в параллелепипеде с вершинами хи4, изображенном на рис. 4.11. Подобно параллелограмму с рис. 4.5 этот параллелепипед открыт в симплексе всех дележей: он содержит только те свои грани, которые лежат на гранях симплекса.

Аналогично описываются возможности доминирования по остальным трехэлементным коалициям.

12.8*. Доминирование по двухэлементным коалициям опишем на примере коалиции {1, 2}. В этом случае доминирование х> у предполагает

эффективность дележа л: для {1, 2), т.е. неравенство х i-X2 dy. Геометрически это означает, что соответствующая дележу х точка лежит по ту

Рис. 4.11

Рис. 4.12

же сторону от плоскости +Ь =34, что и ребро 34, Доминирование х> у будет при этом иметь место, если Xi> у и Х2 >У2, т.е. если дележ 12

лежит внутри двугранного угла, изображенного на рис. 4.12.

12.9*. Из сказанного видно, что априорное перечисление всех возможных вариантов доминирования представляется уже в случае игр четырех лиц достаточно затруднительным. Вместе с тем выяснение каждого конкретного вопроса о возможном доминировании каких-либо двух заданных дележей не составляет труда.



§ 13. с-ЯДРО

13.1.Как указывалось, доминирование дележом х дележа у можно понимать как предпочтение дележа х дележу у со стороны одной из коалиций. Это можно понимать так, что всякая попытка предложить "обществу" дележ у может встретить со стороны этой коалиции контрпредложение дележа х. Значит, дележ, который не доминируется никаким другим дележом, можно считать в известном смысле "вполне устойчивым".

Определение. Множество дележей в кооперативной игре Г (характеристической функции v), каждый из которых не доминируется какими-либо другими дележами, назьшается с-ядром этой игры и обозначается через C(i;) илиС(Г). □

13.2.Удобная характеризация принадлежащих с-ядру дележей дается следующей теоремой.

Теорема. Для того чтобы дележ х принадлежал с-ядру кооперативной игры с характеристической функцией и, необходимо и достаточно, чтобы он был абсолютно неэффективным, т,е. чтобы для любой коалиции К выполнялось неравенство

v(K)x(K).(13.1)

Необходимость. Пусть для дележа л: при некоторой коалиции К v(K) > х(К) . Заметим, что коалиция К должна здесть состоять более чем из одного игрока, иначе это неравенство противоречило бы свойству индивидуальной рациональности дележа х Равным образом, коалиция К должна быть отлична и от /. Мы имеем

д:(/\ К) =v(I) -х(К) v(K) -х(К) >0. Возьмем теперь 6, для которого

И составим вектор У = (Ух, - - - ,Уп) > положив

Xf + е,если i ,

(х(К) ~\К\ е), если iK.

I/ \1

Непосредственная проверка показывает, что вектор у есть дележ, причем у X. Поэтому X не принадлежит с-ядру v.

Достаточность. Предположив, что дележх доминируется дележом у, мы получаем для некоторой коалиции К х(К) < у (К) < v(K), что противоречит (13.1). □

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

[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [ 78 ] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90]