50.8. Связь с однородными мажоритарными играми

50.8.1. Ограничимся теперь случаем U = Wm. Это значит, что мы предполагаем, что полная система уравнений

(50:17) 2 х{: - п для всех S £ Wm

может быть решена вместе с неравенствами (50:7) xt0.

Мы видим, что в этом случае множество V всех as, где S £ Wm, является решением. В этом и только в этом случае мы будем называть V главным простым решением игры.

Имеется определенное сходство между этими ограничениями и ограничениями, которые характеризуют однородную взвешенную мажоритарную игру. Действительно, последняя определяется через

(50:18) 2 wi = Ъ для всех S £ Wm,

Ъ = \{ 21т + а), а>0

(объединение (50:D) и (50:Е) из п. 50.2), и (50:19) WiO.

На самом деле здесь мы имеем дело с большим, чем простое сходство. Так, если дана система wt, удовлетворяющая соотношениям (50:18) и (50:19), то система, удовлетворяющая (50:17) и (50:7), получается следующим образом.

Число Ъ из (50:18) положительно. Умножение всех wt на общий положительный множитель оставляет все без изменения, и, выбрав в качестве множителя п/b, мы можем заменить в (50:18) Ъ на п. Теперь мы можем просто положить xt = wt, и соотношения (50:18), (50:19) перейдут в (50:17), (50:7).

Если, наоборот, дана система х(, удовлетворяющая (50:17), (50:7), то здесь возникает дополнительная трудность. Мы можем положить wt = хг *). Тогда (50:7) перейдет в (50:19), а (50:17) даст (50:18) с Ъ - п,

т. е. а = 2п - 2 wi- Но теперь возникает вопрос, будет ли удовлетворять-

ся условие а > 0, т. е. будет ли

(50:20) 2 х% < 2га.

Суммируя сказанное выше, мы получаем:

(50:К) Каждая однородная взвешенная мажоритарная игра обла-

дает главным простым решением.

*) Те i, которые не принадлежат никакой выигрывающей коалиции, производят легкое искажение, так как они не имеют никакого х% (см. второе ограничение в п. 50.4), в то время как мы требуем, чтобы они равнялись wt. Однако, как легко заключить из сноски 2 на стр. 446, мы можем положить соответствующие Wi = 0.

Обратно, если (простая) игра обладает главным простым решением, то однородные веба для нее можно получить из этого решения тогда и только тогда, когда выполнено (50:20).

50.8.2. Найденная связь между однородными весами и главным простым решением существенна. Однако следует подчеркнуть, что однородная взвешенная мажоритарная игра, вообще говоря, имеет, кроме главного простого решения *), и другие решения. Кроме того, игра с главным простым решением может не удовлетворять неравенству (50:20), т. е. может не быть знака < в

(50:21) 22гс2).

Наконец, при этом мы не должны терять из поля зрения основного ограничения всех наших рассуждений. Рассматриваем ли мы понятие обычного дележа в его узком смысле из п. 50.8.1 (т. е. U = Wm) или в более широкой первоначальной форме из пп. 50.6, 50.7.1 (т. е. U Wm, см. (50:1) из п. 50.6.2), оно по определению ограничивается простыми играми. То, что необходимо выходить за их пределы, равно как и за пределы описанных здесь частных решений, и что это заставит нас решительно вернуться к систематической теории из п. 30.1.1, было указано в конце п. 50.3.

§ 51. МЕТОДЫ ПЕРЕЧИСЛЕНИЯ ВСЕХ ПРОСТЫХ ИГР 51.1. Предварительные замечания

51.1.1. Начиная с п. 50.1.1, мы вводили конкретные простые игры, которые допускали характеризацию с помощью числового критерия вместо первоначального теоретико-множественного (см. начало п. 50.2.1). Мы видели, однако, что эти численные процедуры можно было осуществлять различными способами и что не было уверенности в том, что все простые игры можно перечислить с их помощью. Следовательно, желательно найти комбинаторные (теоретико-множественные) методы, которые дадут систематическое перечисление всех простых игр.

Это действительно необходимо для того, чтобы обозреть возможности простых игр и, в частности, увидеть, насколько продвинули нас рассмотренные численные процедуры. Окажется, что имеющие решающее значение примеры неочевидных возможностей появляются только при относительно большом числе игроков 3), так что чисто словесный анализ не может быть достаточно эффективным.

51.1.2. Мы указывали в конце п. 49.6.3, что перечисление всех простых игр эквивалентно перечислению их семейств W, т. е. всех семейств

