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


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


146

Доказательство. То, что 3 доминируется некоторым элементом из V, т. е. некоторым ат, где Т £ U, означает, что (50:12) выполняется для некоторого Т £ U. Это равносильно тому, что - R ф) £ U*, т. е. что R (Р) $ U+.

Следовательно, R (Р) принадлежит U+ тогда и только тогда, когда

Р не доминируется никаким элементом из V.

50.5.3. Прежде чем перейти к дальнейшему, рассмотрим четыре простых свойства множества U+ из (50: G).

(50:Н:а) U* = U+=.W, если U = Wm.

Доказательство. Предположим, что U = Wm. Тогда U* состоит из тех множеств, которые содержат подмножества, принадлежащие Wm, т. е. минимальные выигрывающие подмножества. Следовательно, U* = W. Операция, которая приводит в (50: G) от U* к U+, является комбинацией преобразований (48:А:а) и (48:А:Ь) из п. 48.2.1. Мы уже тогда заметили, что, когда эти два преобразования применяются к W, они компенсируют друг друга. Следовательно, U* = W дает U+ = W.

(50:H:b) U* - монотонная, a U+ - антимонотонная операция. Иными словами, из Ui U2 следует U* U* и з U%.

Доказательство. Достаточно вспомнить определения из (50:6), чтобы увидеть, что Ut U2 влечет Щ s Щ, а это в свою очередь влечет U* 3 Ui.

(50:Н:с) Для всех наших U Wm выполняется U* W U+.

Доказательство. Комбинируем (50:Н:а) и (50:Н:Ь) (подставляя U, Wm вместо ии U2).

(50:H:d) U* и U+ содержат все надмножества своих элементов.

Доказательство. Для Z7* это очевидно. Рассматриваемое свойство эквивалентно сформулированному в (48:А:с) из п. 48.2.1. (Берем W вместо U*, U+.) Далее, операция, которая приводит в (50: G) от С/* к U+, является комбинацией преобразований (48:А:а) и (48:А:Ь) из п. 48.2.1 (см. доказательство (50:Н:а)). Применение (48:В) из п. 48.2.2 к этим двум преобразованиям показывает, что рассматриваемое свойство сохраняется при переходе от U* к U+.

50.5.4. Заметим, что U* и U+ допускают простую словесную интерпретацию. Если мы знаем о принадлежащих U коалициях только то, что они выигрывающие, то о каких коалициях можно сказать, что они заведомо выигрывающие, а о каких, - что они не являются заведомо проигрывающими?

Первыми являются такие коалиции, которые имеют подмножества, принадлежащие U, т. е. коалиции из U*. Заведомо проигрывающими будут дополнения к ним, т. е. коалиции, не принадлежащие U+. Следовательно, U* есть множество первых упомянутых коалиций, a U+ - множество вторых.

Теперь смысл утверждений (50:Н:а) - (50:Н:с) становится ясным. Для U = Wm все очевидно. Заведомо выигрывающие коалиции в точности



совпадают с теми, которые не являются заведомо проигрывающими, и они образуют множество W. По мере того как U убывает, пробел между этими множествами коалиций расширяется. Первое множество убывает как подмножество W, а второе возрастает как надмножество W. Утверждение (50:H:d) в равной степени правдоподобно.

50.6. Переформулирование полученного результата

50.6.1. Утверждение (50.G) из п. 50.5.2 позволяет нам установить следующее:

(50:1) V является решением в том и только в том случае, если R (Р)

принадлежит U+ тогда и только тогда, когда Р принадлежит V.

Итак, нам только остается решить, когда выполняется (50:1). С этой

-> ->

целью рассмотрим R £ U+ и определим р, для которого R (Р) = R. Рассмотрим три возможности:

(50:13) S (-1) + 2 (-l+*i) = 0,

т. е.

(50:14) 2

-> ->

Если существует Р, для которого R (Р) = R, то мы имеем (50:15) 0= 2 Pi2 (-1) + 2 +

г=1 i$R i£R

т. е. имеем в (50:13) и (50:14) знак 5g. Поэтому > в (50:13), (50:14) исклю-

-* ->

чает существование какого-либо Р с R (Р) = R. Поэтому впредь можно не рассматривать множества R из С/+ с > в (50:13) и (50:14). Рассмотрим с другой стороны i? g С/+ с < в (50:13) и (50:14). Тогда существует беско-

-> 71

нечно много способов выбора Р с 2 Р* = 0 и

Г -1, если

г = \ - 1+хь если i£R.

Для всех них должно быть R (Р) з i?. Следовательно, они принадлежат

V в силу (50:H:d). Так как множество V конечно, эти р не могут все принадлежать V. Мы получили противоречие. Оно означает, что множества R (= U+ с < в (50:13) и (50:14) не могут существовать.

50.6.2. Остается рассмотреть множества из которые имеют

в (50:13) и (50:14) знак =. Согласно сказанному выше, эти множества

->

должны представлять в точности р £ V.

Если Р 6 V, т. е. если р = аг, где Т g U, то мы имеем следующую

->

ситуацию: R (Р) есть Т плюс множество тех £, для которых xt = 0. Т принадлежит С/ 9= U* <== С/4" (второе включение следует из (50:Н:с)); следовательно, R (Р) принадлежит С/+. Также

2 xi ~ 2 xi=п-



Итак, мы имеем в (50:13) и (50:14) знак =. Следовательно, все р из V удовлетворяют этому условию.

Обратно. Рассмотрим R 6 U+ с = в (50:13), (50:14). Добавление к R всех тех г, для которых xt = 0, не влияет ни на факт принадлежности R к U+ (по 50:H:d), ни на равенство (50:14). Поэтому мы можем предполагать, что R содержит все эти i.

Если теперь для дележа Р имеет место R (Р) = R, то pf -1 + хь

для i 6 Но всегда pf - 1. Так как 2 Р* = 0» эт0 влечет

-1, если iR,

(50:16) fo = j

l + a;*, если

Наоборот, из (50:16) следует, что Р является дележом, для которого

R (Р) = R. Следовательно, наше требование в этом случае состоит в том,

-> ->

что р из (50:16) должно быть некоторым аг, где Т £ U. Это означает, что Т и R различаются только элементами i, для которых xt = 0. Это свойство нечувствительно по отношению к нашей начальной модификации i?, к включению всех таких i в R.

Подведем итоги.

(50:J) Для того чтобы V было решением, необходимо и достаточно,

чтобы выполнялось следующее.

Назовем игрока i безразличным, если xi = 01). Тогда мы имеем

(50:8*) 2 *i = n

для множеств Т из U и также для всех тех множеств, которые отличаются от них только безразличными элементами. Кроме того, мы должны потребовать

(50:9*) 2 Xi>n

для, всех остальных Т из U+. При использовании этого результата нужно сначала выбрать множество U Wm, затем попытаться определить xt из (50:8*) и, наконец, проверить, удовлетворяют ли эти х% неравенствам

(50:7) xtO

и (50:9*).

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

В такой ситуации находится исключенный игрок в дискриминирующем решении игры трех лиц (см. (32:А) в п. 32.2.3 с с = 1). Но там решение было бесконечным множеством, тогда как наше V должно быть конечным.

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

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