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


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


71

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

Очевидно, определение простейшей характеристической функции Vj можно записать в виде

f 1, если KDR, Vr(K)=(4.1)

I О, в противном случае.

4.3.Число различньгх простейших характеристических функций над / равно числу непустых подмножеств в/, т.е. 2" - 1.

Теорема. Все 2" - 1 простейших характеристических функций над I линейно независимы в совокупности.

Доказательство. Выясним, какими могут быть коэффициенты в тождестве

Z \r Vr (К) = о при любом К С I.(4.2)

r с i r Ф ф

Будем проводить следующее индуктивное рассуждение. Возьмем некоторую непустую коалицию А С/ и предположим, что для любой коалиции L СК, отличной от К, должно быть =0.

Согласно (4.1) в равенстве (4.2) можно оставить лишь те слагаемью, для которых R СК. При этом для jR ФК no предположенному должно быть Xj = 0. Но тогда (4.2) превратится в равенство XfviK) = О. Поэтому из к(К)- следует Xj =0, и индуктивный переход обоснован.

Таким образом, в тождестве (4.2) все коэффициенты должны обращаться в нуль. О

4.4.Из установленной в предыдущем пункте линейной независимости всех простейших характеристических функций в линейном пространстве, натянутом на множество ?(/), и из совпадеш1я их числа с размерностью этого пространства (см. п. 2.1) следует, во-первых, что размерность конуса (/) всех характеристических функций над / равна 2 - 1, а, во-вторых, что каждую характеристическую функцию над / можно представить, и притом единственным образом, в виде линейной комбинации простейших характеристических функций над /.

4.5*. Теорема. Имеет место представление

v= 2 Xr{v)vj,(4.3)

r ci

Xj,(v)- 2 (~1)-Ца).(4.4)

к cr

Доказательство. Подставим в (4.3) вместо Х/ (v) правую часть равенства (4.4). Для любо го ГС / мы получим

v(T)= 2 ( 2 (-l)-i;(/:))i;(r).

rci kcr

Очевидно, здесь отличны от нуля только те слагаемые, для которых У? С Г;



но для этих слагаемых i; (7 = 1. Поэтому v(T)= 2 S (-l)-i;(A),

R с Т KCR

ИЛИ, изменяя порядок суммирования,

v(T)= 2 ( 2 (-i)-)i;(A)

KCR KCRCT XX

(крестиками помечены переменные множества, по которым производится суммирование). Объединяя во внутренней сумме все слагаемые с одинаковым числом игроков в коалиции R, мы получаем

v(T)= 2(22 (-l)-)i;(A),

KCR r = \K\ \R\=r KCRCT

a так как r-элементное множество R, содержащее данное А (-элементное множество К, можно из данного Г -элементного множества Т выбрать

ровно с I I I I способами,

v(T)= 2 ( 2 (-1)-с,7, ,).(Ю.

КСТ г=\К\

Вьщеляя слагаемое, соответствующее К = Т, мы, пользуясь формулой бинома, получаем

v{T) = v{r)+ 2 (1 -l)-i;(A) = i;(r), КС т КФТ

и справедливость представления (4.3) доказана. □

4.6. В характеристической функции с п игроками наложение условий

дополнительности равносильно наложению- \ линейно независимых

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

2" ~ -мерным вьшуюхым конусом.

§ 5. ОСНОВНЫЕ СООТНОШЕНИЯ МЕЖДУ ХАРАКТЕРИСТИЧЕСКИМИ ФУНКЦИЯМИ

5.1. Между характеристическими функциями, как и между другими теоретико-игровыми объектами, имеют место естественные соотношения аффинной эквивалентности и изоморфности.

Определение. Две характеристические функции

V Hv(5.1)

над одним и тем же множеством игроков / назьюаются {однородно) аффинно эквивалентными, если существует такое /: > О и такие вещественные ai (i G /), что для любой коалиции КС!

v\K)=kv(K)-\- 2 ai.(5.2)



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

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

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

Теорема п. 1.9 по существу утверждает, что аффинно эквивалентные бескоалиционные игры имеют аффинно эквивалентные характеристические функции.

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

1.Рефлексивность. Каждая характеристическая функция аффинно эквивалентна самой себе: v -v.

Действительно, достаточно в (5.2) положить /: = 1, а все - равными нулю.

2.Симметрия. Если v - v\ то v v.

В самом деле, пусть имеет место (5.2). Решив это уравнение относительно v(K), мы получим

v(K)=-vXK) 2 у-, kiK к

и остается заметить, что 1/А: > 0.

3.Транзитивность! Если v v и v" d, то v" yyv.

Для доказательства запишем вместе с условием аффинной эквивалентности v nv условия аффинной эквивалентности v" и v\

v"(K) = kv(K)+ i: ai

Подставляя сюда выражение для v из (5.2), получаем v"{K)-kkv{K) Z {aikat),

где, очевидно, кк>0.

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

*) Иногда аффинная эквивалентность характеристических функций назьшается их стратегической эквивалентностью. Последний термин представляется неудачным, так как уже сам переход к характеристическим функциям сопровождается полным исключением из рассмотрения стратегического аспекта.

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