Таким образом, (48:1) и (48:2) - это выигрывающие коалиции, а (48:3) - проигрывающие.
Легко проверить, что каждое подмножество множества / - (1, 2, 3, 4) принадлежит ровно одному из этих двух классов 1).
48.2. Выигрывающие и проигрывающие коалиции
48.2.1. Рассмотрим теперь множество п игроков /= (1, 2, . . ., тг). Обобщая схему п. 48.1.3, разделим семейство всех подмножеств / на два таких класса W и L, что подмножества из W являются выигрывающими коалициями, а подмножества из L - проигрывающими. Аналоги свойств коалиций из п. 48.1.3 можно сформулировать следующим образом.
Обозначим семейство всех подмножеств / через / 2). Сопоставление каждому подмножеству S его дополнения (в /)
(48:4) S->-S
есть, очевидно, взаимно однозначное отображение / на себя. Мы можем утверждать следующее:
(48:А:а) Каждая коалиция является либо выигрывающей, либо проигрывающей, но не может быть той и другой одновременно/Это значит, что множества W и L дополняют в / друг друга.
(48:А: Ь) Взятие дополнения (в I) переводит выигрывающие коалиции в проигрывающие и наоборот, т. е, преобразование (48:4) отображает W и L друг на друга.
(48:А:с) Коалиция будет выигрывающей, если выигрывающей является какая-либо ее часть; таким образом, семейство W содержит вместе с каждой коалицией все ее надмножества.
(48:A:d) Коалиция является проигрывающей, если она есть часть проигрывающей коалиции; иными словами, L содержит вместе с каждой коалицией все ее подмножества.
48.2.2. Прежде чем обсуждать понятия выигрывающих и проигрывающих коалиций в их связи с игрой, тгроанализируем несколько более подробно структуру условий (48:А:а) - (48:A:d).
Заметим сначала, что, хотя для истолкования игры нам необходимы оба класса коалиций W и L, эти классы друг друга определяют. Это взаимное определение осуществляется даже двумя способами. Задавая класс W (или L), можно для построения другого класса использовать как (48:А:а), так и (48:А: Ь). Иными словами, отправляясь от одного из этих классов, мы получаем другой следующим образом:
Согласно (48:А:а). Возьмем данный класс как целое и найдем его дополнение в /.
Согласно (48:А:Ь). Возьмем отдельно все элементы данного класса и заменим каждый из них дополнением в / 3).
Следует заметить также, что если данное множество W (или L) обладает свойством (48:А:с) или соответственно (48:A:d), то множество,
г) (1, 2, 3, 4) имеет 24 = 16 подмножеств. Из них 8 входят в списки (48:1) и (48:2), а 8 - в (48:3).
2) Так как i содержит п элементов, i состоит из 2п элементов.
3) Читатель должен заметить удивительное свойство этого условия. Мы получаем один и тот же результат независимое того, ищем мы дополнения ко всему множеству или же отдельно к каждому его элементу.
полученное из исходного посредством (48:А:а) или (48:А:Ь), будет обладать свойством (48:А:с) или соответственно (48:A:d).
Замечание. Это действительно верно как для (48:А:а), так и для (48:А:Ь) и не зависит от того, приводят ли (48:А:а) и (48:А:Ь) к одному и тому же множеству. Точнее:
(48:В) Пусть множество М обладает свойством (48:А:с) (соответственно (48:A:d)).
Тогда оба множества, которые получены из него посредством (48:А:а) и (48:А:Ь) (мы не предполагаем их совпадения), обладают свойством (48:A:d) (или (48:А:с)).
Доказательство. Мы должны показать, что оба преобразования (48:А:а) и (48:А:Ь) переводят (48:А:с) в (48:A:d) и наоборот. Ясно, что (48:А:с) эквивалентно следующему:
(48:А:с*) Если S £ М и Т $ М, то S Т.
Аналогично (48:A:d) эквивалентно утверждению
(48:A:d*) Если S $ М и Т £ М, то S 3= Т. *
Преобразование (48:А:а) меняет ролями условия принадлежности и непринадлежности множеству М. Следовательно, оно меняет ролями (48:А:с*) и (48:A:d*). Преобразование (48:А:Ь) меняет ролями символы Си. Следовательно, оно также меняет (48:А:с*) и (48:A:d*).
Из оказанного выше следует, что мы можем построить всю структуру, рассматривая только одно из двух множеств, W или L. Мы должны только требовать, чтобы оба преобразования (48:А:а) и (48:А:Ь) приводили к одному и тому же множеству (которое будет тогда соответственно L или W) и чтобы было удовлетворено соответствующее условие (48:А:с) или (48:A:d) (оставшееся условие выполняется автоматически).
Таким образом, мы имеем только два условия, налагаемых на W или на L: во-первых, эквивалентность (48:А:а) и (48:А:Ь) и, во-вторых, (48:А:с) или (48:A:d).
Первое из этих условий означает следующее. Элементы, не принадлежащие множеству, совпадают с дополнениями (в I) элементов этого множества. Другими словами, из двух взаимно дополнительных (в I) множеств S и -S одно и только одно принадлежит W (соответственно L).
Объединяя сказанное выше, мы получим следующее.
Множества W ( I) характеризуются следующими свойствами:
(48: W)
(48: W:а) Из двух взаимно дополнительных (в I) множеств S и - S одно и только одно принадлежит W.
(48:W:b) W содержит все надмножества своих элементов.
Множества L ( /) характеризуются следующими свойствами:
(48:L)
(48:L:a) Из двух взаимно дополнительных множеств S и -S одно и только одно принадлежит L.
(48:L:b) L содержит все подмножества своих элементов. Переформулируем это еще раз.
Если для W (для L) выполняется (48:W) (соответственно (48:L)), то (48:А:а) и (48:А:Ь) дают одно и то же множество L (соответственно W). Для W и L выполняются (48:А:а) - (48:A:d), а для L (для W) выполняется (48:L) (или соответственно (48:W)). Обратно, если для W и L выполняются (48:А:а) - (48:A:d), то для них порознь выполняются (48:W) и (48:L).
§ 49. ХАРАКТЕРИЗАЦИЯ ПРОСТЫХ ИГР 49.1. Общие понятия выигрывающих и проигрывающих коалиций
49.1.1. Перейдем теперь к рассмотрению связи между выигрывающими и проигрывающими коалициями в самой игре.
Итак, предположим, что задана игра п лиц Г. Во всех последующих рассмотрениях удобно ограничиться старой теорией в смысле п. 30.1.1 или п. 42.4.1. Следовательно, как указано в п. 42.5.3, мы можем предполагать, что Г является игрой с нулевой или с постоянной суммой. В данном случае мы предпочитаем выбрать в качестве Г игры с нулевой суммой.
Кроме этого, никаких ограничений на Г не налагается и, в частности, не предполагается ее нормирование.
49.1.2. Проанализируем сначала понятие проигрывающей коалиции. Повторяя, по существу, то же, что было сказано в п. 35.1.1, можно рассуждать следующим образом1). Игрок £, когда он остается один, получает количество v ((£)). Это, очевидно, самое худшее, что может с ним произойти, так как от дальнейших потерь он может предохранить себя без чьей-либо помощи. Таким образом, мы можем считать игрока i, когда он получает v ((£)), полностью побежденным. Коалиция S может считаться побежденной, если она получает 2 v ((0) так как в этом случае каж-
дый игрок i в ней обязательно должен получить v ((£)) 2). Таким образом критерием побежденности коалиции является:
у (5) = S v((0).
В терминологии п. 31.1.4 это означает, что коалиция S линейная (см. также сноску 3 на стр. 312).
Мы получили удовлетворительное определение семейства Lr 3) всех проигрывающих (побеждаемых) коалиций.
(49:L) Ьт есть множество всех линейных множеств S (/).
Теперь легко определить выигрывающие коалиции. Естественно принять, что они противоположны проигрывающим, т. е. что система W? всех выигрывающих коалиций определяется так:
(49:W) Wr есть множество всех множеств S (/), для которых множество -S линейно.
Из общих соображений должно быть ясно (это, впрочем, немедленно проверяется с помощью пп. 27.1.1-27.1.2), что множества WV и Lv инвариантны относительно стратегической эквивалентности.
г) Различие состоит в том, что рассматриваемая здесь игра Г является более общей.
2) Так как ни один игрок i не обязан соглашаться на меньшее, чем v ((i)), и вся коалиция S имеет в сумме ((0)» это единственный способ, которым они могут про-
i£S
извести разделение.
3) Для того чтобы избежать путаницы, мы будем пользоваться обозначениями WT и LT вместо Wn L из- п. 48.2.2. Различие состоит здесь в том, что п. 48.2.2 посвящен постулированию свойств, которые кажутся желательными для понятий выигрывания и проигрывания, в то время как данный анализ определяет множества, полученные из конкретной игры Г.
Эти две точки зрения сольются в (49:Е) из п. 49.3.3.