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


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


148

ТУ, которые удовлетворяют (49: ТУ*) из п. 49.6.2. Мы также заметили там, что, возможно, полезно заменить рассмотрение ТУ (всех выигрывающих коалиций) рассмотрением Wm (всех минимальных выигрывающих коалиций).

Каждая из этих процедур обеспечивает перечисление всех простых игр. Использование W предпочтительнее с идейной точки зрения, так как ТУ имеет более простое определение, a ТУт вводится с помощью W. Для практического перечисления всех простых игр, что в данный момент является нашей целью, использование ТУ™ предпочтительнее, так как Wm меньше, чем ТУ1), и, следовательно, описывается более просто.

Мы последовательно опишем обе эти процедуры. Окажется, что их обсуждения дадут естественное применение понятий удовлетворяемо-сти и насыщения, введенных в п. 30.3.

51.2. Метод насыщения. Перечисление посредством W

51.2.1. Множество Охарактеризуется свойствами (49:ТУ*) из п. 49.6.2, т. е. условиями (49:W*:a) - (49:W*:c), которые и составляют (49:W*).

Отбросим пока (49:W*:c) и рассмотрим только (49:W*:a) и (49:W*:b). Из этих двух условий следует, что никакие два элемента из ТУ не могут быть непересекающимися 2). Другими словами, если обозначить отрицание дизъюнктности, т. е. S п Тф 0> через SMiT, то из (49:W*:a) и (49:W*:b) следует -удовлетворяемость3). Более исчерпывающим утверждением в этом направлении является следующее:

(51:A) (49:W*:a), (49:W*:b) эквивалентны -насыщенности.

Доказательство, -насыщенность ТУ означает следующее:

(51:1) S принадлежит ТУ тогда и только тогда, когда S п Т Ф 0

для всех Т из ТУ.

Из (49:W*:a) и (49:W*:b) следует (51:1). Действительно, пусть ТУ удовлетворяет (49:W*:a) и (49:W*:b). Если S принадлежит ТУ, то мы знаем, что S п Т ф 0 для всех Т из ТУ. Если S не принадлежит ТУ, то тогда Т = - S принадлежит ТУ, по (49:W*:a), и S[\T = 0.

Из (51:1) следует (49:W*:a) и (49:W*:b). Действительно, пусть ТУ удовлетворяет (51:1). Докажем сначала (49:W*:b), а затем (49:W*:a).

(49:W*:b). Если S удовлетворяет критерию (51:1), то это верно и для каждого надмножества S. Следовательно, ТУ содержит все надмножества своих элементов.

(49:W*:a). Благодаря доказанному выше -S не принадлежит ТУ тогда и только тогда, когда никакое подмножество -S не принадлежит ТУ, т. е. когда любое Г из ТУ не содержится в -S или, что то же самое, когда для любого Т из ТУ 8{\Тф 0. По (51:1) это означает просто, что S принадлежит ТУ.

Таким образом, во всех случаях ровно одно из S и -S принадлежит ТУ.

г) Семейства множеств W и L не пересекаются. Они имеют одинаковое число элементов в силу (48:А:Ь) из п. 48.2.1. Вместе они исчерпывают 7, которое содержит 2п элементов. Следовательно, W, так же как и £, содержит ровно 2n 1 элементов.

Число элементов в Wm может быть различным, но всегда значительно меньше (см. четвертое замечание в п. 53.1).

2) Доказательство. Пусть S, Т принадлежат W л S[\T - 0. Тогда -S 3 Т и, следовательно, -S принадлежит W по (49:W*:b), таким образом, нарушается (49: W*: а).

3) См. определения в п. 30.3.2.



Ясно, что отношение SM\T симметрично; следовательно, мы можем применить (30:G) из п. 30.3.5 х).

51.2.2. Для того чтобы обсудить (49:W*) на этой основе, следует ввести в рассмотрение (49:W*:c). Это может быть сделано двумя путями. Первый путь полезен для последующего сравнения.

(51 :В) Семейство W удовлетворяет (49:W*) тогда и только тогда, когда оно -насыщено и не содержит ни 0, ни одноэлементных множеств.

Доказательство. (49:W*) объединяет (49:W*:a), (49:W*:b) и (49:W*:c). Первые два условия по (51:А) означают .-насыщенность. Если считать (49:W*:a) выполненным, то (49:W*:c) может быть установлено следующим образом. Если S есть / или п - 1-элементное множество, то -S не принадлежит W. Поэтому ни 0, ни одноэлементные множества не принадлежат W.

Польза от второго пути более непосредственная. Пусть У0 - семейство всех множеств, отписываемых в (49:W*:c), т. е. оно состоит из / и всех п - 1-элементных подмножеств /. Тогда мы имеем

(51 :С) V есть подмножество W, удовлетворяющего (49:W*), тогда

и только тогда, когда Fljlo .-удовлетворяемо.

Доказательство. То, что V и для W выполняется

(49:W*), означает следующее. W з V, W удовлетворяет (49:W*:a), (49:W*:b), т. е. является «-насыщенным в силу (51:A). W удовлетворяет (49:W*:c), т. е. W 3 V0. Другими словами, мы ищем -насыщенное №э V \JV0, т. е. хотим узнать, может ли V[) V0 быть расширено до -насыщенного множества.

