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


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


58

(17:F:a) v4 = v[ в том и только в том случае, когда для игрока 1 существует оптимальная чистая стратегия.

(17:F:b) v2 = v2 в том и только в том случае, когда для игрока 2 существует оптимальная чистая стратегия.

Теперь мы имеем = v2 = v, а полная определенность в частном означает Vi = v2 = v, откуда v4 = и v2 = v2. Таким образом, (17:F:a) и (17:F:b) дают вместе (17:Е).

17.10. Ошибки и их следствия. Перманентная оптимальность

17.10.1. Из предыдущих рассуждений мы выяснили, что представляет собой оптимальная смешанная стратегия. Скажем еще несколько слов о других смешанных стратегиях. Мы хотим выразить отличие этих стра-

тегий (т. е. векторов ц) от «оптимальности» и таким образом определить величину ошибки при использовании стратегий, не являющихся оптимальными. Однако мы не будем пытаться исчерпать этот вопрос, имеющий много интересных ответвлений.

Для всех £ £ дУрх и всех т) £ S$2 определим числовые функции (17:13:а) а () = v - min К (!, ij)

(17:13:Ь) (3 (ц) = max К (f, ц) - v.

Согласно лемме (17:А) из п. 17.5.2 это равносильно

(17:13:а*) a(g) = v-min 2 < fa, т2) £Tl,

Т2 *l=3l 32

(17:13:Ь*) р(т]) = тах 2 SJTfa, т2)т]т2-у.

Ti Т2=1

Определение

-> -> -> ->

v = max min К (£, n) = min max К (£, n) -> -> -> ->

£ л л £

гарантирует нам, что всегда

а(1)0, (З(л)О.

Теперь утверждения (17:В:а), (17:В:Ь) и (17:С:а), (17:С:Ь) из п. 17.8

->

дают нам, что стратегия g является оптимальной в том и только в том случае, когда а (£) = 0, a п является оптимальной в том и только в том случае, когда р (п) = 0.

Таким образом, а (£) и р (п) являются удобными числовыми опи-

-> ->

саниями для произвольных £ и л их расстояний от оптимальных стра-

-> ->

тегий. Явное словесное определение а (£), р (п) делает это еще более правдоподобным: формулы (17:13:а), (17:13:Ь) или (17:13:а*), (17:13:Ь*)



показывают, сколько рискует потерять игрок (с точки зрения значения партии для него) х), используя данную стратегию. Под «риском» мы понимаем здесь наихудшее, что может произойти при данных условиях 2).

-> ->

Тем не менее необходимо отдавать себе отчет в том, что а (g) и (3 (т) не указывают, какая именно стратегия противника причиняет эту

(максимальную) потерю для игрока, использующего g или г). В частности, вовсе не очевидно, что если противник использует некоторую оптимальную стратегию, т. е. некоторое г)0 £ В или g0 £А, то это само по себе приведет к максимальным потерям. Если игроки используют отличные

-У -У

от оптимальных стратегии g или г), то максимальные потери достигаются на тех стратегиях т] или g противника, для которых

(17:14:a) К(, rf) = mmK(f, ц),

(17:14:Ь) К(1, ч) = тахКЙ, ч),

т. е. если стратегия ц оптимальна против данной g или g оптимальна

против данной г. При этом мы никогда не можем установить, будет ли

-У -У -У

некоторая фиксированная стратегия г]0 или g0 оптимальной против всех g или Т).

-У -У

17.10.2. Назовем поэтому стратегию г) или стратегию g, которая

-У -У

оптимальна против всех ц или g, т. е. стратегию, для которой выполняются (17:14:а) или (17:14:Ь) в п. 17.10.1 для всех g, т),-- перманентно опти-

-У -У

малъной. Всякая перманентно оптимальная стратегия г) или g необходимо является оптимальной; с концептуальной точки зрения это должно быть ясно, и строгое доказательство является простым.

Доказательство. Достаточно провести доказательство для т; доказательство для g аналогично.

Пусть стратегия ц перманентно оптимальна. Выберем стратегию g*, которая оптимальна против г], т. е. для которой

K(f*, ) = maxK(, V).

х) Под «потерей» игрока понимается значение партии минус его фактический выигрыш:

для игрока 1 v - К (g, т));

для игрока 2 (-v)- (-К (g, ц))=К(1, rjj - v.

2) Действительно, используя предыдущую сноску, а также (17:13:а) и (17:13:Ь), мы имеем

a(g) = v-minK (g, rf) = max{v -К (g, rj)},

-у -у

Р0п) = тахК (f, v = max{K(g, л)-у}.

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



По определению

К(*, л) = ттК(*, ц).

-У -> * -> -У

Таким образом, £* и т) образуют седловую точку функции К (g, г]), и, следовательно, согласно (17:C:f) в п. 17.8.2 т) принадлежите, т. е. является оптимальной стратегией.

Однако открытым остается вопрос: все ли оптимальные стратегии являются перманентно оптимальными? Более того: существуют ли перманентно оптимальные стратегии вообще?

В общем случае ответ оказывается отрицательным. Так, например,

в «орлянке», в игре «камень, мешок и ножницы» единственной оптимальной

-> ->

стратегией (для игрока 1, равно как и для игрока 2) является £ = г\ = = {1/2, 1/2} или соответственно {1/3, 1/3, 1/3} х). Если игрок 1 играет определенным образом, например выбирая всегда «решетку» или всегда «камень» 2), то он проиграет, если противник будет выбирать соответственно «герб» 3) или «мешок» 3). Однако в этом случае стратегия противника не будет оптимальной; она не будет совпадать с {1/2, 1/2} в одном случае и с {1/3, 1/3, 1/3} в другом. Если противник играет оптимальную стратегию, то ошибки игрока не имеют значения 4).

Далее мы приведем другой пример - в более тонком и сложном случае, касающемся покера и необходимости «блефа» (см. пп. 19.2 и 19.10.3).

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

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

Другим предостережением против переоценки этой точки зрения является следующее. Во многих случаях слово «наступательный» употребляется в повседневной речи не в том смысле, как мы только что употребляли; оно употребляется именно в том смысле, который полностью охватывается настоящей теорией. Это, как будет показано в п. 17.10.3, имеет место для всех игр с полной информацией,5) а также в случае таких типично «агрессивных» операций (обусловленных неполной информацией), как «блеф» в покере 6).

17.10.3. Закончим этот параграф замечанием о том, что существует важный класс игр двух лиц с нулевой суммой, в которых существуют

*) См. п. 17.1. Любые другие вероятности приведут к потерям в случае «раскрытия». См. далее. ч

-V ->

2) То есть 1 = 6= {1, 0} или соответственно {1, 0, 0}.

3) То есть т = 6" = {0, 1} или соответственно {0, 1, 0}.

4) То есть плохая стратегия «решетка» (или «камень») может быть побеждена только стратегией «герб» (или «мешок»), которая сама по себе является плохой стратегией.

5) Шахматы и трик-трак относятся к таким играм.

6) Предыдущие рассуждения относятся скорее к отсутствию «блефа». См. § 19.2 и п. 19.10.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]