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


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


70

Пусть в результате выбора игроками / G / их стратегий л:,- сложилась ситуация JC = (хь . . ., х). Коалицию К будем называть замкнутой в ситуации X, если для любого игрока / G К будет / Ux/ = К (т.е. если каждый игрок из К обращается о вступлении в коалицию ко всем остальным игрокам из А и только к ним; заметим, что стратегии-предложения игроков, не принадлежащих К, при этом не принимаются во внимание, даже если они хотят обьединиться с коалицией К).

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

Обозначим через А/(х) замкнутую в х коалицию, содержащую игрока /, или же самого игрока /, если он является в х изолированным, и положим

v(Ki(x)) \Ki(x)\

Соотношения (3.3) и (3.4) определяют некоторую бескоалиционную игру Г вида (3.2). Покажем, что эта игра является искомой. Обозначив через Vp ее характеристическую функцию, возьмем произвольную коалицию К CI и покажем, что (К) = v(K).

Если К = ф, то, очевидно, (К) = 0 =v(K).

Предположим поэтому, что К Ф ф. Пусть каждый игрок / G К выбирает свою стратегию Х/* = K\i. Составим из индивидуальных стратегий х * (i G К) коалиционную стратегию коалиции К, которую обозначим через х. Возьмем также произвольную стратегию Х/\/ коалиции 1\К. В ситуаций (х, Х/\д:) коалиция К, очевидно, является замкнутой. Общий ее вьшгрыш согласно (3.4) будет равен

2 ЯДх,х,\)= Z --=v(K).(3.5)

i Е: кi Е: к \ к \

с другой стороны, стоящая здесь слева сумма является вьшгрышем игрока 1 в ситуации (x]c,xfJ) в антагонистической игре Г/-, т.е. fKiKi Xi\K- Кроме того, этот вьшгрыш не зависит от стратегии X/\j. Значит,

v(K)=Hk(x*k,x}\j)= min Hjc(x*,Xj\j)

< max min Я/ (xj , x\ ) =•(3.6)

Обратимся теперь к дополнительной коалиции 1\К. Рассмотрим, как и выше, коалиционную стратегию Xjj, состоящую из индивидуальных стратегий X* = (I\K)\i для каждого игрока / G 1\К, и произвольную коалиционную стратегию Xj коалиции К. Пусть (х), р = 1, . .. г, - все замкнутые коалиции (за исключением 1\К) и все изолированные игроки в ситуации X. Тогда, как и при вьшоде формулы (3.5), мы имеем

I ЯДх.х;.)= к v(Kp(x))v(Kl

iE кр =1



Вместе с тем. как и при выводе формулы (3.6), мы получаем v(K) = Нк (хк, x*sj) = max Я (х л: )

> min msix Hj(xk,Xj\j) = Vy (К).(3.7)

Неравенства (3.6) и (3.7) дают нам viK) = Vy{K), □

3.2.Доказанная теорема имеет принципиальное значение. Во-первых, из нее следует, что теорию абстрактных характеристических

функций можно интерпретировать как теорию характеристических функций бескоалиционных игр.

Во-вторых, эта теорема вместе с утверждениями п. 1.5 и 1.6 означает своего рода "структурную замкнутость" системы из двух свойств характеристической функции - персональности и супераддитивности. Определяемая этими двумя свойствами теория реализуется единственным образом как результат систематического использования принципа максимина в бескоалиционных играх.

3.3.В одном важном частном случае теорему п. 3.1 о реализуемости можно уточнить.

Теорема. Если характеристическая функция v вида (3.1) обладает помимо свойств персональности и супераддитивности еще и свойством дополнительности, то существует бескоалиционная игра Г вида (3.3) с

постоянной суммой, для которой Vy ~ V.

Доказательство этого утверждения является модификацией доказательства теоремы п. 3.1. Как и раньше, множества стратегий игроков х- определяются соотношением (3.3). Это дает нам основание ввести хшя каждой ситуащи конструируемой игры Г понятия замкнутой в этой сит>а-ции коалиции и изолированного игрока. Если Ki(x) - замкнутая в х коалиция, содержащая игрока / (или сам этот игрок, если он является изолированным) , то положим для любого Z Е/

v(Kiix))1 /viKjix)) \

\Ki(x)\ п \j = i \Kj(x)\ J

Здесь, как видно из непосредственного подсчета, Z Я/ (х) = v(I), так что

построенная бескоалиционная игра Г является игрой с постоянной суммой. Ясно также, что Z Я(х) = Vy(r), Из последних двух равенств следует, что

vy(r) = v(l).(3.8)

Для доказательства того, что Vr = v, поступим так же, как и в доказательстве теоремы п. 3.1. Взяв коалицию К С/, положив х* =K\i для любого i Е К и приняв Xf для / Е 1\К произвольным, мы получаем аналоги равенств (3.5) и (3.6), из чего следует, что

v(K)Vy(K).(3.9)

Применяя те же рассуждения к коалиции 1\К, мы получаем

v(I\K)VyiI\K).(3.10)



Сложение неравенств (3.9) и (3.10) дает нам

v(K) + v(I\K) S Vr (Ю + Vr(I\lC}.(3.11)

Но слева здесь стоит по условию дополнительности d(/), а справа - в силу постоянства суммы игры Г - число VyQ) . Поэтому и ввиду (3.8) в соотношении (3.11) имеет место точное равенство. Но тогда (3.9) и (3.10) также должны бьпь равенствами, и v(K) = Vy(K). □

§ 4. ЛИНЕЙНАЯ СТРУКТУРА МНОЖЕСТВА ВСЕХ ХАРАКТЕРИСТИЧЕСКИХ ФУНКЦИЙ

4.1.В линейном пространстве всех вещественньгк функций на множестве 2 множество(/) всех характеристических функций над / (т.е. функций, обладаюшдх свойствами супераддитивности и персональности) имеет определенное строение.

Теорема. В пространстве всех вещественных функций на I (где I / I = п) множество 2(1) является выпуклым конусом, размерность которого не превосходит 2 - 1.

Доказательство того, что 2(7) является вьшуклым конусом, следует из того, что умножение супераддитивной функции на положительное вещественное число и сложение двух таких функций не вьюодит за пределы класса супераддитивных функций. Замкнутость же класса всех персональ-HbDC функций относительно этих двух операций тривиальна.

Для оценки размерности 2{1) достаточно заметить, что все вообще вещественные функции над / образуют линейное пространство размерности 2 При этом все характеристические функции удовлетворяют условию персональности и(ф) = О, которое является нетривиальным линейным соотношением. □

Из теоремы п. 4.3 будет следовать, что размерность множества равна 2" - 1.

4.2.Для указания базиса в множестве введем следующие понятия, которые представляют и самостоятельный теоретико-игровой интерес.

Определение. Характеристическая функция i; называется простой, если она пршшмает лишь два значею1я: О и 1. Если характеристическая функция V простая, то коалиции К, для которьис v(K) = 1, назьшаются выигрывающими, а коалиции К, для которых v{K) = О,-проигрывающими.

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

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

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

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