Действительно, если R принадлежит ТУ, то S R тоже принадлежит ТУ. Обратно, пусть S принадлежит ТУ. Тогда в ТУ существует минимальное Т <=: S. Так как Т принадлежит И7771, каждое i £ Т принадлежит /0. Следовательно, Т е 10. Таким образом, Т е S[}I0 = R и, следовательно, R принадлежит W вместе с 7 .

(51:17) Т принадлежит L.

Действительно, заменим S на Т I - 10). Это заменит наши R и Т на 0 и Т. Так как 0 принадлежит L, (51.16) позволяет заключить то же самое и о Г.

Докажем теперь, что

(51:18) у(5) = у(Л) + у(Г).

Рассмотрим отдельно случаи, когда S £ L и когда 5 £ ТУ.

Пусть S (i L. Тогда Л, Т <=l S также принадлежат L. Следовательно,

v (S) = 2 v ((j)) + S v ((0) = v (Д) + v (Г),

т. е. мы получаем (51:18).

Пусть S £ ТУ. По (51:16) и (51:17) должно быть R £ ТУ, а Т g L. Поэтому

v(5)=-Sv((0),

v(Д) = - 2 v((0) = - 2v О)-2 v о),

у(Г) = 2 v((0),

откуда

y(S) = v(R)+v(T),

т. е. (51:18).

(51:18) есть просто утверждение о том, что 10 есть разлагающее множество. Для всех Т1 - 10 (51:17) дает

v(f) = Sv((0).

Поэтому (7 - /0)-компонента Н несущественна. Следовательно, по (51:J) /0-компонента А должна быть простой. Таким образом, доказательство завершено.

51.7.2. Теперь мы в состоянии полностью описать разложимость простой игры Г, т. е. можем указать разлагающее разбиение Пг в смысле п. 43.3.

(51 :N) При тех же предположениях, что и в (51 :М), элементами разлагающего разбиения Пг являются 10 и одноэлементные множества (i) для всех i £ I - 10.

Доказательство. Все (i), где i £ I - /0, принадлежат Пг.

По (51 :М) I - 10 есть разлагающее множество, образующее несущественную компоненту Н. Поэтому каждое (i) (i £ I - /0) есть разлагающее множество для Н (на основании, например, (43:J) из п. 43.4.1), а поэтому и для Г (на основании (43:D) из п. 43.3.1). Будучи одноэлементным множеством, (г),неизбежно минимально. Поэтому оно принадлежит Пг,

30 Дж. Нейман, О. Моргенштерн

10 принадлежит Пг. Io есть разлагающее множество по (51 :М). Если / есть разлагающее множество 0, то (51 :L) применимо к / или к I-J. Поэтому либо / з 70, либо I - J з I0, I0(]J = 0. Оба случая исключают / cz 10. Таким образом, 10 минимально. Поэтому оно принадлежит Пг.

Никакие другие / не принадлежат Пг. Любое другое / из Пг должно не пересекаться с 10 и со всеми (i) (i £ I - 10) (на основании (43:F) из 43.3.2). Так как объединение этих множеств есть 7, должно быть / = 0; но 0 не может быть элементом Пг (см. начало п. 43.3.2).

Таким образом, доказательство завершено.

51.7.3. Комбинация (43:К) из п. 43.4.1 и (51 :N) г) дает следующее.

(51:0) Простая игра Г неразложима тогда и только тогда, когда Io = /, т. е. когда все ее участники значимы.

В заключение докажем следующее утверждение:

(51 :Р) Простая игра обладает ровно одной /-компонентой, которая проста и неразложима. При этом / = 10.

Доказательство. /0-компонента может быть образована, и она проста по (51 :М).

Рассмотрим теперь простую /-компоненту. Тогда она имеет, по (51 :К), то же самое Wm и те же самые значимые элементы, что и Г. Таким образом, множество ее значимых элементов есть 1 0, но, по (51:0), неразложимость / компоненты эквивалентна / = /0.

Назовем /0-компоненту А0 игры Г ее ядром. Все остальные участники игры, т. е. элементы множества / - /0, суть болваны . (См. (51 :М) или (51 :N) и последнюю часть п. 43.4.2). Поэтому все, что происходит в игре Г, осуществляется в ее ядре Д0. Чтобы увидеть это, достаточно применить первое замечание из п. 51.6.

§ 52. ПРОСТЫЕ ИГРЫ ДЛЯ НЕБОЛЬШИХ ЗНАЧЕНИЙ П

52.1. Случаи п = 1, 2 интереса не представляют.

Описание случая п = 3

52.1. Нашей дальнейшей-целью является перечисление всех простых игр для небольших значений п. Мы предполагаем проводить этот казуистический анализ до тех пор, пока это необходимо для получения примеров, упомянутых в п. 51.2 (см. сноску 2 на стр. 444), в п. 50.7.2 (см. сноски 2, 3, 4 на стр. 452) и в п. 50.8.2 (см. сноски 1,2 на стр. 454).

Так как каждая простая игра существенна, мы должны рассматривать игры при пЗ.

Для п = 3 ситуация следующая. Единственная существенная игра трех лиц проста и описывается символом [1, 1, 1] 2).

Таким образом, начиная отсюда, мы можем предполагать, что п 4.

52.2. Процедура для п7>:4. Двухэлементные множества и их роль в классификации Wm

52.2.1. Пусть дано п 4. Мы хотим перечислить все простые игры при данном п. Для того чтобы сделать это, удобно ввести принцип дальнейшей классификации этих игр, который §есьма эффективен для небольших значений п.

1) Или более прямо (43:К) из п. 43.4.1 с (51:L), (51:М). 2) См. (50:А) в п. 50.1.1 и последнее замечание в п. 50.2.2.

