совпадают с теми, которые не являются заведомо проигрывающими, и они образуют множество 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 во избежание потери общности или строгости.

50.7. Интерпретация полученного результата

50.7.1. Результат (50: J) позволяет сформулировать обещанное в п. 50.5.1 словесное утверждение. Эта формулировка такова.

Решение V находится путем выбора произвольного множества U тех минимальных выигрывающих коалиций (т. е. U Wm), которые рассматриваются как прибыльные. Числа xt должны удовлетворять соответствующим уравнениям (50:8*). Однако после этого мы должны проверить, что некоторые другие коалиции заведомо неприбыльны в смысле (50:9*). Это требуется не только для тех коалиций, которые известны как выигрывающие (т. е. W), но и для всех тех, про которые нельзя сказать, что они определенно проигрывают одной из коалиций из U (т. е. U+), исключая, конечно, коалиции из самого U 1).

Читатель может теперь судить, оправдывается ли этой формулировкой заключительное замечание п. 50.1.1.

50.7.2. Вопрос о нахождении надлежащего U для (50:1) довольно деликатный. Здесь дает себя чувствовать антимонотонность U+ (см. (50:Н:Ь) из п. 50.5.3). Уменьшение U, т. е. числа уравнений, увеличивает U+, т. е. число неравенств, и наоборот.

В частности, если мы выберем U максимально возможным, т. е. возьмем U = Wm, то неравенства, связанные с С/+, не создают трудностей вообще. Действительно, U = Wm влечет U+ = W в силу (50:Н:а) из п. 50.5.3. Любое Т из W определенно обладает таким подмножеством 5, которое минимально в W, т. е. принадлежит U ~ Wm. Если Т отличается от этого S не только безразличными элементами, то xt > 0 для некоторых i из Т - S и, следовательно, 2 xt > 2 xi ~ п-> т- е- неравенство

(50:9*) выполнено.

Таким образом, U = Wm всегда дает решение V, если равенства (50:8*) (вместе с (50:7)) могут быть решены.

Однако, как мы выяснили в п. 50.4.3, мы не имеем права ожидать априори, что так будет всегда, и, в частности, в том случае, когда уравнений (50:8*) (т. е. элементов Wm) больше, чем переменных xt.

Последнее возражение не является абсолютным; в действительности легко найти простую игру, в которой число этих уравнений превосходит число переменных, а решение тем не менее существует 2). С другой стороны, существуют простые игры, для которых эти уравнения не имеют решения. Пример этого несколько менее тривиален 3), но возможно, что это явление довольно общее. Когда оно имеет место, надлежит исследовать, нельзя ли найти решение V подходящим выбором U a Wm. Трудность и тонкость этого вопроса комментировались уже в начале этого пункта 4).

г) А также те коалиции, которые отличаются от них только безразличными элементами.

2) В первый раз это окажется в случае п = 5, см. пятое замечание в п. 53.1.

3) В первый раз это окажется в случае п = 6, см. пятое замечание в п. 53.2.5.

4) Не известно никаких примеров простых игр с решением V, выведенным из U С Wm, но не установлено также, что их нет. Возникающий далее вопрос о том, обладает ли каждая простая игра решением V, соответствующим некоторому U с Wm, остается также открытым.

Проблема представляется довольно важной. Решение может оказаться трудным. Представляется, что эта проблема имеет некоторое сходство с решенными вопросами, упомянутыми в замечании на стр. 177-178, но воспользоваться этой связью пока не удавалось.