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


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


50

«л

1/5 О

Рис. 2.11

Рис. 2.13

2 «ЗзX

Рис. 2.14

значит, что никакое подмножество х не порождает покрытия у. Тем самыми О, так что Up = О, и стратегия yQ игрока 2 оказывается его оптимальной стратегией. Игрок 1 бессилен что-либо выиграть, и любая его стратегия оказывается оптимальной.

29.4.Пусть в простой игре Г на единичном квадрате множество zp является полосой, расположенной вдоль диагонали квадрата cитyaщй, как это изображено на рис. 2.13.

Ясно, что здесь множество чистых стратегий Xj = 1/5, = 1/2, =4/5 порождает покрытие у,а множество стратегий = О, >2 = 1/2 и = 1 - укладку в х. Поэтому согласно сказанному в п. 28.4 здесь up = 1/3, а пара смешанных стратегий X* и К*, в которых стратегии из троек {x, х, х} {у, у , у} выбираются с вероятностью 1/3 каждая, составляет седловую точку.

Очевидно, чистые стратегии, составляющие спектры оптимальных стратегий ЛГ*и F*, можно в этой игре несколько "пошевелить", не нарушая порождения этими чистыми стратегиями соответствующих покрытий и укладок, и тем самым - оптимальности X* и К*. Развитию конструкции, лежащей в основе такого "шевеления", будет посвящен следующий параграф.

29.5.Пусть в простой игре Г на единичном квадрате множество zp имеет вид, изображенный на рис. 2.14. Здесь помеченное на рисунке множество из пяти чистых стратегий игрока 1 порождает покрытие множества у кратности 3, а такое же множество чистых стратегий игрока 2 - укладку в множестве х, также кратности 3. Поэтому в данном случае по следствию п. 28.4 должно быть up = 3/5, а одна из си-туащй равновесия получается в результате взятия каждой из перечисленных стратегий игроков с вероятностью 1/5.

29.6.Пусть для простой игры Г множество zp имеет вид, изображенный на рис. 2.15. Очевидно, здесь проекции сплошных вертикальных отрезков составляют покрытие у, а проекции сплошных горизонтальных отрезков - укладку в х. Счетное число тех и других дает основание применить теорему п. 28.5, согласно которой здесь up = О, оптимальной стратегией игрока 1 является любая его стратегия, а е-оптимальная стратегия игрока 2 получится, если взять в качестве ее спектра любое доста-



точно большое подмножество { у,, }приписав каждой стратегии из спектра

вероятность, не превосходящую е.

29,1. Рассмотрим, наконец, простую игру Г на единичном квадрате, для которой множество Zp имеет вид, изображенный на рис. 2.16. Здесь никакой конечный набор сечений не порождает покрытия у. Значит, у нас нет в этом случае основашй оценивать ip снизу положительным числом. С другой стороны, стратегии = с < 1 и

= 1 игрока 2 порождают укладку в х, так что i7p 1/2. Так как вместе с тем никакой укладки в \ из трех множеств здесь сконструировать нельзя, должно быть и up 1/2. Значит. i7p = 1/2.

§ 30*. ГРАФОАНАЛИТИЧЕСКОЕ РЕШЕНИЕ ОДНОГО КЛАССА ПРОСТЫХ ИГР

30.1.в этом параграфе мы будем рассматривать простые игры Г на единичном квадрате, для которых множество Zp имеет вид, вообще говоря, криволинейной полосы (рис. 2.17), ограниченной графиками непрерывных неубывающих функций f и g, удовлетворяющих условиям

Дх) = О на [0,] и строго возрастает на [а, 1]; g(x) строго возрастает на [О, Ь] и g(x) = 1 на [Ь, 1]; m<g(x) на [О, 1]. Таким образом,

zr = {(x,y): f(x)<yugix)}.

30.2.Ясно, что на сегменте [О, /(!)] существует функция, обратная к /.

Из рис. 2.17 видно, что составляющая множество Zp полоса имеет ширину по вертикали не меньшую, чем некоторое положительное 5верх, и ширину по горизонтали не меньшую, чем некоторое положительное гор-

Рис. 2.17

Рис. 2.18

30.3. Опишем процесс построения для рассматриваемой игры Г такого конечного множества { Х], Хз,. . . } С х, которое порождает покрытие у, а также равномощного ему множества { >i, J2, • • } У, порождающего укладку в X.

Положим индуктивно

У1 =0, Xl = а,

Уклх =g(Xk), Xk + i =Г(Ук).



Геометрически этот процесс соответствует построению зигзага, как это изображено на рис. 2.18.

Длина каждого вертикального звена зигзага не менее чем бверт» а каждого горизонтального - не менее чем брор- Суммарная же длина всех горизонтальных (равно как и всех вертикальных) звеньев зигзага не превосходит единицы. Поэтому число всех звеньев зигзага должно быть конечным; оно не должно превосходить 2(тах{бверт, брор))~ • Следовательно, через некоторое конечное число шагов зигзаг "уткнется" либо в правую сторону квадрата ситуаций на некотором Уп >/(1), либо в верхнюю его сторону на некотором х„ Ь.

Рис. 2.19

30п 1

Рис. 2.20

В первом из этих случаев (рис. 2.19) мы примем х„ = 1 и закончим на этом процесс построения зигзага. Во втором случае (рис. 2.20) положим + 1 = 1 и также закончим процесс.

30.4. Нетрудно видеть, что множество стратегий {Xi,. . . , х„ } порождает покрытие у. При / = 1,. . ., А2 - 2 каждое пересечение у О у состоит ровно из одной точки, множество же

yUn-\ yUn = [Уп-1, Уп]

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

Множество стратегий {yi,. . . ,Уп} укладки в х не порождает: сечения х\у1 =Xi] и х\у1+1 = [xi, Xi+i] пересекаются (хотя и по единственной точке). Однако если зигзаг утыкается в правую сторону квадрата, то суммарная длина его вертикальных звеньев без последнего будет меньше единицы, так что некоторое согласованное смещение стратегий Уг,. . . уУп вверх уже будет порождать укладку в х.Если же зигзаг утыкается в верхнюю сторону квадрата, то сумма длин горизонтальных звеньев зигзага (также без последнего) будет меньше единицы, и снова возникает возможность "растягивания" элементов покрытия за счет смещения стратегий Xi,. . . ,х„ вправо.

Применение следствия п. 28.4 дает, что = l/n, а приписьюание каждой из порождающих покрытие и укладку чистых стратегий вероятности Ijn дает оптимальные стратегии игроков. Разумеется, ими не исчерпьюается множество всех оптимальных стратегий, полное описание которого возможно, но требует более обстоятельных рассмотрений.

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