Интересующее нас перечисление равнозначно перечислению множеств И7771, для которых мы располагаем различными характеризациями, например характеризацией (51 :G) из п. 51.4.1.

Рассмотрим минимальные множества, которые могут принадлежать W . Так как (51:G:d) исключает из Wm пустое множество и одноэлементные множества, это означает рассмотрение двухэлементных множеств в Wm. Эти множества обладают следующим свойством.

(52:А) Двухэлементное множество принадлежит W 1 тогда и только тогда, когда оно принадлежит W1).

Доказательство. То, что из первого следует второе, очевидно. Для доказательства обратного предположим, что двухэлементное множество S принадлежит W. Собственными подмножествами S являются пустое, а также одноэлементные множества. Ни одно из них не принадлежит W. Поэтому S принадлежит Wm.

Мы предполагаем производить классификацию по двухэлементным множествам, содержащимся в Wm.

52.2.2. Можно себе представить, что Wm вовсе не содержит двухэлементных множеств. Обозначим эту возможность символом С0.

Следующей альтернативой является то, что Wm содержит ровно одно двухэлементное множество. Некоторой перестановкой игроков 1, 2, . . ., п мы можем добиться того, чтобы это множество было множеством (1,2). Обозначим эту возможность символом CV

Далее, Wm может содержать два или более двухэлементных множеств. Рассмотрим два из них. По (51:G:a) они должны иметь общий элемент. Некоторой перестановкой игроков 1, . . ., п мы можем добиться того, чтобы общим элементом было 1, а оставшимися элементами этих множеств 2 и 3.

Итак, W содержит (1, 2) и (1,3).

Обозначим возможность, при которой Wm не содержит иных двухэлементных множеств, символом С2-

52.2.3. Предположим теперь, что Wm содержит другие двухэлементные множества. Предположим, кроме того, что не все из них содержат 1.

Рассмотрим поэтому двухэлементное множество, не содержащее 1. По (51:G:a) оно должно содержать общие с (1, 2) и с (1,3) элементы. Так как 1 исключается, это множество должно быть (2,3).

Таким образом (1,2), (1,3) и (2,3) принадлежат Wm (мы имеем здесь полную симметрию относительно 1, 2, 3).

Рассмотрим теперь какое-либо другое двухэлементное множество из Wm. Оно не может содержать все три элемента 1, 2, 3. Некоторой перестановкой этих игроков мы можем добиться того, чтобы это множество не содержало 1. Но оно должно иметь общие элементы с (1, 2) и с (1, 3), а так как 1 исключается, оно должно быть множеством (2, 3). Но мы предполагали, что оно отлично от (2,3).

Таким образом, Wm содержит двухэлементные множества (1,2)% (1,3), (2,3) и никаких иных. Обозначим эту возможность символом С*..

52.2.4. Остается альтернатива, что Wm содержит другие двухэлементные множества, кроме (1,2), (1,3), но что все они содержат 1.

Некоторой перестановкой игроков 4, . . п мы можем дать соответствующим игрокам номера 4, . . ., к + 1, где к = 3, . . ., п - 1

) То есть неминимальное множество в W должно иметь хотя бы три элемента.,