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


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


19

Для доказательства (15.4) достаточно вспомнить, что согласно теореме п. 15.1 в рассматриваемом сл)Л1ае максимум достигается на чистой стратегии: X = /. Это и означает (15.4). Аналогично доказьшается (15.5). □

Теоретико41гровой смысл доказанной теоремы весьма прозрачен. Первый игрок получает максимин выигрыша, если противник знает применяемую им чистую стратегию. Но если некоторая его чистая стратегая оптимальна, то это значит, что он может ее применением и ограничиться, а его противник может действовать с учетом этого обстоятельства. Выражаясь йесколько вольно, можно утверждать, что наличие у игрока чистой оптимальной стратегаи отражает некоторые неблагоприятные для него условия игры, не позволяющие ему "запутьшать" противника.

15.4.Вернемся к формулировке теоремы из п. 15.1. Из нее следует, что для любых X и F G Y должно быть

minX4 .i; шахЛ-.Г.(15.6)

Кроме того, для оптимальности стратегаи X необходимо и достаточно, чтобы левая сторона этого соотношения обращалась в точное равенство:

mmXA,j = v,(15.7)

а для оптимальности стратегаи Y необходимо и достаточно, чтобы точным равенством оказалась правая сторона соотношения (15.6):

v=msixAiY,(15.8)

15.5.Иногда бьшает удобно проверять оптимальность стратегаи X и Y, записьюая равенства (15.7) и (15.8) в виде неравенств, которые в действительности оказьюаются равносильными равенствам:

minX4.y>i;,(15.9)

maxAY,(15.10)

В самом деле, в (15.9), равно как ив (15.10), строгого неравенства быть не может, так как это противоречило бы определению значения игры (именно, противоречило бы соотношению (15.6)).

15.6.Неравенства (15.9) и (15.10) можно записать соответственно в виде

XA-vдля всех / = 1,...,а2,(15.11)

Л/.Г длявсех / = l,...,w,(15.12)

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

15.7.Следующие критерии оптимальности стратегаи игроков в матричной игре не предполагают знания значения этой игры.

Теорема. Если X и Y - соответственно стратегии игроков I и 2, а V - некоторое число, причем

max AYv < min ХА,.,(15.13)

то X и Y - оптимальные стратегии игроков, а v = Vj.



Доказательство. Из (15.6) и (15.13) следует, что

msixAiY = v = v. =minXAi, i j

и, в частности, вьшолняются равенства (15.7) и (15.8). □

15.8.Условие (15.13) можно заменить на эквивалентное ему. Следствие. Если X и У - стратегии игроков \ и 2, а v - число, причем

AYvXAj(15.14)

для любых i = I,... ,т и / = 1,...,«,

то Хи Y - оптимальные стратегии игроков, а v = v.

Для доказательства достаточно заметить, что соотношения (15.14) и (15.13) равносильны. □

15.9.В формулировках утверждений пп. 15.7 и 15.8 упоминание о "некотором числе и" можно опустить.

Теорема. Если X и Y - стратегии игроков I и2,то для их оптимальности достаточно соблюдения неравенства:

тахЛ,..У=ттХ4 ..(15.15)

Для доказательства достаточно в качестве "числа и" взять любой из стоящих в (15.14) экстремумов. □

15.10.Как и в теореме п. 15.7, от неравенства между экстремумами можно перейти к неравенствам между конкретными значениями выиг-рьппей.

Следствие. Если стратегии Хи Y игроков 1и2 таковы, что A,Y<XA,(15.16)

для любых i = I,, . . ,т и j = 1,. ., ,п,

то эти стратегии оптимальны.

Это следует из того, что утверждения (15.16) и (15.15) равносильны. □ 15.11. Отметам в заключение одну простую связь между значениями игры и ее подыгр.

Теорема. Если есть х-подыграигры Г, д + -ее -подыгра, то v-vv..(15.17)

Доказательство. Согласно (15.1) должно быть

V. - = шах min ХА max min ХА = i;., X JX j

где максимум по Х берется по множеству Х всех смешанных стратегий игрока 1 в игре -, а максимум по X - по множеству всех его смешанных стратегий X в игре . Ссылка на п. 3.6 доказьгоает левое неравенство в (15.17).

Правое неравенство в (15.17) устанавливается аналогично. □



§ 16. МНОЖЕСТВА ОПТИМАЛЬНЫХ СТРАТЕГИЙ ИГРОКОВ в МАТРИЧНЫХ ИГРАХ

16.1.Теорема. В матричной игре Г множества оптимальных стратегий игроков 8 (А) и < (А) являются выпуклыми непустыми многогранниками.

Доказательство. Согласно п. 15.6 множество 8 (А) 51вляется множеством всех решений системы неравенств (15.10), т.е. пересечением конечного числа замкнутых полупространств. Кроме того, оно является ограниченным. Тем самым согласно п. 11.3 это множество является выпуклым многогранником.

То, что вьшуклым многогранником является множество (А), устанавливается аналогично ссылкой на систему неравенств (15.11). □

Заметим, что многогранность и вьшуклость множеств оптимальных стратегий игроков в матричной игре являются элементарными и как бы непосредственно наблюдаемыми фактами (мы здесь оставляем в стороне возможные рассуждения по поводу нетривиальности утверждений о том, что ограниченное пересечение конечного числа замкнутых полупространств конечномерного евклидова пространства есть вьшуклый многогранник, т.е. вьшуклая оболочка конечного числа точек - вершин; это наглядно и как бы очевидно). Напротив, доказательство непустоты этого многогранника потребовало, как мы видели, известных усилий. Эта теорема исторически не сразу поддалась доказательству, и даже высказьюались сомнения в ее справедливости.

16.2.Из доказанной в п. 16.1 теоремы вытекает, что если значение v игры Г заранее известно (например, если оно может быть найдено на основании каких-либо обшлх свойств матрицы вьшгрышей Л), то многогранники 8 (А) и (А) для этой игры можно считать заданными, хотя, быть может, и "в недостаточно явном виде" (т.е. своими гранями, а не вершинами).

§ 17. СПЕКТРЫ СТРАТЕГИЙ И ДОПОЛНЯЮЩАЯ НЕЖЕСТКОСТЬ

17.1. Нахождение оптимальных стратегий игроков в матричньгх играх (т.е. описание множеств § (А) и (А) для тех или иных матриц А или целых классов матриц) является, вообще говоря, достаточно трудоемким делом.

Попытки систематического описания множеств оптимальных стратегий игроков приводят к их определению не посредством универсальных формул, а лишь посредством альтернативных формул: перебирается достаточно обширный список формул, по каждой из них находится некоторый "кандидат в оптимальные стратегии", который и проверяется на оптимальность (например, по критериям, приведенным в § 16).

Численное же нахождение оптимальных стратегий в матричных играх требует значительного объема вычислений, который быстро растет с увеличением размеров матрицы вьшгрьппей игры.

Из сказанного вытекают две задачи: во-первых, систематизировать и тем самым сократить поисю! аналитических выражений для оптимальных стратегий игроков и, во-вторых, уменьшить число чистых стратегий игроков

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