Доказательство. Если множество S принадлежит Lr, то оно линейное и, следовательно, заведомо не необходимо в силу (31 :F) из п. 31.1.5. Если S принадлежит Wr, то -S линейное и S Ф 0 (потому что 0 принадлежит Lr и, следовательно, не принадлежит Wr)- Поэтому S заведомо необходимо в силу (31:G) из п. 31.1.5.

Мы можем теперь выполнить сформулированное выше обещание относительно простых игр; фактически это можно сделать двумя различными путями.

(49:1) В любой простой игре Г все множества S из Wr заведомо

необходимы, а все другие заведомо не необходимы.

Доказательство. Комбинируем (49:Н) с тем фактом, что в простой игре Lr является точным дополнением Wr-

(49:J) В любой простой игре Г все множества S из Wr заведомо

необходимы, а все остальные множества заведомо не необходимы х).

Доказательство. Мы можем заменить Wr из (49:1) на его подмножество W т. е. перевести все S из Wr - Wr из заведомо необходимого класса в заведомо не необходимый, используя (31:С) из п. 31.1.3. Действительно, каждое S £ W г обладает подмножеством Т G W .

Из этих двух критериев, (49:1) и (49:J), последний более полезен. Их важность выявится при фактическом нахождении решений простых игр 2). Действительно, этот анализ простых игр дает возможность самого глубокого проникновения в теорию игр со многими участниками 3).

§ 50. МАЖОРИТАРНЫЕ ИГРЫ И ГЛАВНОЕ РЕШЕНИЕ

50.1. Примеры простых игр. Мажоритарные игры

50.1.1. Прежде чем двинуться\дальше, полезно привести несколько примеров простых игр, т. е. пар W и L из (49:F). Нам известно из п. 49.6.2, что достаточно рассмотреть W, характеризуемое утверждениями (49:W*).

Рассмотрим поэтому несколько возможных способов введения таких Wy т. е. возможные определения понятия выигрывания.

Принцип мажоритарности напрашивается как один из возможных способов определения выигрывания. Естественно определить W как семейство всех таких множеств S, которые содержат большинство игроков. Следует заметить, однако, что мы при этом доляшы исключить равенство: действительно, (49:W*:a) устанавливает для этого W, что для каждого множества S либо S, либо -S должно содержать большинство игроков; таким образом, исключается, что оба множества содержат точно половину игроков. Другими словами, общее число участников должно быть нечетным.

Таким обрааом, если п нечетно, то мы можем определить W как множество всех S с числом элементов больше чем п/2 4). Простую игру б),

г) Сравнение (49:1) и (49:J) показывает, что S из WT - одновременно заведомо необходимо и заведомо не необходимо. Это - другая иллюстрация замечания в конце замечания на стр. 293.

2) См. пп. 50.5.2 и 55.2.

3) См. пп. 55.2 - 55.11 и, в частности, общие замечания в § 54.

4) Так как минимальное целое число, большее чем /г/2, есть (п + 1)/2 (п нечетно) г мы можем говорить, что S должно иметь элементов не меньше чем (п + 1)/2.

5) Точнее, класс стратегически эквивалентных игр (с п участниками).

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

Наименьшим п, для которого такая игра может быть построена г), является 3. Известно, что существует только одна существенная игра 3 лиц, и для нее W состоит из двух- и трехэлементных множеств, т. е. множеств с числом элементов, большим чем 3/2. Таким образом, мы видим:

(50:А) Единственная существенная игра трех лиц является простой; это - чисто мажоритарная игра трех участников.

Для дальнейших возможных п (т. е. п = 5, 7, ...) чисто мажоритарная игра оказывается лишь одной из многих возможностей.

50.1.2. Чисто мажоритарная игра возможна только при нечетных щ но простые игры существуют также и для четных п. Действительно, для нашего прототипа простой игры (см. пп. 48.1.2, 48.1.3) было п = 4.

