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


[Старт] [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]


143

Множества W (1) характеризуются следующими свойствами: (49:W*)

(49:W*:a) Из двух дополнительных (в /) множеств S и --S одно и только одно принадлежит W.

(49:W*:b) W содержит все надмножества своих элементов.

(49:W*:c) W содержит / и все (п - 1)-элементные множества.

Множества L (1) характеризуются следующими свойствами:

(49:L*)

(49:L*:a) Из двух дополнительных (в /) множеств S и -S одно и только одно принадлежит L.

(49:L*:b) L содержит все подмножества своих элементов.

(49:L*:c) L содержит пустое множество и все одноэлементные множества.

Как было указано выше, мы можем строить теорию, либо опираясь на If с (49: W*), либо - на L с (49:L*).

49.6.3. Обычному способу мышления в большей мере свойственно указывать выигрывающие коалиции, а не проигрывающие; мы будем пользоваться поэтому первой из упомянутых процедур.

В связи с этим заметим, что некоторое подмножество множества W оказывается равным по важности самому W. Это - множество тех элементов S £ W, которые не имеют собственных подмножеств, принадлежащих W. Назовем такие S минимальными элементами W (т. е. Wi), а их семейство обозначим через Wm (т. е. W™).

Интуитивное значение этого понятия ясно. Введенные минимальные выигрывающие коалиции действительно являются решающими. Это - те выигрывающие коалиции, из которых ни один участник не может быть удален. (Следует вспомнить, что наше обсуждение в п. 48.1.3 началось с перечисления этих коалиций для рассматриваемой там игры.)

49.7. Решения простых игр

49.7.1. Эвристические рассмотрения, которые привели нас к понятию простых игр, делают правдоподобным то, что исследование игр, принадлежащих этой категории, может оказаться легче, чем исследование произвольных игр п лиц с нулевой суммой. Для подтверждения этого мы должны исследовать, как определяются решения в простых играх. Так как мы рассматриваем теперь старую форму теории, нужно принять во внимание п. 30.1.1 *). Начнем с замечания, что можно ожидать значительного упрощения от того факта, что в простой игре каждое множество либо заведомо необходимо, либо заведомо не необходимо (см. п. 31.1.2).

49.7.2. Для того чтобы установить это утверждение,докажем сначала:

(49:Н) В любой существенной игре Г все множества S из Wr заведомо необходимы, а все множества S из Ьт заведомо не необходимы.

г) В терминах новой формы теории, введенной в п. 44.7.2 и в последующих пунктах, это означает, что мы ищем решения для Е (0), т. е. при этом эксцессы ограничены значением 0.

Роль этого ограничения станет яснее в третьем замечании в п. 51.6.



Доказательство. Если множество S принадлежит Lr, то оно линейное и, следовательно, заведомо не необходимо в силу (31 :F) из п. 31.1.5. Если S принадлежит Wr, то -S линейное и S Ф 0 (потому что 0 принадлежит Lr и, следовательно, не принадлежит Wr)- Поэтому S заведомо необходимо в силу (31:G) из п. 31.1.5.

Мы можем теперь выполнить сформулированное выше обещание относительно простых игр; фактически это можно сделать двумя различными путями.

(49:1) В любой простой игре Г все множества S из Wr заведомо

необходимы, а все другие заведомо не необходимы.

Доказательство. Комбинируем (49:Н) с тем фактом, что в простой игре Lr является точным дополнением Wr-

(49:J) В любой простой игре Г все множества S из Wr заведомо

необходимы, а все остальные множества заведомо не необходимы х).

Доказательство. Мы можем заменить Wr из (49:1) на его подмножество W™ » т. е. перевести все S из Wr - Wr из заведомо необходимого класса в заведомо не необходимый, используя (31:С) из п. 31.1.3. Действительно, каждое S £ W г обладает подмножеством Т G W™.

Из этих двух критериев, (49:1) и (49:J), последний более полезен. Их важность выявится при фактическом нахождении решений простых игр 2). Действительно, этот анализ простых игр дает возможность самого глубокого проникновения в теорию игр со многими участниками 3).