Далее, мы знаем, что применимо (30:G) из п. 30.3.5, и, следовательно, результаты последней части п. 30.3.5 также применимы 2). Возможность этого расширения эквивалентна -удовлетворяемости VJ V0.

51.2.3. Переформулируем (51 :С) более подробно.

(51 :D) Семейство V будет подмножеством W, удовлетворяющего

(49:W*), тогда и только тогда, когда оно обладает следующими свойствами:

(51:D:a) Любые два S и Т из V пересекаются.

(51:D:b) V не содержит ни 0, ни одноэлементных множеств.

Доказательство. Согласно (51 :С) мы должны доказать, J-удовлетворяемость V\j V0, т. е. что любые два S и Т из V или V0 пересекаются.

Если оба множества S и Т принадлежат У, то это совпадает с (51:D:a). Если оба множества S и Т принадлежат V0, то оба они имеют - 1 элементов. Следовательно, они не могут быть непересекающимися 3).

г) Следует вспомнить, что в п. 30.3.5 мы предполагали справедливость х?Ах, т. е. в нашем случае SMtS- Это означает, что S Ф 0, так как SMiS нарушается при S = 0.

Однако (49:W*:a) и (49:W*:b) исключают 0 из W; следовательно, мы можем использовать в качестве области D из п. 30.3.2, вместо / (семейства всех подмножеств /) 1 - 0 (семейство всех непустых подмножеств /). Это избавляет нас от S = 0.

2) Заметим, что область D = I - 0 (см. предыдущую сноску) конечна.

3) Мы используем то, что 2 (п - 1) > п, т. е. п > 2, т. е. п 3. Следовало бы сказать об этом подробно с самого начала, но это вполне естественное допущение, так как простые игры (т. е. множества с (49:W*)) существуют только для п 3 (см. пп. 49.4 и 49.5).



Из множеств S и Т одно принадлежит У, а другое У0. По симметрии можно предположить, что S £ У, а Т £ У0. Итак, 5 из F не может быть дизъюнктным с 7 или с любым п - 1-элементным множеством, а это совпадает с (51:D:b).

(51 :D) решает вопрос о перечислении всех ТУ. Начиная с любого У, которое удовлетворяет (51:D:a) и (Sl.D.b)1), мы можем увеличивать его постепенно до тех пор, пока это можно делать, не нарушая (51:D:a) и (51:D:b). Когда этот процесс не может быть продолжен дальше, мы имеем У, которое является максимальным подмножеством ТУ (с 49: W*)), т. е. мы получаем нужное ТУ. Проводя этот последовательный процесс построения всеми возможными путями, мы получим все искомые ТУ.

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

51.3. Основания для перехода от ТУ к Wm. Трудности использования Wm

51.3.1. Рассмотрим семейства ТУШ из п. 49.6.

Мы хотим охарактеризовать эти ТУт непосредственно и найти некоторый простой процесс построения их всех. Далее мы выведем два различных способа характеризации, оба - типа насыщения. Первый 1>УДет введен асимметричным отношением, а второй- симметричным. Таким образом, именно второй способ, который подходит для искомого построения, аналогичен построению ТУ в п. 51.2.

Мы тем не менее приведем обе характеризации, потому что их эквивалентность весьма поучительна. Первая в некоторых (технических) отношениях напоминает определение решения (см. пп. 30.3.3 и 30.3.7), и, следовательно, переход к эквивалентной второй форме интересен тем, что указывает пути разрешения проблем этого типа. Ранее мы упоминали (в п. 30.3.7), сколь желателен мог бы быть соответствующий переход для нашего понятия решения.

51.3.2. Пусть ТУ - семейство, содержащее все надмножества своих элементов, например удовлетворяющее (49:W*:b). Тогда семейство ТУт его минимальных элементов определяет ТУ. Действительно, ясно, что ТУ является семейством надмножеств всех элементов ТУт.

Следовательно, если дано семейство У и мы ищем такое ТУ, удовлетворяющее (49:W*), что У = ТУШ, то это ТУ обязательно должно быть семейством У надмножеств всех элементов У.

Следовательно, У = ТУт для ТУ, удовлетворяющего (49:W*), тогда и только тогда, когда эти два требования удовлетворяются для семейства

ТУ = У2). Перейдем теперь к преобразованию этой характеризации у jym в харакхерИзацИЮ насыщения.

Обозначим утверждение, что ни S [} Т = 0, ни S zd Т, через SM2T. Тогда мы имеем:

(51 :Е) У = ТУт для ТУ, удовлетворяющего (49:W*), тогда и только

тогда, когда У «5?2-насыщено и не содержит ни 0, ни одноэлементных множеств.

х) В принципе мы можем начать с пустого множества. Читатель заметит, что исключение 0 из V (см. выше) не влияет на возможность V = 0.

2) То есть W = V есть единственное семейство, которое может удовлетворять этим требованиям, но даже для него они могут не выполняться.

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