Доказательство. То, что 3 доминируется некоторым элементом из V, т. е. некоторым ат, где Т £ U, означает, что (50:12) выполняется для некоторого Т £ U. Это равносильно тому, что - R ф) £ U*, т. е. что R (Р) $ U+.
Следовательно, R (Р) принадлежит U+ тогда и только тогда, когда
Р не доминируется никаким элементом из V.
50.5.3. Прежде чем перейти к дальнейшему, рассмотрим четыре простых свойства множества U+ из (50: G).
(50:Н:а) U* = U+=.W, если U = Wm.
Доказательство. Предположим, что U = Wm. Тогда U* состоит из тех множеств, которые содержат подмножества, принадлежащие Wm, т. е. минимальные выигрывающие подмножества. Следовательно, U* = W. Операция, которая приводит в (50: G) от U* к U+, является комбинацией преобразований (48:А:а) и (48:А:Ь) из п. 48.2.1. Мы уже тогда заметили, что, когда эти два преобразования применяются к W, они компенсируют друг друга. Следовательно, U* = W дает U+ = W.
(50:H:b) U* - монотонная, a U+ - антимонотонная операция. Иными словами, из Ui U2 следует U* U* и з U%.
Доказательство. Достаточно вспомнить определения из (50:6), чтобы увидеть, что Ut U2 влечет Щ s Щ, а это в свою очередь влечет U* 3 Ui.
(50:Н:с) Для всех наших U Wm выполняется U* W U+.
Доказательство. Комбинируем (50:Н:а) и (50:Н:Ь) (подставляя U, Wm вместо ии U2).
(50:H:d) U* и U+ содержат все надмножества своих элементов.
Доказательство. Для Z7* это очевидно. Рассматриваемое свойство эквивалентно сформулированному в (48:А:с) из п. 48.2.1. (Берем W вместо U*, U+.) Далее, операция, которая приводит в (50: G) от С/* к U+, является комбинацией преобразований (48:А:а) и (48:А:Ь) из п. 48.2.1 (см. доказательство (50:Н:а)). Применение (48:В) из п. 48.2.2 к этим двум преобразованиям показывает, что рассматриваемое свойство сохраняется при переходе от U* к U+.
50.5.4. Заметим, что U* и U+ допускают простую словесную интерпретацию. Если мы знаем о принадлежащих U коалициях только то, что они выигрывающие, то о каких коалициях можно сказать, что они заведомо выигрывающие, а о каких, - что они не являются заведомо проигрывающими?
Первыми являются такие коалиции, которые имеют подмножества, принадлежащие U, т. е. коалиции из U*. Заведомо проигрывающими будут дополнения к ним, т. е. коалиции, не принадлежащие U+. Следовательно, U* есть множество первых упомянутых коалиций, a U+ - множество вторых.
Теперь смысл утверждений (50:Н:а) - (50:Н:с) становится ясным. Для U = Wm все очевидно. Заведомо выигрывающие коалиции в точности
совпадают с теми, которые не являются заведомо проигрывающими, и они образуют множество W. По мере того как U убывает, пробел между этими множествами коалиций расширяется. Первое множество убывает как подмножество W, а второе возрастает как надмножество W. Утверждение (50:H:d) в равной степени правдоподобно.
50.6. Переформулирование полученного результата
50.6.1. Утверждение (50.G) из п. 50.5.2 позволяет нам установить следующее:
(50:1) V является решением в том и только в том случае, если R (Р)
принадлежит U+ тогда и только тогда, когда Р принадлежит V.
Итак, нам только остается решить, когда выполняется (50:1). С этой
-> ->
целью рассмотрим R £ U+ и определим р, для которого R (Р) = R. Рассмотрим три возможности:
(50:13) S (-1) + 2 (-l+*i) = 0,
т. е.
(50:14) 2
-> ->
Если существует Р, для которого R (Р) = R, то мы имеем (50:15) 0= 2 Pi2 (-1) + 2 +
г=1 i$R i£R
т. е. имеем в (50:13) и (50:14) знак 5g. Поэтому > в (50:13), (50:14) исклю-
-* ->
чает существование какого-либо Р с R (Р) = R. Поэтому впредь можно не рассматривать множества R из С/+ с > в (50:13) и (50:14). Рассмотрим с другой стороны i? g С/+ с < в (50:13) и (50:14). Тогда существует беско-
-> 71
нечно много способов выбора Р с 2 Р* = 0 и
Г -1, если
г = \ - 1+хь если i£R.
Для всех них должно быть R (Р) з i?. Следовательно, они принадлежат
V в силу (50:H:d). Так как множество V конечно, эти р не могут все принадлежать V. Мы получили противоречие. Оно означает, что множества R (= U+ с < в (50:13) и (50:14) не могут существовать.
50.6.2. Остается рассмотреть множества из которые имеют
в (50:13) и (50:14) знак =. Согласно сказанному выше, эти множества
->
должны представлять в точности р £ V.
Если Р 6 V, т. е. если р = аг, где Т g U, то мы имеем следующую
->
ситуацию: R (Р) есть Т плюс множество тех £, для которых xt = 0. Т принадлежит С/ 9= U* <== С/4" (второе включение следует из (50:Н:с)); следовательно, R (Р) принадлежит С/+. Также
2 xi ~ 2 xi=п-
Итак, мы имеем в (50:13) и (50:14) знак =. Следовательно, все р из V удовлетворяют этому условию.
Обратно. Рассмотрим R 6 U+ с = в (50:13), (50:14). Добавление к R всех тех г, для которых xt = 0, не влияет ни на факт принадлежности R к U+ (по 50:H:d), ни на равенство (50:14). Поэтому мы можем предполагать, что R содержит все эти i.
Если теперь для дележа Р имеет место R (Р) = R, то pf -1 + хь
для i 6 Но всегда pf - 1. Так как 2 Р* = 0» эт0 влечет
-1, если iR,
(50:16) fo = j
l + a;*, если
Наоборот, из (50:16) следует, что Р является дележом, для которого
R (Р) = R. Следовательно, наше требование в этом случае состоит в том,
-> ->
что р из (50:16) должно быть некоторым аг, где Т £ U. Это означает, что Т и R различаются только элементами i, для которых xt = 0. Это свойство нечувствительно по отношению к нашей начальной модификации i?, к включению всех таких i в R.
Подведем итоги.
(50:J) Для того чтобы V было решением, необходимо и достаточно,
чтобы выполнялось следующее.
Назовем игрока i безразличным, если xi = 01). Тогда мы имеем
(50:8*) 2 *i = n
для множеств Т из U и также для всех тех множеств, которые отличаются от них только безразличными элементами. Кроме того, мы должны потребовать
(50:9*) 2 Xi>n
для, всех остальных Т из U+. При использовании этого результата нужно сначала выбрать множество U Wm, затем попытаться определить xt из (50:8*) и, наконец, проверить, удовлетворяют ли эти х% неравенствам
(50:7) xtO
и (50:9*).
х) Эти i вносят некоторое усложнение, которое в дальнейшем усугубляется тем фактом, что мы не располагаем примерами игр, в которых они действительно присутствовали бы. Может оказаться, что они никогда не существуют; безразличный игрок i характерен тем, что он принадлежит некоторой минимальной выигрывающей коалиции, но никогда не получает доли в выигрыше.
В такой ситуации находится исключенный игрок в дискриминирующем решении игры трех лиц (см. (32:А) в п. 32.2.3 с с = 1). Но там решение было бесконечным множеством, тогда как наше V должно быть конечным.
Было бы интересным решить этот существенный вопрос; во всяком случае, мы должны здесь предусмотреть существование безразличных i во избежание потери общности или строгости.