Имя материала: Математические методы в экономике

Автор: Замков Олег Олегович

13.4. принципы решения матричных антагонистических игр

В качестве основного допущения в теории игр предполагается, что каждый игрок стремится обеспечить себе максимально возможный выигрыш при любых действиях партнера. Предположим, что имеется конечная антагонистическая игра с матрицей выигрышей 1-го игрока Ни, соответственно, матрицей выигрыша 2-го игрока -Н. Пусть Игрок 1 считает, что какую бы стратегию он ни выбрал, Игрок 2 выберет стратегию, максимизирующую его выигрыш, и тем самым минимизирующую выигрыш Игрока 1. Оптимальная стратегия Игрока 1, которая обеспечит ему наибольший из возможных выигрышей вне зависимости от стратегии противника, будет состоять в выборе стратегии с самым высоким из таких платежей. Таким образом, Игрок 1 выбирает і-ю стратегию, которая является решением задачи

max тіпЛ(/

Игрок 2 л очно так же стремится обеспечить себе наивысшую величину выигрыша (или, что эквивалентно, наименьшую величину проигрыша) вне зависимости от стратегии, избранной партнером. Его оптимальной стратегией будет столбец матрицы Не наименьшим значением максимального платежа. Таким образом, Игрок 2 выберет 7-ю стратегию, которая является решением задачи

min шах/г,,

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

hit 5: max min htj

Соответственно, если Игрок 2 придерживается своей минимаксной стратегии, его проигрыш будет не больше минимаксного значения (называемого верхней ценой игры), т.е.

htj < min max Л(>

В случае, если верхняя цена игры равна нижней, т.е.

max min п~ = min max h:j = hj

оба игрока получают свои гарантированные платежи, а значение А * называется ценой игры. Элемент А. матрицы выигрышей, соответствующий максиминной и минимаксной стратегиям, называется седловой точкой матрицы Н (это объясняется формой графика функции выигрыша в точке А.: она напоминает седло, убывая при изменении одной из переменных и возрастая при изменении другой переменной). В случае, если цена антагонистической игры равна О, игра называется справедливой.

Рассмотрим игру, в которой Игрок 1 располагает двумя стратегиями, а Игрок 2 - тремя. Пусть матрица выигрышей Игрока 1 имеет следующий вид:

2 1 -1 О

(Поскольку мы рассматриваем пример антагонистической игры, матрица выигрышей Игрока 2 будет равна Яр взятой с обратным знаком, т.е. Н2 = - Hv)

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

Точно так же Игрок 2 рассматривает свои наихудшие варианты, когда противник выбирает свою первую стратегию, если Игрок 2 выбирает первую или вторую стратегии, или когда противник выбирает вторую стратегию, когда Игроком 2 выбран третий столбец. Эти варианты соответствуют максимальным значениям столбцов 2, 1 и 6. Взяв минимальное значение этих максимумов, Игрок 2 останавливается на своей второй стратегии, при которой его проигрыш минимален и равен 1:

m&xh^ {216) t

minmaxA.

 

Следовательно, в этой игре существуют совместимые выборы, т.е.

h ' = max min     = min max h{] = ]

і     і     j '

В итоге будет разумно ожидать, что в описанной выше игре противники будут придерживаться избранных стратегий. Матричная антагонистическая игра, для которой max min htJ = min max hljt

'     j     j і

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

Однако далеко не все матричные антагонистические игры являются вполне определенными, и в общем случае

Игры, в которых выполняется строгое неравенство, называются не полностью определенными играми (или не имеющими решения в чистых стратегиях играми). Следующая матрица представляет пример подобной игры:

6-2 3 -4 5 4'

Для этой игры max min h. = -2 < 4 = min max Л. В результате,

если игроки будут следовать предложенным выше правилам, то Игрок 1 выберет стратегию 1 и будет ожидать, что Игрок 2 выберет стратегию 2, при которой проигрыш равен -2, в то время как Игрок 2 изберет стратегию 3 и будет ожидать, что Игрок 1 выберет стратегию 2 с выигрышем, равным 4. Однако если Игрок 2 выберет свою третью стратегию, то Игрок 1 поступит правильнее, выбирая вторую, а не первую стратегию. Аналогично, если Игрок 1 выберет первую стратегию, то Игроку 2 выгоднее выбрать вторую стратегию, а не третью. По всей видимости, в играх такого типа принцип решения в чистых стратегиях оказывается непригодным.

В описанной ситуации игрокам становится важно, чтобы противник не угадал, какую стратегию он будет использовать. Для осуществления этого плана игрокам следует пользоваться так называемой смешанной стратегией. По существу, смешанная стратегия игрока представляет собой схему случайного выбора чистой стратегии. Математически ее можно представить как вероятностное распределение на множестве чистых стратегий данного игрока. В итоге векторх = (хр х2,... хт), где х.>О соответствует вероятности применения Игроком 1 /-и стратегии и J^x,. = 1, задает смешанную страте-

гию этого игрока. Аналогично определяется смешанная стратегия Игрока 2 у — (yv у2,... уп). Мы будем предполагать использование игроками их смешанных стратегий независимым, так что вероятность, с которой Игрок 1 выбирает i'-ю стратегию, а Игрок 2 -у'-ю, равна ху;. В этом случае платеж равен h... Суммируя по всем і и у, найдем математическое ожидание выигрыша Игрока 1:

 

/ <

или в матричных обозначениях v, = х Ну'.

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

v = max min х Н у'.

'           і У

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

v = min max х Н у'

I           у X

Фундаментальным результатом теории игр является так называемая Теорема о минимаксе, которая утверждает, что сформулированные задачи для Игрока 1 и Игрока 2 всегда имеют решение для любой матрицы выигрышей Я и, кроме того,

V, = v2 = V.

Существующие доказательства этой теоремы основаны на теореме о неподвижной точке, или свойстве отделимости вьптуклых множеств (см., например, Г.Н.Дюбин, В.Г.Суздаль. Введение в прикладную теорию игр).

Как и для вполне определенных игр, стратегия х* Игрока 1 называется максиминной стратегией, стратегия Игрока 2 у - минимаксной стратегией, значение v - ценой игры; в случае, когда v= О, игра называется справедливой.

Очевидным следствием из Теоремы о минимаксе является соотношение

 

х Я / < V < х* Я у,

8 О. О. Замков

которое означает, что никакая стратегия Игрока 1 не позволит выиграть ему сумму большую, чем цена игры, если Игрок 2 применяет свою минимаксную стратегию, и никакая стратегия Игрока 2 не даст возможности проиграть ему сумму меньшую, чем цена игры, если Игрок 1 применяет свою максиминную стратегию. Это верно также и для чистых стратегий как для частного случая смешанных стратегий (т.е. чистая стратегия - это стратегия, используемая с вероятностью 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 |