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


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


118

Должно быть доказано соотношение <42:12) уд (S) + уд (/- S) = уд (/).

Ввиду (41:4) это условие означает, что

{42:12*) vr (S) +vT(J-S) = vr (/).

Для доказательства (42:12*) применим (42:6:Ь) к функции vr (R) и множествам R=J - S и R - J. Для этих множеств соответственно / - R = 5 U К и I - R = K. Тогда равенство (42:12*) примет вид

vr (S) + vr (/) - vr (S U К) = уг (/) - vr (К),

т. е.

vr (S[)K)=vt(S)+yt (К),

а это равенство есть частный случай (41:6) при Т = К.

Итак, мы следующим образом улучшили результат (41 :С) из п. 41.4:

4(42:G) В области всех игр с постоянной суммой игра Г разложима по отношению к множествам J я К (см. 41.3.2) тогда и только тогда, когда она удовлетворяет условию (41:6), т. е. (41:7).

42.5.3. Сравнение результатов (41 :С) из п. 41.4 и (42:G) из п. 42.5.2 показывает, что переход от игр с нулевой суммой к играм с постоянной суммой избавляет нас от нежелательного условия разложимости (41:8), т. е. (41:9).

Разложимость теперь определяется только условием (41:6), т. е. (41:7), и инвариантна относительно стратегической эквивалентности, как это и должно быть.

Мы знаем также, что если игра Г разлагается на две компоненты А и Н (причем все они являются только играми с постоянной суммой!), то мы можем все эти игры с помощью преобразования стратегической эквивалентности свести к играм с нулевой суммой (см. (42:С) в п. 42.2.3 для Г, а затем (42:А) п. 42.2.1 и далее для А, Н.)

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

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

§ 43. РАЗЛАГАЮЩЕЕ РАЗБИЕНИЕ 43.1. Разлагающие множества. Компоненты игры

43.1.1. Разложимость игры Г мы определили не саму по себе, -а по отношению к разбиению множества / всех игроков на два дополнительных друг к другу множества /, К.

Поэтому можно принять следующую точку зрения: будем считать игру Г фиксированной, а множества J я К - переменными. Так как / определяет К (действительно, К=1 - /), достаточно считать единственным переменным /. Тогда возникает следующий вопрос.

Если дана игра Г (с множеством игроков /), то для каких множеств J <=: I (я соответствующих им множеств К - I - J) игра Г является пазложимой?



Те множества / ( /), для которых игра Г является разложимой, мы будем называть разлагающими множествами игры Г. Компонента А, которая получается при этом разложении (см. п. 41.2.1 и (41:4) из п. 41.3.2), называется J-компонентой игры Г *).

Таким образом, разлагающее множество / определяется формулой (41:6) (или, что то же самое, формулой (41:7)) из п. 41.3.2, в которой должна быть сделана подстановка К = I - /.

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

43.2. Свойства совокупности всех разлагающих множеств

43.2.1. Совокупность всех разлагающих множеств данной игры характеризуется несколькими простыми свойствами. Большинство из них имеег непосредственный интуитивный смысл, благодаря чему математические доказательства могут показаться необязательными. Тем не менее мы будем продолжать систематическое изложение и приведем доказательства этих свойств, указав в сносках их содержательную интерпретацию. В дальнейшем характеристическую функцию уг (S) игры Г мы будем обозначать через v (£).

(43:А) / является разлагающим множеством тогда и только тогдау

когда разлагающим является его дополнение К = I - / 2).

Доказательство. Множества J ж К входят в определение разложимости Г симметрично.

(43:В) 0 и / являются разлагающими множествами 3).

Доказательство. Равенства (41:6) или (41:7), очевидно, выполнены при / = 0, К - I, так как v (0) =0.

43.2.2.

(43:С) Если /, /" - разлагающие множества, то множества / (}J"

