49.3.2. Утверждение (49:2) определяет v (S) для S из W и L, поэтому нам остается определить ее значения только для тех S, которые не принадлежат ни одному из этих множеств. Попытаемся приписать им всем значение 0. Согласно этому мы полагаем:
{п - д, если S£W, ) s является g-элементным множеством. - д, если S£L J ff = 0, 1, тг,
0 в остальных случаях1).
Мы докажем сначала, что v (S) есть характеристическая функция, т. е. что она удовлетворяет соотношениям (25:3:а) - (25:3:с) из п. 25.3.1. Мы докажем эти условия в их эквивалентной форме (25:А) из п. 25.4.2.
Случай р = 1 со знаком =. v (I) = 0, так как, в силу (48:А:Ь) и (49:С), / = - 0 принадлежит W.
Случай р = 2 со знаком =. v (St) + v (S2) = 0> если Si и S2 - дополнительные множества. Действительно, если оба St и S2 не принадлежат W или L, то v (Si) = v (S2) = 0. Если одно из St и S2 принадлежит W или L, то, в силу (48:А:Ь), другое принадлежит соответственно L или W. Предположим по симметрии, что St £ L, S2 6 W, Пусть St имеет q элементов; тогда S2 имеет п - q элементов. Но тогда v (St) = - q и v (S2) = g. Итак, в любом случае v (St) + v (S2) = 0.
Случай p = 3 со знаком v (St) + v (S2) + v (S3) 0, где Si9 S2i S3 попарно не пересекаются, и объединение их равно I. Действительно, если ни одно из множеств St, S2, S3 не принадлежит W, то v (St), v (S2)i v (з) = 0 2)- Если одно из S S2, S3 принадлежит W, то мы можем по симметрии предполагать, что это S3. Следовательно, - S3 = St U 2 принадлежит L в силу (48:A:b), a St и S2 принадлежат L в силу (48:A:d). Пусть St имеет д4 элементов, 2 имеет д2 элементов, a S3 имеет п - д4 - д2 элементов. Тогда v (St) = - gi, v (iS2) = - g2, v ()5з) = q± + дг- Итак, в любом случае v + v (S2) + v (S3) 0.
49.3.3. Таким образом, v (S) соответствует игре Г. Установим теперь оставшиеся утверждения.
Характеристическая функция v (S) (т. е. игра Г) нормирована, и у= = 1. Действительно, все v ((i)) == - 1.
v (S) удовлетворяет (49:2). Вследствие (48:А:Ь) и того, что v ( - S) = = - v (S), обе части (49:2) переходят друг в друга при замене S на - S. Рассмотрим поэтому только вторую половину утверждения.
Если S £ L, то ясно, что v (S) = - g. Если S не принадлежит L, то из v (S) = - g следует, что - g = 0 3), т. е. q = 0. Но это означает, что S является пустым множеством в противоречии с (49:С).
Итак, игра Г обладает всеми требуемыми свойствами.
Мы в состоянии теперь доказать следующее исчерпывающее утверждение:
(49:Е) Для того чтобы два семейства W и L были семействами Wr и Ьг для соответствующей игры Г, необходимо и достаточно выполнения следующих требований: Если игра Г несущественна, то W = L =±= I. Если игра Г существенна, то выполняются (48:А:Ь) - (48:A:d), (49:с), (49:1:а).
х) Первые два условия непротиворечивы ввиду (49:1:а).
2) Ясно, что v (S) 0, если S § W.
3) Так как п - q Ф -q, S не может принадлежать W; следовательно, v (S) = 0.
Доказательство в случае, когда игра Г несущественна, непосредственно следует из (49:В:Ь).
Пусть игра Г существенна. Необходимость была установлена в (49:А), (49:В:а) и (49:С). Достаточность вытекает из произведенного построения.
В заключение упомянем другую интерпретацию (49:2). Вспомним неравенства (27:7) из п. 27:2 (описываемые также на рис. 30), которые определяют ограничения, налагаемые на v (S). Оказывается, что W? есть множество тех S, для которых v (S) достигает верхнего предельного значения, а - множество тех 5, для которых v (S) достигает нижнего предельного значения.
49.4. Точное определение простоты
49.4. (49:Е) позволяет нам дать строгое определение того класса игр, который мы упомянули в пп. 48.1.2 и 48.2.1 и который был описан более детально в п. 49.1.3. Речь идет о том классе игр, где единственной целью всех игроков является образование определенных решающих коалиций и где нет никаких других мотивов, которые входят в количественное описание игры.
При комбинировании той части (49:Е), которая относится к существенным играм, с (49:1) оказывается, что формальным выражением этой идеи является
(49:1:Ь) Wr [j LT = 7.
Действительно, это условие выражает то, что любая данная коалиция S принадлежит либо к выигрывающей, либо к проигрывающей категории, без какого-либо дальнейшего подразделения.
В соответствии с этим введем определение: существенная игра, которая удовлетворяет (41:1:Ь), называется простой.
Понятие простоты инвариантно относительно стратегической эквивалентности, поскольку таковыми являются Wr и LT.
49.5. Некоторые элементарные свойства простоты
49.5.1. Прежде чем заняться детальным математическим исследованием введенного понятия, рассмотрим еще раз заключительное замечание из п. 49.3. Смысл этого замечания состоит в том, что существенные игры - простые, если значения v (S) лежат для каждого S на границе *) области, определенной неравенствами (27:7) из п. 27.2.
Множество всех существенных игр п лиц (нормированных; у = 1) может быть представлено как геометрическая фигура, размерность которой видна из табл. 24. Говоря более точно, соответствующие неравенства определяют выпуклую многогранную область Qn в линейном пространстве соответствующей размерности, и точки этой области описывают все такие игры 2).
49.5.2. Например, для п = 3 размерность равна 0 и область Q3 есть единственная точка.
г) Эта граница состоит из двух точек: верхнего предельного значения п - р и нижнего предельного значения -р (у = 1). v (S) должно быть одним из этих двух значений, безразлично каким.
2) Читатель, который знаком с гс-мерной линейной геометрией, заметит, что так как множество Qn определяется линейными неравенствами, оно должно быть многогранником. Рассуждения из п. 27.6 позволяют заключить, что этот многогранник выпуклый.
Для п = 4 размерность равна 3 и областью является куб Q из п. 34.2.2.
Простыми играми являются те игры, для которых мы находимся на границе каждого определяющего неравенства. Относительно выпуклой многогранной области Qn это означает, что простые игры соответствуют вершинам Qn, лг = 3, 4.
Например, для п = 3 множество Q3 состоит из единственной точки, т. е. ничего, кроме вершины, в нем нет; поэтому существенная игра трех лиц простая 1). Для п = 4 множество (?4 есть куб Q, и простым играм соответствуют его вершины I-VIII 2).
49.6. Простые игры и их W и X. Минимальные выигрывающие коалиции Wm
49.6.1. Комбинируя (49:Е) с определением простоты, мы получаем следующее.
(49:F) Для того чтобы два данных семейства W и L были множе-
ствами Wr и Lr для некоторой соответствующей игры Г, необходимо и достаточно выполнения следующих условий: (48:А:а) - (48:A:d), (49:С).
То, что S из (49:2) пробегает все подмножества /, является определяющим для простоты. Поэтому для простых игр и только для них знание Wr и Lv позволяет определить v (S) при условии, что игра нормирована и у = 1. Без последнего условия это определяет игру с точностью до стратегической эквивалентности.
Переформулируем сказанное:
(49: G) Игра Г определяется своими Wr и Lr с точностью до стратегической эквивалентности тогда и только тогда, когда она простая.
Поэтому, согласно (49:F) и (49:G), теория простых игр эквивалентна теории тех пар семейств W и L, которые удовлетворяют (48:А:а) - (48:A:d), (49:С).
49.6.2. При изучении описанных выше пар W и L следует вспомнить п. 48.2.2 и, в частности, (48:W) и (48:L), а также (49:2). Согласно этим условиям, для того чтобы определить пару W и L, достаточно указать либо W, либо L.
Условия (48:А:а) - (48:A:d) заменяются тогда на (48:W), если используется W, или на (48:L), если используется L.
Условие (49:С) непосредственно относится к L. Можно отнести его и к W, применив (48:А:Ь); при этом упомянутые в нем множества следует заменить их дополнениями.
Ради полноты мы переформулируем (48:W) и (48:L) вместе с соответствующими формами (49:С).
х) См. также (50:А) из п. 50.1.1.
2) Поскольку дело касается вершин /, v, vi, vii, это неудивительно. Наше рассуждение началось с них в п. 48.1, и наше понятие простоты было получено из них посредством обобщения.
Появление вершин , 77/, iv, viii может даже озадачить. Мы исследовали в п. 35.2 соответствующие игры как прототипы разложимости. Однако они также простые, как это будет следовать из (50:А) и начала п. 51.6.