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


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


119

(Мы пишем v(S)- вместо vT(S).) Снова ввиду (41:6) / является разлагающим множеством игры Г, если

(43:5) v(S{]T) = v(S) + v(T) для S с= Т д= I-J.

Мы должны доказать эквивалентность условий (43:4) и (43:5). Так как / 9= /, очевидно, что (43:4) есть частный случай (43:5), поэтому нам необходимо доказать только, что из (43:4) следует (43:5).

Предположим поэтому, что выполнено условие (43:4). К игре Г мы можем применить формулу (41:6) с множествами /, К = I - /.

Рассмотрим два множества: S s /, Т <=: I - J. Пусть Т = T[)J, тогда Т" = Т - Г содержится в / - /. Таким образом, Т = Г \] Т", Т J, Т" <=: I - J, и применение к игре Г (41:6) с множествами J, I - J дает

(43:6) v(T)=v(T) + \(T").

Далее, S s / S / и Г сг /, так что S [) Г д= /. Кроме того, Г" д= / - /. Очевидно, что (S\j Т)\]Т" = S[) Т. Следовательно, применение к игре Г (41:6) с множествами J, I - J дает, кроме того,

(43:7) v (S U Т) = v (S U Г) + v (Т").

Наконец, Tc=I-J и Тs /, так что Г д=/ - /. Следовательно, (43:4) дает нам

(43:8) w(S\)T)=y(S)+y(T).

Подставим теперь (43:8) в (43:7) и с помощью (43:6) упростим правую часть; эти преобразования дают в точности требуемую формулу (43:5).

43.3.2. Утверждение (43:D) показывает, что стоит рассматривать только такие разлагающие множества /, для которых / Ф 0, но никакое собственное подмножество / Ф 0 множества / разлагающим не является. Такое множество /, по очевидным причинам, мы будем называть минимальным разлагающим множеством.

Рассмотрим наши определения неразложимости и минимальности. Из (43:D) сразу следует, что

{43:Е) /-компонента А игры Г неразложима тогда и только тогда, когда / есть минимальное разлагающее множество.

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

(43:F) Любые два различных минимальных разлагающих множества

не пересекаются.

(43: G) Объединение всех минимальных разлагающих множеств равно /.

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

2) Интуитивный смысл этих утверждений должен быть совершенно ясен. Они правдоподобным образом описывают структуру всех возможных способов разложе-лия игры Г.



Доказательство (43:F). Пусть /, /" - два минимальных разлагающих множества, имеющих непустое пересечение. Тогда согласно (43:С) / (]J" Ф 0 есть разлагающее множество, которое содержится и в /, и в /". Из минимальности / и /" следует, что / f] J" равно как /, так и /". Следовательно, / = /".

Доказательство (43:G) Достаточно показать, что каждое к 6 I принадлежит некоторому минимальному разлагающему множеству.

Существуют разлагающие множества, которые содержат игрока к (например, /). Пусть / - пересечение всех таких множеств. Согласно (43:С) / есть разлагающее множество. Если бы / не было минимальным, то существовало бы разлагающее множество / Ф 0, / и содержащееся в /. Но согласно (43:А), (43:С) множество /" = /-/ = /f] (/ - /) также является разлагающим, и очевидно также / Ф 0, /. Либо /, либо /" = / - / должно содержать к; пусть, например, это будет множество /. Тогда / содержится среди тех множеств, пересечением которых является множество /. Поэтому / /. Но это невозможно ввиду того, что / / и J ф J,

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

