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


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


37

Если смешанная стратегия (х\, Х2, х) такова, что одно из значений X/ = 1, а следовательно, остальные равны нулю, то такая стратегия называется чистой стратегией игрока. Чистая стратегия уже не является случайной. Вспоминая игру, показанную ранее, можно записать оптимальную стратегию первого игрока, какх = (0,0,1), а второго, как у = (0,1,0).

Для случая игры со смешанными стратегиями платежная матрица принимает следующий вид (табл. 5.6).

Таблица 5.6

«и

«12

«2„

<ш2

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

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

max min X «,,,,

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

min max У <3f„v,.

Эти величины определяются соответственно как среднеожидаемые максиминные и среднеожидаемые минимаксные платежи.

Если X*. и у J - оптимальные решения для обоих игроков, каждому

элементу платежной матрицы лу соответствует вероятность х*>*. Сле-довательно, оптимальное ожидаемое значение игры v = Z Z yj • 118



Как и в случае чистых стратегий, выполняется соотношение:

минимаксный ожидаемый проигрьш! > > максиминный ожидаемый выигрьш!.

Когда xi и yj соответствуют оптимальным решениям, вьшолняется

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

Справедлива следующая основная теорема теории матричных игр с нулевой суммой (теорема фон Неймана).

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

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

Теорема 4. Пусть К{х,у) - вещественная непрерывная функция двух векторных аргументов х и у, принимающих значения из выпуклых, замкнутых, ограниченных множеств С czE" и DciE", Причем К(х, у) вогнута по X для всех у е D и выпукла по у для всех х е С. Тогда min max К(х, у) = max min К(х, у).

ухXу

Вернемся к рассмотрению матричной игры в смешанных стратегиях. В этом случае платежная функция имеет вид

K{x,y)=tta,jx,yj. /=iy=i

Области изменения векторов х и у задаются соотношениями (5.6) и (5.7) и, как нетрудно видеть, являются выпуклыми, замкнутыми, ограниченными множествами евклидовых пространств. Функция К(х, у) является линейной и, следовательно, вогнутой по х при фиксированном у и выпукла по у при фиксированном х. Таким образом, из приведенной теоремы следует основная теорема теории матричных игр.

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

Справедлива теорема об активных стратегиях.

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



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

Для игры 2x2 любая чистая стратегия противника является активной, если отсутствует седловая точка

Доминируемые стратегии могут быть исключены, при этом цена игры не изменяется.

Доминирование можно распространить и на смешанные стратегии.

5.2.4. Аналитическое решение игры 2x2. Рассмотрим игру размера 2x2, которая является простейшим случаем конечной игры. Если такая игра имеет седловую точку, то оптимальное решение- это пара чистых стратегий, соответствующих этой точке.

Для игры, в которой отсутствует седловая точка, в соответствии с основной теоремой теории игр оптимальное решение игры существует и определяется парой смешанных стратегий (х*,*) и (yly).

Для того чтобы их найти, воспользуемся теоремой об активных стратегиях. Если первый игрок придерживается своей оптимальной смешанной стратегии, то его средний выигрыш будет равен цене игры V, какой бы активной стратегией ни пользовался второй игрок. Для игры 2x2 любая чистая стратегия противника является активной, если отсутствует седловая точка. Поэтому средний выигрыш и первого игрока, и второго будет равен цене игры. Пусть игра задана платежной матрицей

Средний выигрыш первого игрока, если он использует оптимальную смешанную стратегию / =(х*,Х2), а второй игрок- чистую стратегию, соответствующую первому столбцу платежной матрицы, равен цене игры V:

Тот же средний выигрыш получает первый игрок, если второй игрок применяет стратегию, соответствующую второму столбцу платежной матрицы, т.е. а21 + 22X2 = v. Учитывая, что х* + х* = 1, получаем систему уравнений для определения оптимальной стратегии первого игрока и цены игры:

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