(31: В) S является заведомо необходимым для данного дележа а (а £ V), если оно заведомо необходимо (и рассматривается)

-* -У

для такого другого дележа a (а £ V), что (31:1) aiat для всех i£S.

Объяснение. Можно не рассматривать какую-то коалицию, если существует другая коалиция, которая имеет тех же самых участников и обещает каждому из них (индивидуально) не меньше, чем первая.

Доказательство. Пусть дележи аир удовлетворяют главному условию: at > pf для всех i £ S. Тогда, на основании (31:1), а и Р также удовлетворяют ему: а\ > pj для всех i £ S. Так как S и а заданы, установлено, таким образом, что р доминируется каким-то элементом из V, и не представляется необходимым рассматривать S и а.

(31:С) S является заведомо не необходимым, если другое множество

Т S заведомо необходимо (и рассматривается).

Объяснение. Можно не рассматривать коалицию, если ее часть уже определенно должна рассматриваться.

Доказательство. Пусть дележи а (а £ V) и р удовлетворяют главному условию для S; тогда они, очевидно, будут удовлетворять ему

и для Т S. Поскольку Г и а рассматриваются, они, таким образом, устанавливают, что р доминируется каким-то элементом из V, и не является необходимым рассматривать S и а.

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

Для произвольного множества S = (&i, . . ., кр) воспользуемся (25:5) из п. 25.4.1 при £i = (ki), . . ., Sp - (кр). Тогда мы получим

v(S)v((kJ)+...+v((kp)),

т. е.

(31:2) v(5)Sv((&)).

fees

Избыток левой части в (31:2) над правой выражает полное преимущество (для всех участников вместе), присущее образованию коалиции S. Назовем это свойство выпуклостью множества S. Если это преимущество исчезает, т. е. если

(31:3) v(S)=2v((ft))t

fees

то множество S назовем линейным.

Непосредственно получаем несколько утверждений.

(31 :D) Следующие множества всегда линейны:

(31:D:a) Пустое множество.

(31:D:b) Любое одноэлементное множество.

(31:D:c) Любое подмножество линейного множества.

(31 :Е) Любое из следующих утверждений равносильно несущественности игры:

(31:Е:а) Множество / = (1, ... , п) является линейным.

(31:Е:Ь) Существует такое множество S, что оба множества S и -S линейны.

(31:Е:с) Любое множество S линейное.

Доказательство утверждений (31:D:a) и (31:D:b). Для этих множеств (31:3) очевидно.

Утверждение (31:D:c). Пусть 5д Ги множество Т линейное. Положим R = Т - S. Тогда на основании (31:2)

<31:4) v (5)2= 2 v ((*)),

fees

<31:5) у(Д)2т((й)).

Поскольку множество Т линейное, то по (30:3) получаем (31:6) v(r)=2v((*)).

Так как S П R = 0, то S [} R = Г; поэтому

v(S)+v(i?)<v(T), 2 v((fc)) + 2 v((*)) = 2 v((ft)).

Следовательно, (31:6) влечет

<31:7) v(S) + v(R) S v((*))+ Ev((*)).

feis fee#

Теперь сравнение (31:4), (31:5) и (31:7) показывает, что мы должны иметь в них во всех равенство. Но равенство в (31:4) означает как раз линейность S.

Утверждение (31:Е:а). Это утверждение совпадает с (27:В) из п. 27.4.1.

Утверждение (31:Е:с). Это утверждение совпадает с (27:С) из п. 27.4.2.

Утверждение (31:Е:Ь). Для несущественной игры это верно при любом S на основании (31:Е:с). Обратно, если это верно для S (хотя ы для одного), то

v(S)=2v((fc)), v(-£) = 2v((ft));

fees fes

следовательно, суммируя (используем (25:3:b) из п. 25.3.1), получаем

0= 2 v((*)),

fe=l

т. е. игра является несущественной на основании (31:Е:а) или (27:В) из п. 27.4.1.

31.1.5. Теперь мы можем доказать следующее:

(31 :F) S является заведомо не необходимым, если оно линейное.

Объяснение. Не нужно рассматривать коалицию, если игра не допускает полного преимущества (для всех ее участников вместе) по сравнению с тем, что они получили бы сами по себе, как независимые игроки *).

*) Отметим, что это связано с критерием (31 :А), но вовсе не тождественно с ним! В самом деле, (31:А) имеет дело с щ, т. е. с обещаниями, сделанными для каждого участника индивидуально. (31 :F) имеет дело с функцией v(S) (которая определяет линейность), т. е. с возможностями игры для всех участников вместе. Но оба критерия согласуют свои утверждения с v((i)), т. е. с тем, что каждый игрок индивидуально может получить сам по себе.

Доказательство. Если а е- р для некоторого S, то необходимо S Ф 0, > Pi Для всех i £ S и Р* v((0); следовательно, af > v((i)). Таким образом, 2 a* > 2 v((0)- Так как S линейно, это

означает, что 2 a* > (*У). Но S должно быть эффективным: 2 а* = 5g v(iS), и мы получаем противоречие.

(31 :G) S является заведомо необходимым, если - S линейно

и S ф 0.

Объяснение. Коалиция должна рассматриваться, если она не пуста и противостоит коалиции вида, описанного в (31 :F).

Доказательство. Предварительные условия выполнены для всех дележей.

Проверяем (30:4:а). S Ф 0 по условию.

Проверяем (30:4:Ь). Всегда аг > v((z)), так что 2 at = 2 v((0)-

i$S i$S

Поскольку 2 аг = 0, левая часть равна - 2 at- Так как -S линейног

i=l i£S

то правая часть равна v (-S), т. е. (используем (25:3:Ь) из п. 25:3:1) равна -v (S). Итак, - 2 аг = v (£)> 2 аг v (£)> т. е. S эффективно-Из (31 :F) и (31 :G) получим, в частности:

(31 :Н) /7-элементное множество является заведомо необходимымг если р = п - 1, и заведомо не необходимым, если р = О, 1, ?г.

Объяснение. Коалиция обязательно должна рассматриваться, если она имеет только одного противника. Коалицию не нужно рассматривать, если она пуста или состоит только (!) из одного игрока или если она не имеет противников.

Доказательство, Пусть р = п - 1. Множество -S имеет только один элемент; следовательно, оно линейное по (31 :D). Утверждение следует теперь из (31 :G).

Пусть р = О, 1. Утверждение получается непосредственно из (31 :D) и (31:F).

Пусть р = п. В этом случае S = / = (1, . . ., п), что делает главное условие невыполнимым. В самом деле, получается > Pj для всех j = l, . . . , п, и, следовательно,

г=1 г=1

Но так как а и Р суть дележи, обе части обращаются в нуль, и мы получаем противоречие.

Таким образом, те р, для которых необходимость S сомнительнаг ограничены случаем р Ф О, 1, п - 1, п, т. е. интервалом

(31:8) 2рп-2.

Этот интервал играет некоторую роль только при п 4. Обсуждаемая ситуация сходна с ситуацией в конце п. 27,5.2 и в п. 27.5.3, причем еще раз выявляется исключительная простота случая п = 3.