Пусть К - разлагающее множество. Если / - минимальное разлагающее множество, то, согласно (43:С), J(\K есть разлагающее множество; кроме того, J{\K е /; поэтому либо J{]K = 0, либо J{]K = J. В первом случае / и К не пересекаются, во втором / К. Итак, мы видим следующее:

(43:1) Каждое минимальное разлагающее множество / либо не пере-

секается с К, либо содержится в К.

Пусть К - объединение первых множеств /, а К" - объединение вторых. К U К" есть объединение всех минимальных разлагающих множеств, и, следовательно, согласно (43:G)

По определению, К* не пересекается с К, а К" содержится в К, т. е.

Из совместного выполнения условий (43:9) и (43:10) необходимо следует, что К" = К; поэтому К есть объединение соответствующей совокупности минимальных множеств, что и требовалось.

43.3.3. Утверждения (43:F) и (43:G) показывают, что минимальные разлагающие множества образуют разбиение множества / в смысле п. 8.3.1, а их объединение равно /. Это разбиение мы будем называть разлагающим разбиением игры Г и будем обозначать его через Пг. Теперь утверждение (43:Н.) можно выразить следующим образом:

(43:Н*) Разлагающее множество К I характеризуется следующим свойством: точки каждого элемента Пг находятся в одном и том же отношении к множеству К - иначе говоря, каждый элемент Пг либо содержится в К, либо не пересекается с К.

Таким образом, Пг показывает, насколько далеко можно продвинуться в разложении игры Г в /, не нарушая наложенных правилами

(43:9)

К\]К"=1.

(43:10)

К <= I - К,

Кс=К.



игры Г связей между игроками х). Ввиду (43:Е) элементы Пг характеризуются также и Tejjf свойством, что они разлагают Г на неразложимые компоненты.

43.4. Свойства разлагающего разбиения

43.4.1. После того как установлена природа разлагающего разбиения Пг, естественно изучить влияние степени тонкости этого разбиения. Мы собираемся исследовать только два крайних случая: случай, когда Пг является настолько мелким, насколько это возможно, т. е. когда оно разбивает множество / на одноэлементные множества, и случай, когда Пг является настолько крупным, насколько это возможно, т. е. когда оно не разбивает / совсем. Другими словами, в первом случае Пг есть совокупность всех одноэлементных множеств (в /), а во втором случае Пг состоит из одного множества /.

Смысл этих двух крайних случаев легко устанавливается следующим утверждением:

(43:J) Пг есть совокупность всех одноэлементных множеств (в /)

тогда и только тогда, когда игра несущественна.

Доказательство. Из (43:Н) или (43:Н*) ясно, что устанавливаемое свойство Пг эквивалентно утверждению о том, что все множества / ( /) являются разлагающими. Иначе говоря (ввиду (43:1)), для дополняющих друг друга множеств / и К ( = / - /) игра Г является разложимой. Это означает, что во всех этих случаях выполнено равенство (41:6). Отсюда, однако, следует, что условие, налагаемое равенством (41:6) на множества S, Т (т. е. S /, Т К), означает просто, что множества S, Т не пересекаются. Таким образом, наше утверждение принимает вид

v(S[)T)=v(S) + v(T) для5ПГ=0.

Но согласно (27:D) из п. 27.4.2 это есть условие несущественности.

(43:К) Пг состоит из множества / тогда и только тогда, когда игра Г неразложима.

Доказательство. Из (43:Н) (или (43:Н*)) следует, что устанавливаемое свойство Пг эквивалентно утверждению о том, что множества 0, / являются единственными разлагающими множествами. Но это есть в точности определение неразложимости, данное в начале п. 43.3.

Эти результаты показывают, что неразложимость и несущественность являются двумя крайними возможностями для игры. В частности, несущественность означает, что разложение игры Г, описанное в конце п. 43.3, можно довести до отдельных игроков, не нарушая никаких связей, установленных правилами игры Г2). Читатель должен сравнить это утверждение с нашим первоначальным определением несущественности в п. 27.3.1.

43.4.2. Между несущественностью, разложимостью и числом п игроков существует следующая связь.

п = 1. Это случай едва ли имеет практическую важность. Очевидно, такая игра неразложима 3), и в то же время она несущественна по первому замечанию п. 27.5.2.

х) То есть, не нарушая свойство самостоятельности полученных в результате разложения множеств.

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

3) Так как / - одноэлементное множество, единственными его подмножествами являются множества 0,1.

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