и / (J J" также являются разлагающими.

Замечание. Пересечение J\Jn. Читателю может показаться странным, что два самостоятельных множества вообще могут иметь непустое пересечение. Однако это возможно, как показывает пример / = J". Более глубокая причина кроется в том,-что самостоятельное множество вполне может быть объединением меньших самостоятельных множеств (его собственных подмножеств). (См. (43:Н) из п. 43.3.) Наше утверждение состоит в том, что если два самостоятельных множества /, J" имеют непустое пересечение J[\J", то это пересечение также есть самостоятельное подмножество. В этой форме оно, вероятно, покажется правдоподобным.

Объединение J\]J". Тот факт, что объединение двух самостоятельных множеств есть снова самостоятельное множество, представляется обоснованным. Оно может стать не столь очевидным, если существует непустое пересечение J{\Jn, но, как обсуждалось выше, этот случай не вносит дополнительных трудностей. Приводимое доказательство в действительности представляет собой в основном точный учет всех возможностей именно этого случая.

Доказательство. Объединение / (J /". Так как /, /" - разлагающие множества, равенство (41:6) выполнено для /, К, равных

1) Согласно тому же определению игра Н (см. п. 41.2.1 и (41:5) из п. 41.3.2) является тогда Я-компонентой игры Г (где к - i - /).

2) Утверждение о том, что множество игроков самостоятельно в смысле п. 43.1,, очевидно, эквивалентно утверждению о том, что самостоятельно его дополнение.

3) Самостоятельность этих множеств очевидна.



соответственно «/, / - /и / - Мы хотим доказать это равенство для множеств J\}J" и I - (/ \JJ"). Для этого рассмотрим два множества: Sg/U/" и Т д= I - (/ у /"). Пусть S = S{]Jf; тогда S" = S - £ содержится в дополнении к и так как S / \)J", S" содержится также в Итак, S = S [j S <= Г, Ss Теперь £ S" I - J, и формула (41:6), примененная к множествам «Г, / - дает

(43:1) у(£) = у(£) + у(£*).

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

(43:2) v (S U Т) = v (5) + v (5" U Т).

Наконец, и Т I--{J\)J") I- J". Поэтому формула (41:6)

для множеств / - J" дает

(43:3) v (5" []Т) = у (S") + v (Т).

Подставим теперь (43:3) в (43:2) и затем упростим правую часть по формуле (43:1); в результате мы получим равенство v (S [] Т) = v (S) + v (Г), которое представляет собой формулу (41:6), что и требовалось.

Пересечение / П Воспользуемся (43:А) и только что установленным результатом. Так как /" - разлагающие множества, мы последовательно получаем, что разлагающими являются множества / - /, / - /", (/ - /) U (/ - Л =/-(/ П J") г) и / П последнее множество является требуемым.

43.3. Описание совокупности всех разлагающих множеств. Разлагающее разбиение

43.3.1. Может оказаться, что не существует разлагающих множеств, отличных от тривиальных 0 и / (см. (43:В) выше). В этом случае мы будем называть игру Г неразложимой 2). Не изучая этот вопрос подробнее 3), мы продолжим исследование раз лагающих множеств игры.

(43:D) Рассмотрим разлагающее множество / игры Г и /-компоненту А игры Г. В этом случае множество J J является разлагающим множеством игры А тогда и только тогда, когда оно является разлагающим множеством игры Г 4).

Доказательство. Ввиду (41:6) и (41:4) / является разлагающим множеством игры А, если

(43:4) v(S[)T) = v(S) + v(T) для Г<=/-/.

х) Дополнение пересечения равно объединению дополнений.

2) Фактически большинство игр являются неразложимыми; в противном случае критерий (42:G) п. 42.5.2 требует выполнения ограничительных уравнений (41:6), (41:7) п. 41.3.

3) Пока! См. сноску 2 выше и приведенные в ней ссылки.

4) Самостоятельность внутри самостоятельного подмножества эквивалентна самостоятельности в исходном (всем) множестве. Это утверждение может показаться очевидным, однако это не так, что будет видно из доказательства.

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