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


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


152

Интересующее нас перечисление равнозначно перечислению множеств И7771, для которых мы располагаем различными характеризациями, например характеризацией (51 :G) из п. 51.4.1.

Рассмотрим минимальные множества, которые могут принадлежать W™. Так как (51:G:d) исключает из Wm пустое множество и одноэлементные множества, это означает рассмотрение двухэлементных множеств в Wm. Эти множества обладают следующим свойством.

(52:А) Двухэлементное множество принадлежит W"1 тогда и только тогда, когда оно принадлежит W1).

Доказательство. То, что из первого следует второе, очевидно. Для доказательства обратного предположим, что двухэлементное множество S принадлежит W. Собственными подмножествами S являются пустое, а также одноэлементные множества. Ни одно из них не принадлежит W. Поэтому S принадлежит Wm.

Мы предполагаем производить классификацию по двухэлементным множествам, содержащимся в Wm.

52.2.2. Можно себе представить, что Wm вовсе не содержит двухэлементных множеств. Обозначим эту возможность символом С0.

Следующей альтернативой является то, что Wm содержит ровно одно двухэлементное множество. Некоторой перестановкой игроков 1, 2, . . ., п мы можем добиться того, чтобы это множество было множеством (1,2). Обозначим эту возможность символом CV

Далее, Wm может содержать два или более двухэлементных множеств. Рассмотрим два из них. По (51:G:a) они должны иметь общий элемент. Некоторой перестановкой игроков 1, . . ., п мы можем добиться того, чтобы общим элементом было 1, а оставшимися элементами этих множеств 2 и 3.

Итак, W™ содержит (1, 2) и (1,3).

Обозначим возможность, при которой Wm не содержит иных двухэлементных множеств, символом С2-

52.2.3. Предположим теперь, что Wm содержит другие двухэлементные множества. Предположим, кроме того, что не все из них содержат 1.

Рассмотрим поэтому двухэлементное множество, не содержащее 1. По (51:G:a) оно должно содержать общие с (1, 2) и с (1,3) элементы. Так как 1 исключается, это множество должно быть (2,3).

Таким образом (1,2), (1,3) и (2,3) принадлежат Wm (мы имеем здесь полную симметрию относительно 1, 2, 3).

Рассмотрим теперь какое-либо другое двухэлементное множество из Wm. Оно не может содержать все три элемента 1, 2, 3. Некоторой перестановкой этих игроков мы можем добиться того, чтобы это множество не содержало 1. Но оно должно иметь общие элементы с (1, 2) и с (1, 3), а так как 1 исключается, оно должно быть множеством (2, 3). Но мы предполагали, что оно отлично от (2,3). •

Таким образом, Wm содержит двухэлементные множества (1,2)% (1,3), (2,3) и никаких иных. Обозначим эту возможность символом С*..

52.2.4. Остается альтернатива, что Wm содержит другие двухэлементные множества, кроме (1,2), (1,3), но что все они содержат 1.

Некоторой перестановкой игроков 4, . . п мы можем дать соответствующим игрокам номера 4, . . ., к + 1, где к = 3, . . ., п - 1

) То есть неминимальное множество в W должно иметь хотя бы три элемента.,



Таким образом, Wm содержит двухэлементные множества (1,2), (1,3), (1,4), . . ., (1, к + 1) и никаких других. Обозначим эту возможность СИМВОЛОМ Cfc.

52.2.5. Удобно объединить для совместного рассмотрения случаи С0, Си С2, из п. 52.2.2 со случаями Сд, к == 3, . . ., п - 1, из п. 52.2.4.

Тогда мы имеем случаи

Ch, А:=-0, 1, ..., п - 1.

Теперь в случае Ck Wm содержит двухэлементные множества (1,2), . . ., (1, к + 1) и никаких других. Дополнительной перестановкой игроков 1, . . ., п1) мы можем заменить эти множества на (1, п), . . . . . ., (к, п).

Именно в этой форме мы собираемся использовать случаи Ckl к = 0, . . ., п - 1. Теперь СА содержит двухэлементные множества (1, п), . . ., [к, п) и никаких других.

Кроме этих Сй, возможна только альтернатива С* из п. 52.2.3, которую мы оставим без изменения.

52.3. Разложение в случаях С*, Сп-ъ<) Cti-i

52.3.1. Из всех этих альтернатив три могут быть разобраны немедленно: С*, Сп-2, Cn-i.

Пусть имеет место С*. Рассмотрим S I. Если S содержит два или более из элементов 1, 2, 3; например 1, 2, то тогда S з(1,2). (1,2) принадлежит W и, следовательно, S тоже. Если S содержит один или менее из элементов 1, 2, 3, например S не содержит 2,3, то 5 g -(2, 3) (2,3) принадлежит Wn -(2,3) принадлежит L. Следовательно, S также принадлежит L. Итак, мы видим, что W состоит точно из тех S, которые содержат два или более из элементов 1, 2, 3. Поэтому Wm состоит точно из множеств (1, 2), (1, 3), (2, 3)2). Итак, (1, 2, 3) есть для этой игры множество 10 из п. 51.7.

