§ 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 (проведенное выше доказательство действительно привело к ней) мы рассматривали только чистые стратегии, но не смешанные. Другими словами, все эти игры двух лиц оказались вполне определенными.
Это, однако, не имеет отношения к той цели, которую мы сейчас преследуем