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


[Старт] [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] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230] [231] [232]


84

§ 26]

ИГРА С ЗАДАННОЙ ХАРАКТЕРИСТИЧЕСКОЙ ФУНКЦИЕЙ

(25:6) для /?= 3 со знаком означает v (S) + v (Т) + v (- (S[) T))0 (обозначаем St и Sz соответственно через S, Т; тогда множеством £3 является -(S (J Г)), т. е.

-v(-(S[)T))v(S) + v(T).

На основании (25:3:Ь) мы получаем v (S [} Т) t v (S) + v (Г), т. е. <25:3:с).

Итак, наши утверждения в точности эквивалентны конъюнкции свойств (25:3:а) - (25:3:с).

§ 26. ПОСТРОЕНИЕ ИГРЫ С ЗАДАННОЙ ХАРАКТЕРИСТИЧЕСКОЙ

ФУНКЦИЕЙ

26.1. Построение

26.1.1. Докажем теперь утверждение, обратное тому, которое было установлено в п. 25.3.1. Именно, для всякой числовой функции множеств у(5), удовлетворяющей условиям (25:3:а) - (25:3:с), существует игра п лиц с нулевой суммой Г, для которой эта функция y(S) является характеристической.

Во избежание недоразумений удобнее обозначить данную числовую функцию, удовлетворяющую условиям (25:3:а) - (25:3:с), через v0 (S). Мы определим с ее помощью некоторую игру п лиц с нулевой суммой Г и обозначим ее характеристическую функцию через v (S). Тогда нужно будет доказать, что v (S) === v0 (S).

Итак, пусть дана числовая функция множеств v0 (S), удовлетворяющая условиям (25:3:а) - (25:3:с). Определим игру п лиц с нулевой суммой Г следующим образом х).

Каждый игрок к = 1, 2, . . ., п, делая ход, выбирает подмножество Sk cz /, содержащее к. Каждый игрок делает свой выбор независимо от выборов других игроков 2). После этого платежи, которые должны быть сделаны, определяются следующим образом.

Назовем кольцом 3>4) любое множество игроков S, для которого

(26:1) Sb = S при каждом

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

х) Эта игра Г является, по существу, более общим аналогом простой мажоритарной игры трех лиц, определенной в п. 21.1. Мы будем сопровождать последующее изложение комментариями, раскрывающими детали этой аналогии.

2) Множество /, состоящее из п элементов, имеет 2п~1 подмножеств £, содержащих к, которые можно пронумеровать индексами х (S) = 1,2, . . ., 2п~1. Если теперь игрок к выбирает вместо множества Sh свой индекс xk = xh (Sk) = 1,2, . . ., 2n-1, то игра приобретает нормальную форму, как в п. 11.2.3. Очевидно, все §к = 2п~1.

3) Кольца являются аналогами пар в п. 21.1; поэтому здесь применима сноска 2 €0 стр. 243; в частности, кольца являются формальным понятием из множества правил игры, ведущим к коалициям, которые влияют на фактическое течение всякой партии.

4) Другими словами, кольцо - это такое множество игроков, в котором каждый игрок выбирает как раз это множество. Аналогия с определением пары в п. 21.1 очевидна. Различия вызваны формальными соображениями: в п. 21.1 каждый игрок должен назвать другой элемент желаемой пары; теперь же мы пред полагаем, что он указывает все кольцо. Более подробный анализ этого отличия был бы достаточно легким, но в нем не видно необходимости.

5) Доказательство: пусть S и Т - два кольца с общим элементом к; тогда на основании (26:1) = S и = Г, и, следовательно, S - Т.



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

Рассмотрим теперь игрока к. Он принадлежит одному из этих множеств Ci, . . ., Ср, скажем Cq. Тогда игрок к получает сумму

(26:2) J Vo(Ce) i2 Md)1)- •

q T=l

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

26.1.2. Доказательство того, что построенная игра является игрой с нулевой суммой. Рассмотрим одно из множеств Cq. Каждый из nq игроков этого множества получает один и тот же выигрыш, выражаемый формулой (26:2). Следовательно, игроки из Cq получают вместе-