Другими словами, ядро рассматриваемой игры есть игра трех лиц с участниками 1, 2, 3. Ее W™ состоит из тех же (1,2), (1,3), (2,3). Как уже упоминалось (в последний раз в п. 52.1), эта игра описывается символом [1, 1, Ид. Оставшиеся п - 3 игроков, 4, . . ., п являются «болванами».

Итак, мы видим, что случай С* представлен ровно одной игрой, а именно игрой трех лиц [1, 1, 1] с числом «болванов», равным п - 3.

52.3.2. Пусть имеет место случай С. Рассмотрим S I. Предположим сначала, что игрок п принадлежит S. Если S не имеет других элементов, то 5 - одноэлементное множество и, следовательно, принадлежит L. Если S имеет другие элементы, скажем & = 1, п - 1, то S з (£, п). Так как (t, п) принадлежит W, то S тоже. Другими словами, если S содержит тг, то ч£ принадлежит W, за исключением случая, когда S = (п). Применяя это к -5, мы получим, что если п не принадлежит S, то S принадлежит W, когда -S не принадлежит W, т. е. тогда и только тогда, когда -S = (п); иными словами S = (1, . . ., п - 1).

1) А именно подстановкой * П \ ; см. п. 28.1.1.

V п, 1, Z, . . ., ть 1/

2) Эти двухэлементные множества принадлежат Wm по определению, но мы показали сейчас, что они исчерпывают VP™ полностью.



2) Таким образом, двухэлементными множествами Wm являются (1, /г), . . . . . ., (п - 1, п), как и должно быть по определению. Новым фактом является здесь то, что единственный элемент Wm, кроме перечисленных, есть (1, . . ., п - 1).

Заметим, что последнее множество не есть двухэлементное только потому, что п 4.

2) Таким образом, двухэлементными множествами Wm являются (1, тг), . . . . . ., (п - 2, тг), как и должно быть по определению. Новым фактом является то, что единственный элемент Wm, отличный от перечисленных, есть (1, . . ., п - 2).

Для п = 4 последнее множество также двухэлементное, в результате чего изменяется класс игры (он становится С* вместо 6-2> т- е- Съ)-Следовательно, класс Сд 2 непуст только при п 5.

3) Для п 5. Случай Сп-2 пуст для тг = 4. См. предыдущую сноску.

Следовательно, W состоит точно из следующих S: все подмножества, содержащие тг, за исключением (тг), а также множество (1, . . ., п - 1). Легко проверить, что W действительно удовлетворяет требованиям (49:W*), а также что эта игра может быть описана как взвешенная мажоритарная игра. Все игроки 1, . . ., п - 1 имеют одинаковый вес, в то время как игрок п имеет вес, в п - 2 раза больший. Таким образом, эта игра описывается символом [1, . . ., 1, п - 2].

W71 немедленно получается из W. Оно состоит точно из следующих S: (1, тг), . . ., (тг - 1, тг), (1, . . ., тг - 1) х). Легко проверить, что эта игра однородна и нормирована с а = 1. Это значит, что as = 1 (см. п. 50.2) для всех S из этого Wm. Поэтому мы можем написать [1, . . ., 1, п - 2]д.

Итак, мы видим, что случай Сп представлен только одной игрой - игрой п лиц [1, . . ., 1, п - 2]h.

52.3.3. Пусть имеет место случай Сп-.2. Рассмотрим некоторое S L Предположим сначала, что п принадлежит S. Если S не содержит других элементов, кроме, возможно, п - 1, тс) S (п - 1, тг). Но (тг - 1, тг) не принадлежит Wm, а потому и W (по (52:А) из п. 52.2.1). Поэтому S принадлежит L вместе с (тг - 1, тг). Если £ имеет элементы, отличные от тг - 1, скажем i = 1, . . ., тг - 2, то S з (t, п). Множество (£, п) принадлежит W, а поэтому и S принадлежит W. Итак, мы видим, что если п принадлежит S, то S принадлежит W, за исключением случаев S = (п) или S = (п - 1, п). Применяя это к дополнению -S, мы получим, что если п не содержится в S, то S принадлежит W, когда -S = (п) или -S = (п - 1, п), т. е. S = (1, . . ., тг - 1) или (1, . . ., п - 2).

Следовательно, W состоит из следующих множеств S: все подмножества, содержащие тг, за исключением (тг) и (тг - 1, тг); множества (1, . . ., тг - 2) и (1, . . ., тг - 1). Легко проверить, что это W действительно удовлетворяет условиям (49:W*).

Wm немедленно получается из W. Оно состоит из следующих S: (1, тг), . . ., (тг - 2, п) и (1, . . ., тг - 2) 2). Итак, (1, . . ., тг - 2, тг) есть 10 из п. 51.7 для этой игры.

Другими словами, ядро рассматриваемой игры есть игра п - 1-го лица с участниками 1, . . ., п - 2, тг. Ее Wm состоит из (1, тг), ... . . ., (тг - 2, тг), (1, . . ., тг - 2). Таким образом, случай Сп 2 для тг - 1 игроков есть аналог случая Сп для описанного выше случая п игроков. Поэтому эта игра описывается символом [1, . . ., 1, тг - 3]д. Оставшийся тг - 1-й игрок является «болваном».

Итак, мы видим следующее.

Случай Сп-2 представлен ровно одной игрой 3) - игрой тг - 1 игроков [1, . . ., 1, тг - 3]/г с одним «болваном».

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