назад Оглавление вперед


[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [ 147 ] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230] [231] [232]


147

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, но воспользоваться этой связью пока не удавалось.



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.

[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [ 147 ] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230] [231] [232]