(26:3) Vo(Cg) 2 Уо(Сх).

Чтобы найти полную величину выигрыша, которую получают все игроки 1, . . ., п, нужно просуммировать выражение (26:3) по всем множествам Cq, т. е. по всем q = 1, . . ., р. Эта сумма, очевидно, равна

2 *o(Cq)- Sv0(CT),

т. е. нулю 2).

Доказательство того, что характеристической функцией игры является v0 (S). Обозначим характеристическую функцию игры Г через v (S). Напомним, что условия (25:3:а) - (25:3:с) для v(S) выполняются, так как эта функция является характеристической, а для v0 (S) - по предположению. Поэтому условия (25:4) - (25:6) также выполняются для каждой из функций v(S) и v0 (S).

Докажем сначала, что

(26:4) v (S) v0 (S) для всех подмножеств Sczl.

Если S пусто, то обе стороны неравенства равны нулю на основании свойства (25:3:а), поэтому можно предполагать, что S не пусто. В этом случае-коалиция всех игроков к £ S может влиять на выборы множеств Sk щк, чтобы наверняка сделать S кольцом. Для этого достаточно каждому к G S* выбрать Sk = S. Что бы ни делали другие игроки (из - S), S будет, следовательно, одним из множеств (колец или сольных множеств)

г) Течение партии, т. е. выборы Si4 . . ., Sn или, в смысле сноски 2 на стр. 263., выборы т1? . . ., тд, определяют множества Cj, . . ., Cpj а следовательно, и выражение (26:2). Конечно, функция (26:2) совпадает с функцией $bk (т4, . . ., хп) из общей теории.



Ci, . . Ср, скажем Cq. Таким образом, каждый игрок к £ Cq = S получает выигрыш (26:2); следовательно, вся коалиция S получает (26:3). Далее, мы знаем, что система множеств

Ci, ...» Ср

является разложением множества /; поэтому на основании (25:6),

2 vo (Сх) 0. Другими словами, выражение (26:3) оказывается

v0 (Cq) = v0 (S) 2). Иначе говоря, игроки, принадлежащие коалиции S, могут обеспечить себе по меньшей мере выигрыш v0 (S) независимо оттого, что делают игроки из -S. Это означает, что v (S) v0 (S), т. е. (26:4).

Теперь мы можем установить требуемую формулу (26:5) v(S)=v0(S).

Применим (26:4) к -S. Согласно свойству (25:3:Ь) это означает -v (S) £г -v0 (S), т. е.

(26:6) v(S)v0(S).

(26:4) и (26:6) вместе дают (26:5) 2).

26.2. Резюме

26.2. Сформулируем кратко полученные результаты. В пп. 25.3- 26.1 мы получили полное математическое описание характеристических функций y(S) всех возможных игр п лиц с нулевой суммой Г. Если мы покажем, что предположение, высказанное в п. 25.2.1, верно, т. е. если мы окажемся в силах построить всю теорию игр на основе глобальных свойств коалиций, выраженных функцией v(S), то наша характеризации функции v(S) представит собой точную математическую основу всей теории. Следовательно, характеризация функции v(S) и функциональные соотношения (25:3:а) - (25:3:с) имеют особую важность.

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

§ 27. СТРАТЕГИЧЕСКАЯ ЭКВИВАЛЕНТНОСТЬ. НЕСУЩЕСТВЕННЫЕ И СУЩЕСТВЕННЫЕ ИГРЫ

27.1. Стратегическая эквивалентность. Редуцированная форма

27.1.1. Рассмотрим игру п лиц с нулевой суммой Г с характеристической функцией v (S). Пусть задана также система чисел а\, . . . , а%. • Образуем тогда новую игру Г, которая согласуется с игрой Г во всем,, кроме следующего: Г играется точно так же, как и Г, но когда она закан-

г) Отметим, что выражение (26:3), т. е. полный выигрыш, полученный коалицией S, не определяется выборами игроков только из S. Но мы установили для нее нижнюю границу v0 (S), которая определена.

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

Это, однако, не имеет отношения к той цели, которую мы сейчас преследуем

[Старт] [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] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230] [231] [232]