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


[Старт] [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]


72

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

5.3.Непосредственно из соотношения (5.2) следует, что характеристическая функция, аффинно эквивалентная характеристической функции, обладающей условием дополнительности, сама обладает этим свойством.

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

5.5.Поучительным является пример аффинного преобразования характеристической функции vv\ при котором к = \, Siai-v(i). В этом случае для любого А С У будет

v(K) = v(K)+ S aiv(K) S v(i)0,

iEKiEK

Т.е. функция v{K) оказывается неотрицательной.

Таким образом, всякая характеристическая функция аффинно эквивалентна неотрицательной.

Из неравенства (4.3) непосредственно следует, что всякая супераддитивная неотрицательная функция является монотонной.

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

и\7гК) = и(К). □(5 3)

Теорема п. 1.10 означает, что изоморфные бескоалиционные игры имеют изоморфные характеристические функции.

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

5.7.Определение. Изоморфизм характеристической функции на себя называется ее автоморфизмом. □

Если тг есть автоморфизм характеристической функции v, то (5.3) переписывается как

1;(7гА) v(K).

Утверждение п. 1.11 означает, что автоморфизм бескоалиционной игры порождает автоморфизм ее характеристической функции.

Очевидно, тождественная ("единичная") перестановка тг элементов множества / является автоморфизмом любой характеристической функции V над /; если перестановка п есть автоморфизм v над /, то обратная ей перестановка тг" также является автоморфизмом v\ наконец, если тг и тг" - два автоморфзима i\ то их произведение тгтг" ("композиция") также является автоморфизмом v. ("казанное означает, что множество всех автоморфизмов характеристической функции составляет группу.



§ 6. АДДИТИВНОСТЬ в ХАРАКТЕРИСТИЧЕСКИХ ФУНКЦИЯХ

6.1.Крайним ("вырожденным") случаем супераддитивности характеристической функции является ее аддитивность.

Определение. Характеристическая функция v называется аддитивной, если для любыхK,L С IcK П1 =ф имеет место

v(K) +i;(L) =v(KUL).(6.1)

Характеристическая функция, не являющаяся аддитивной, называется строго супераддитивной. □

Тривиальной индукцией по числу объединяемых коалиций устанавливается, что для аддитивной характеристической функции v при любых попарно пересекающихся коалициях!, . . . ,Kj будет

Z v{Ki) = v{ и К,)-(6.2)

/=11=1

в частности, если каждая из этих коалиций состоит из единственного игрока, то

2 v{i)-v{K).(6.3)

В качестве аддитивной можно упомянуть характеристическую функцию из примера 2 п. 2.2.

6.2.Удобный признак аддитивности (супераддитивной) характеристической функции V дается следующей теоремой.

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

2 v(i)-v{I).(6.4)

Доказательство. Необходимость написанного равенства из аддитивности функции вытекает автоматически.

Для доказательства дастаточности возьмем произвольные не пересекающиеся коалиции К и L и напишем систему неравенств, вытекащ-щих из супераддитивности функции v (они являются частными случаями формул (1.4) и (1.7)) :

v(K) + v(L) v(KUL),

2 v(i) S и(К),

2 v(i) v(L),

2 v(i)<v{I\{KKj D),

il\{K и L)

v(KUL) + v(I\(KUL)) v(I), v(I)£ 2 v(i)

(b действительности, на основании условия теоремы в последнем соотношении имеет место знак точного равенства, но нас это в данный момент



не интересует). Обратим внимание на то, что в совокупности этих неравенств слева и справа стоят одни и те же величины. Поэтому, сложив все эти неравенства почленно, мы получим тождественное равенство. Следовательно, и каждое из складываемых соотношений является равенством, и в частности, первое из них: v(K) + v(L) =v(K UL) . □

6.3.Даже строго супераддитивная характеристическая функпия может обладать некоторыми чертами аддитивности: для некоторых конкретных коалиций К и L может выполняться равенство (6.1). В связи с этим для нас будут представлять интерес понятия, вводимые следующим определением.

Определение. Игрок / в характеристической функции v над/ назьшается существенным, если сушествует такая коалиция К, что

v(K) + v(i)<v(KUi).(6.5)

В противном случае, т.е. если для любой коачиции К CI будет

v(K)v(i) = v(KUi),(6.6)

игрок / назьшается несущественным, илиболваном*) .

Коалиция в условиях характеристической функции, содержащая всех существенных в ней игроков, назьшается носителем в этой характеристической функции.

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

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

Если L - некоторое множество несущественных игроков, содержащееся в коалиции К, то итерирование равенства (6.6) дает нам

viK) = v(K\L) 2 v(i){6.1)

i& L

В частности, если коалиция К состоит только из несущественных игроков, то v{K)= I v{i).(6.8)

6.4.Применим к существенной игре рассуждения п. 5.5. Определение. Характеристическая функция, тождественно равная

нулю, назьгоается нулевой. □

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

Доказательство. Необходимость. Пусть характеристическая функция V аффинно эквивалентна нулевой. Это значит, что найдутся такие к>0 и ai(i G /), что для любого К CI будет

kv(K)+ 2 ai = 0.(6.9)

/ G а:

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

[Старт] [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]