Однако понятие мажоритарное легко распространяется на случай четных п. Введем для этого понятие взвешенного большинства. Пусть v каждому игроку 1, . . . , п приписан численный вес, скажем соответственно Wi, . . . , wn. Определим W как множество всех таких S, которые содержат большую часть общего веса. Это означает следующее:

(50:1) S>y2

i£S г=1

или, что то же самое,

(50:2) 2 wt> 2 wt.

i£S i£-s

Мы должны снова позаботиться об исключении ничейного случая. Однако благодаря большей общности нашего данного построения лучше непосредственно перейти к полному рассмотрению (49:W*).

50.1.3. Рассмотрим, следовательно, какие ограничения накладывает (49:W*) на числа wi9 . . . , wn.

(49:W*:a). Так как мы можем выразить принадлежность S к W посредством неравенства (50:2), множество -S будет принадлежать W, если

(50:3) 2 т< 2 Щ.

Итак, (49:W*: а) означает, что выполняется одно и только одно из двух соотношений (50:2) и (50:3). Это означает, очевидно, что никогда не выполняется

(50:4) 2= 2 т

i£S i£-S

или, в эквивалентной форме, что никогда не выполняется

(50:5) 3>i=t2 Wi-

i£S i=l

(49:W*:b). Используя определение W в форме (50:1), мы видим, что это условие выполняется, если все wt 0 2).

х) То есть число, которое нечетно и для которого игра может быть существенной. 2) Это, конечно, вполне правдоподобное условие. Удивительно здесь то, что мы не требуем, чтобы wt >> 0, т. е. что мы можем допустить существование нулевых весов.

(49:W*:c). Снова используя (50:1), мы видим, что /=(1,2, . . . , п) принадлеяшт W. Для произвольного п - 1-элементного множества S = = I - (i0) условие (50:1) означает, что

п i=l

Суммируя сказанное выше, мы получаем (50:В) Веса wu ..., wn могут использоваться в (50:1) или (50:2)

для задания W, удовлетворяющего (49:W*), тогда и только тогда,

когда выполняются следующие условия: (50:В:а) Для всех i0 = 1, . .., п

п г=1

<50:В;Ь) Для всех SI

1 V Л

Ziwi=YZiWi

i£S i=l

Иными словами, игрок всегда имеет неотрицательный вес, который никогда не достигает половины общего веса и не превосходит ее; никакая комбинация игроков не обладает точно половиной общего веса 1).

Простую игру, которая получена на основе такого W 2), будем называть взвешенной мажоритарной игрой (п участников с весами Wi, . . . . . . , wn). Мы будем также обозначать эту игру символом [wi, . . . , wn].

Таким образом, чисто мажоритарной игре приписывается символ

[1, 1].

Следует заметить, что игра четырех лиц, соответствующая вершине / куба Q, которая рассматривалась в пп. 48.1.2 и 48.1.3, может быть описана как взвешенная мажоритарная игра. Действительно, принцип выигрывания, найденный в п. 48.1.3, может быть выражен тем, что игрокам 1, 2, 3 придается один и тот же вес, а игроку 4 двойной вес. Это значит, что такой игре следует приписать символ [1, 1, 1, 2].

50.2. Однородность

50.2.1. Введение мажоритарных игр и описывающих их символов [iVi, . . ., wn] является известным шагом в направлении количественной (числовой) классификации и характеризации простых игр. Есть все основания думать, что полное осуществление такой программы было бы желательным. Простота была определена в комбинаторных, теоретико-множественных терминах, и следует ожидать, что числовая характеризация облегчит обращение с ними. Такая характеризация обычно облегчает более исчерпывающее, количественное понимание рассматриваемого понятия. Кроме того, в стоящей перед нами проблеме мы в конце концов ищем решения, которые определяются численно, и поэтому представляется вероятным, что числовая характеризация будет соответствовать им более прямо, чем комбинаторная.

2) Первое требование устраняет трудности из п. 49.2, второе - исключает равенство.

2) Точнее, класс стратегически эквивалентных игр.