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


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


27

Покажем, что игрок 1 имеет в игре вполне смешанную оптимальную стратегию. Возьмем сначала для этого смешанную стратегию = . . ., 1/п). Тогда aj

niri Х A,j = min - > 0.

Если теперь предположить, что для оптимальной стратегии Х*= (i,. . • , при некотором / будет ( =0, то, как легко подсчитать, окажется Х*у1.у = О, а это противоречит тому, что по доказанному

0<VA= min X*A,i < X*A.i . /

Значит, в игре все оптимальные стратегии игрока I являются вполне смешанными (мы доказали даже несколько более того, что нам требовалось), и мы оказываемся в условиях второй части теоремы п. 24.3. Поэтому согласно (24.6), (24.2) и

(24.3) мы получаем

Y-(l J y7 L,....±>(24.7)

Но теперь оказьшаетя, что и игрок 2 имеет в игре вполне смешанную оптимальную стратегию, и мы можем воспользоваться первой частью теоремы п. 24.3, согласно которой

2У(±,...,М(24.8)

24.5.Описываемый формулой (24.8) результат на первый взгляд может показа-заться парадоксальным, так как согласно ему игрок 1 должен с большими вероятностями искать менее ценные предметы. Однако этот парадокс разрешается, если принять во внимание оптимальную стратегию игрока 2, описываемую формулой (24.7). Из этой формулы видно, что при своих оптимальных действиях игрок 2 чаще всего прячет как раз наименее ценные предметы. Поэтому естественно, чю игрок 1 должен стремиться найти именно их.

Заметим, что векторы оптимальных стратегий игроков 1 и 2 в диагональной игре равны друг другу. Говорить о том, чю оптимальные стратегии игроков в данном случае совпадают, едва ли уместно, так как они выражают совершенно различные действия того и другого. Совпадают здесь только вероятности обращения игроков к одному и тому же месту.

24.6.Класс всех диагональных игр при всей их простоте и элементарности может в некотором смысле считаться универсаль ным. Именно, любая вполне смешанная стратегия является оптимальной в некоторой диагональной игре.

Действительно, вполне смешанная стратегия Z = ( ,. .. , „) является оптимальной стратегией каждого из игроков в диагональной игре Г, где

О ... О

О 2- ... О

О О ...

24.7. Иногда оказывается, что проверка невырожденности матрицы выигрышей игры затруднительна. Имея в виду такие случаи, желательно исключить проверку невырожденности матрицы из решения игры. В связи с этим представляется полезной следующая лемма.

Лемма. Если в матричной пХ п-игре оба игрока имеют вполне смешанные оптимальные стратегии, а для одного из них вполне смешанными являются все оптимальные стратегии, то матрица А оказывается невырожденной,

6.Н.Н. Воробьев81



Доказательство. Пусть в пХ«-игре вполне смешанными являются все оптимальные стратегии игрока 1. Ввиду существования вполне смешанной оптимальной стратегии игрока 2, как и раньше, все оптимальные стратегии игрока 1 суть решения уравнения ХА =Это уравнение заведомо разрешимо (ибо оптимальные стратегии у игрока 1 существуют!). Поэтому если бы матрица А бьша вырожденной, то решения уравнения составляли бы целое подпространство положительной размерности. При этом некоторые решения находились бы на пересечении этого подпространства с границей фундаментального симплекса смешанных стратегий X. Но точки этой границы соответствуют смешанным стратегиям, имеющим нулевые компоненты, т.е. не являющимся вполне смешанными, а это противоречит предположенному. □

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

24.8.Доказанная лемма позволяет модифицировать теорему п. 24.2 следующим образом.

Теорема. Если в пХп-матричной игре оба игрока имеют вполне смешанные оптимальные стратегии, причем для одного из них все оптимальные стратегии являются вполне смешанными, то матрица А выигрышей невырожденная, оптимальные стратегии X и Y в игре являются единственными и могут быть определены по формулам (24,1) и (24.3). Значение игры определяется по формуле (24.2).

24.9.Следующее понятие приводит к удобному признаку полной смешанности игры.

Определение. Будем говорить, что в «Х«-игре имеется доминирующая диагональ, если для некоторого вещественного > О будет

aii>q, aijSq при /9/,(24.9)

и имеется сильно доминирующая диагональ, если, кроме того, найдется такая смешанная стратегия Х игрока 1, что

ХМ>/.П(24.10)

Использование в п. 24.4 при рассмотрении диагональной игры вектора Х = (1/«,. . . , 1/п) показывает, что диагональ в этой игре оказывается сильно доминирующей. В сущности, доказательство следующей теоремы является обобщением анализа диагональной игры.

Теорема. Игра с сильно доминирующей диагональю является вполне смешанной.

Доказательство. Пусть в игре имеется сильно доминирующая диагональ. Тогда согласно (24.10) будет

итах min XА. j > mm ХA.j > q.(24.11)

Предположим теперь, что в игрок 1 имеет оптимальную стратегию, не являющуюся вполне смешанной. Пусть, например, Х*= (i,. . ., „) -такая стратегия, и = 0. Тогда в силу (24.9) мы получаем

VA - min ХМ.уХМ., = Z<q ,

а это противоречит (24.11). Значит, все оптимальные стратегии игрока 1 являются вполне смешанными.



Но уже из существования одной вполне смешанной оптимальной стратегии у игрока I согласно теореме о дополняющей нежесткости (см. п. 17.3) следует, что для любой оптимальной стратегии Y*= (rji,. .. ,7]) игрока 2 должно быть

Ai.Y*=VA при любом Z = 1,...,л2.(24.12)

Но если r}j = О, то ввиду (24.11) будет

что противоречит (24.12). □

§ 25. МАТРИЧНЫЕ ИГРЫ И ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

25.1. Решение матричной игры можно свести к решению стандартной задачи линейного программирования.

Рассмотрим игру стХ /-матрицей выигрышей Л. Не нарушая общности, можно считать, что все элементы этой матрицы положительны (если это не так, то мы можем,, прибавив ко всем элементам некоторое достаточно большое число, рассматривать получившуюся игру, которая аффинно эквивалентна первоначальной).

Пусть Х - произвольная стратегия игрока 1 в этой игре.

Положим и; = min XA.j и заметим, что из положительности элементов А j

следует положительность vx любой стратегии X. Таким образом, мы имеем

()<Vx<xA.j. /=1,...,л.(25.1)

Кроме того, согласно теореме п. 15.1 оптимальность стратегии Xравносильна тому, что

vx =niax vx =i;.4 .(25.2)

Рассмотрим теперь вектор Х= {llvx)X. Неравенства (25.1) дают нам ХЛ.у1, /-L...,M.(25.3)

То, что X - стратегия, означает

XJl =llvxy(25.4 j

а также

Х>0.(24.5)

Из (25.2) и (25.4) следует, что стратегия X будет оптимальной тогда и только тогда, когда

X/J;->min.(25.6)

В результате (25.3), (25.5) и (25,6) определяют некоторую стандартную задачу линейного программирования. Ее значение есть число, обратное значению первоначальной игры, а всякое ее решение после соответствующей нормировки (т.е. после деления на значение задачи) является оптимальной стратегией игрока 1.

6*ез

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