§ 50. МАЖОРИТАРНЫЕ ИГРЫ И ГЛАВНОЕ РЕШЕНИЕ

50.1. Примеры простых игр. Мажоритарные игры

50.1.1. Прежде чем двинуться\дальше, полезно привести несколько примеров простых игр, т. е. пар W и L из (49:F). Нам известно из п. 49.6.2, что достаточно рассмотреть W, характеризуемое утверждениями (49:W*).

Рассмотрим поэтому несколько возможных способов введения таких Wy т. е. возможные определения понятия выигрывания.

Принцип мажоритарности напрашивается как один из возможных способов определения выигрывания. Естественно определить W как семейство всех таких множеств S, которые содержат большинство игроков. Следует заметить, однако, что мы при этом доляшы исключить равенство: действительно, (49:W*:a) устанавливает для этого W, что для каждого множества S либо S, либо -S должно содержать большинство игроков; таким образом, исключается, что оба множества содержат точно половину игроков. Другими словами, общее число участников должно быть нечетным.

Таким обрааом, если п нечетно, то мы можем определить W как множество всех S с числом элементов больше чем п/2 4). Простую игру б),

г) Сравнение (49:1) и (49:J) показывает, что S из WT - одновременно заведомо необходимо и заведомо не необходимо. Это - другая иллюстрация замечания в конце замечания на стр. 293.

2) См. пп. 50.5.2 и 55.2.

3) См. пп. 55.2 - 55.11 и, в частности, общие замечания в § 54.

4) Так как минимальное целое число, большее чем /г/2, есть (п + 1)/2 (п нечетно) г мы можем говорить, что S должно иметь элементов не меньше чем (п + 1)/2.

5) Точнее, класс стратегически эквивалентных игр (с п участниками).



которая таким образом получается, будем называть чисто мажоритарной игрой.

Наименьшим п, для которого такая игра может быть построена г), является 3. Известно, что существует только одна существенная игра 3 лиц, и для нее W состоит из двух- и трехэлементных множеств, т. е. множеств с числом элементов, большим чем 3/2. Таким образом, мы видим:

(50:А) Единственная существенная игра трех лиц является простой; это - чисто мажоритарная игра трех участников.

Для дальнейших возможных п (т. е. п = 5, 7, ...) чисто мажоритарная игра оказывается лишь одной из многих возможностей.

50.1.2. Чисто мажоритарная игра возможна только при нечетных щ но простые игры существуют также и для четных п. Действительно, для нашего прототипа простой игры (см. пп. 48.1.2, 48.1.3) было п = 4.

Однако понятие мажоритарное™ легко распространяется на случай четных п. Введем для этого понятие взвешенного большинства. Пусть v каждому игроку 1, . . . , п приписан численный вес, скажем соответственно Wi, . . . , wn. Определим W как множество всех таких S, которые содержат большую часть общего веса. Это означает следующее:

(50:1) S>y2

i£S г=1

или, что то же самое,

(50:2) 2 wt> 2 wt.

i£S i£-s

Мы должны снова позаботиться об исключении ничейного случая. Однако благодаря большей общности нашего данного построения лучше непосредственно перейти к полному рассмотрению (49:W*).

50.1.3. Рассмотрим, следовательно, какие ограничения накладывает (49:W*) на числа wi9 . . . , wn.

(49:W*:a). Так как мы можем выразить принадлежность S к W посредством неравенства (50:2), множество -S будет принадлежать W, если

(50:3) 2 т< 2 Щ.

Итак, (49:W*: а) означает, что выполняется одно и только одно из двух соотношений (50:2) и (50:3). Это означает, очевидно, что никогда не выполняется

(50:4) 2= 2 т

i£S i£-S

или, в эквивалентной форме, что никогда не выполняется

(50:5) 3>i=t2 Wi-

i£S i=l

(49:W*:b). Используя определение W в форме (50:1), мы видим, что это условие выполняется, если все wt 0 2).

х) То есть число, которое нечетно и для которого игра может быть существенной. 2) Это, конечно, вполне правдоподобное условие. Удивительно здесь то, что мы не требуем, чтобы wt >> 0, т. е. что мы можем допустить существование нулевых весов.

[Старт] [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]