Множества W (1) характеризуются следующими свойствами: (49:W*)
(49:W*:a) Из двух дополнительных (в /) множеств S и --S одно и только одно принадлежит W.
(49:W*:b) W содержит все надмножества своих элементов.
(49:W*:c) W содержит / и все (п - 1)-элементные множества.
Множества L (1) характеризуются следующими свойствами:
(49:L*)
(49:L*:a) Из двух дополнительных (в /) множеств S и -S одно и только одно принадлежит L.
(49:L*:b) L содержит все подмножества своих элементов.
(49:L*:c) L содержит пустое множество и все одноэлементные множества.
Как было указано выше, мы можем строить теорию, либо опираясь на If с (49: W*), либо - на L с (49:L*).
49.6.3. Обычному способу мышления в большей мере свойственно указывать выигрывающие коалиции, а не проигрывающие; мы будем пользоваться поэтому первой из упомянутых процедур.
В связи с этим заметим, что некоторое подмножество множества W оказывается равным по важности самому W. Это - множество тех элементов S £ W, которые не имеют собственных подмножеств, принадлежащих W. Назовем такие S минимальными элементами W (т. е. Wi), а их семейство обозначим через Wm (т. е. W™).
Интуитивное значение этого понятия ясно. Введенные минимальные выигрывающие коалиции действительно являются решающими. Это - те выигрывающие коалиции, из которых ни один участник не может быть удален. (Следует вспомнить, что наше обсуждение в п. 48.1.3 началось с перечисления этих коалиций для рассматриваемой там игры.)
49.7. Решения простых игр
49.7.1. Эвристические рассмотрения, которые привели нас к понятию простых игр, делают правдоподобным то, что исследование игр, принадлежащих этой категории, может оказаться легче, чем исследование произвольных игр п лиц с нулевой суммой. Для подтверждения этого мы должны исследовать, как определяются решения в простых играх. Так как мы рассматриваем теперь старую форму теории, нужно принять во внимание п. 30.1.1 *). Начнем с замечания, что можно ожидать значительного упрощения от того факта, что в простой игре каждое множество либо заведомо необходимо, либо заведомо не необходимо (см. п. 31.1.2).
49.7.2. Для того чтобы установить это утверждение,докажем сначала:
(49:Н) В любой существенной игре Г все множества S из Wr заведомо необходимы, а все множества S из Ьт заведомо не необходимы.
г) В терминах новой формы теории, введенной в п. 44.7.2 и в последующих пунктах, это означает, что мы ищем решения для Е (0), т. е. при этом эксцессы ограничены значением 0.
Роль этого ограничения станет яснее в третьем замечании в п. 51.6.
Доказательство. Если множество 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, т. е. что мы можем допустить существование нулевых весов.