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


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


36

в общем виде условие того, что пара стратегий (/о»7о) образуют ситуацию равновесия, можно записать как aj < aj < a,j для всех / и j. Справедлива следующая теорема.

Теорема 2. Конечная игра имеет седловую точку тогда и только тогда, когда существуют такие чистые стратегии (/о?Уо) > "Р которых

%%.и-(5.3)

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

max min а =minmaxa...

Тогда если щ - максиминная стратегия первого игрока, то maxmina.=mina ,<а ..

\<i<m\<jun \<.j<n V W

Если Уо - минимаксная стратегия второго игрока, то

Поскольку

а < max а,, = min max а, ..

iJQ \<.i<m\Jnx<i<m 0

max mm ay = mm max д;, \<i<m\<j<n \<j<n\<i<m

справедливо соотношение

a. < max min a, < a, ,.(5.4)

Это неравенство справедливо при любых значениях / и у, и в частности при / = Iq J- jqa.следовательно,

а, , < max min а„ < а. , .

Откуда очевидно следует, что

шах min а. = min max а. = <з, , .

l/ml<y<« У lj<n\<i<m lj 0

Из данных равенства и неравенства (5.4) следует неравенство (5.3), что и требовалось доказать.



(Достаточность), Если выполняется неравенство (5.3), то справедлива следующая последовательность неравенств

min max а„ < max а„ <а, < min а, , < max min а„.

Откуда следует, что

mm max а,. < max mm а,..

J I I J

В теореме была доказана справедливость обратного неравенства для произвольной матричной игры, а следовательно, справедливо равенство

min max а = max min , что и требовалось доказать.

J i J I j

Игра двух лиц с нулевой суммой далеко не всегда имеет седловую точку. Например, рассмотрим игру со следующей платежной матрицей (табл. 5.4)

Таблица 5.4

Стратегия 1

Стратегия 2

Минимум по строкам

Стратегия 1

Стратегия 2

Максимум по столбцам

Как легко видеть, условие существования седловой точки для данной платежной матрицы не выполняется в силу того что справедливо условие (5.5)

max min а,, = -1 < min max а.. = +1

l</<ml<y<« \<.j<n\<i<m

(5.5)

Далее исследуем вопрос о нахождении значения игры и оптимальных стратегий игроков в случае отсутствия седловой точки.

5.2.3. Смешанные стратегии.

Как мы отмечали, не все игры двух лиц с нулевой суммой имеют седловую точку. Рассмотрим, каким образом строятся оптимальные стратегии в этом случае. В качестве примера приведем следующую иг-РУ-

Пример (игра «четное-нечетное»). Два игрока одновременно выбрасывают один или два паль-

Теорема фон Неймана. Каждая конечная игра с нулевой суммой имеет по крайней мере одно оптимальное решение, возможно, среди смешанных стратегий.

Если один из игроков придерживается своей опшмальной смешанной стратегаи, то выифыш остается неизменным и равным цене ифы V, если второй игрок не выходит за пределы сюих активных стратегии.



ца. Если сумма выброшенных пальцев оказывается четной, то первый игрок получает от второго 1$. Если же количество выброшенных пальцев будет нечетным, то первый игрок платит второму 1$. Рассмотрим платежную матрицу данной игры (табл. 5.5).

Таблица 5.5

Стратегия 1

Стратегия 2

Минимум по строкам

Стратегия 1

Стратегия 2

Максимум по столбцам

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

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

Для того чтобы ввести понятие оптимальных стратегий в случае игры двух лиц без седловой точки, необходимо обобщить понятие стратегии, введя понятие случайной стратегии. До этого под оптимальной стратегией мы понимали некоторую стратегию, которую игрок применяет каждый раз, когда реализуется данная игра. Почему бы не предоставить игрокам возможность выбирать свои стратегии некоторым случайным образом в соответствии с некоторыми вероятностями. Пусть: xi- вероятность, с которой первый игрок выбрасывает один палец; Х2 - вероятность, с которой первый игрок выбрасывает два пальца; У\- вероятность, с которой второй игрок выбрасывает один палец; У2 - вероятность, с которой второй игрок выбрасывает два пальца.

Если xi и Х2 таковы, что xi > О, Х2 О и xi + Х2= 1, то (хь Х2) - случайная, или смешанная, стратегия первого игрока. Аналогично (у 12) - случайная, или смешанная, стратегия второго игрока, если

У1 > 0,>2> 0,>1+>2= 1.

В общем случае смешанные стратегии есть векторы (хь Х2, х) и (у и Уъ . ".Уг). ДЛЯ которых

х/> о, /= 1, w, £х, =1,

>У> 0,7=Z>y=l.

(5.6) (5.7) 117

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