*) Главное простое решение существенной игры трех лиц ([1, 1.1], см. конец п. 50.2) есть первоначальное решение из п. 29.1.2, т. е. (32:В) из п. 32.2.3. О сущест- * вовании других решений мы знаем из пп. 32.2.3 и 33.1.

Главное простое решение вершины / куба Q ([1, 1, 1, 2], см. конец п. 50.2) есть первоначальное решение из п. 35.1.3. Мы обсудим эту игру вместе с более общей игрой [1, . . ., 1, п - 2]h (п участников) в п. 55 и получим все решения.

Все эти ссылки делают ясным то, что решения, отличные от главного простого, весьма важны (см. пп. 33.1 и 54.1).

2) Знак = в первый раз встречается в случае п = 6, см. четвертое замечание в п. 53.2.4. Знак > в первый раз встречается в случае п = б или 7, см. шестое замечание в п. 53.2.6.

3) п = б, 7, см. п. 53.2.

ТУ, которые удовлетворяют (49: ТУ*) из п. 49.6.2. Мы также заметили там, что, возможно, полезно заменить рассмотрение ТУ (всех выигрывающих коалиций) рассмотрением Wm (всех минимальных выигрывающих коалиций).

Каждая из этих процедур обеспечивает перечисление всех простых игр. Использование W предпочтительнее с идейной точки зрения, так как ТУ имеет более простое определение, a ТУт вводится с помощью W. Для практического перечисления всех простых игр, что в данный момент является нашей целью, использование ТУ предпочтительнее, так как Wm меньше, чем ТУ1), и, следовательно, описывается более просто.

Мы последовательно опишем обе эти процедуры. Окажется, что их обсуждения дадут естественное применение понятий удовлетворяемо-сти и насыщения, введенных в п. 30.3.

51.2. Метод насыщения. Перечисление посредством W

51.2.1. Множество Охарактеризуется свойствами (49:ТУ*) из п. 49.6.2, т. е. условиями (49:W*:a) - (49:W*:c), которые и составляют (49:W*).

Отбросим пока (49:W*:c) и рассмотрим только (49:W*:a) и (49:W*:b). Из этих двух условий следует, что никакие два элемента из ТУ не могут быть непересекающимися 2). Другими словами, если обозначить отрицание дизъюнктности, т. е. S п Тф 0> через SMiT, то из (49:W*:a) и (49:W*:b) следует -удовлетворяемость3). Более исчерпывающим утверждением в этом направлении является следующее:

(51:A) (49:W*:a), (49:W*:b) эквивалентны -насыщенности.

Доказательство, -насыщенность ТУ означает следующее:

(51:1) S принадлежит ТУ тогда и только тогда, когда S п Т Ф 0

для всех Т из ТУ.

Из (49:W*:a) и (49:W*:b) следует (51:1). Действительно, пусть ТУ удовлетворяет (49:W*:a) и (49:W*:b). Если S принадлежит ТУ, то мы знаем, что S п Т ф 0 для всех Т из ТУ. Если S не принадлежит ТУ, то тогда Т = - S принадлежит ТУ, по (49:W*:a), и S[\T = 0.

Из (51:1) следует (49:W*:a) и (49:W*:b). Действительно, пусть ТУ удовлетворяет (51:1). Докажем сначала (49:W*:b), а затем (49:W*:a).

(49:W*:b). Если S удовлетворяет критерию (51:1), то это верно и для каждого надмножества S. Следовательно, ТУ содержит все надмножества своих элементов.

(49:W*:a). Благодаря доказанному выше -S не принадлежит ТУ тогда и только тогда, когда никакое подмножество -S не принадлежит ТУ, т. е. когда любое Г из ТУ не содержится в -S или, что то же самое, когда для любого Т из ТУ 8{\Тф 0. По (51:1) это означает просто, что S принадлежит ТУ.

Таким образом, во всех случаях ровно одно из S и -S принадлежит ТУ.

г) Семейства множеств W и L не пересекаются. Они имеют одинаковое число элементов в силу (48:А:Ь) из п. 48.2.1. Вместе они исчерпывают 7, которое содержит 2п элементов. Следовательно, W, так же как и £, содержит ровно 2n 1 элементов.

Число элементов в Wm может быть различным, но всегда значительно меньше (см. четвертое замечание в п. 53.1).

2) Доказательство. Пусть S, Т принадлежат W л S[\T - 0. Тогда -S 3 Т и, следовательно, -S принадлежит W по (49:W*:b), таким образом, нарушается (49: W*: а).

3) См. определения в п. 30.3.2.