Смешанные стратегии и теорема о минимаксе для матричных антагонистических игр

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

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

Поскольку случайная величина задается своим распределением вероятностей, то смешанную стратегию можно отождествлять с вероятностной комбинацией чистых стратегий, т. е. множеством чистых стратегий, взятых в случайном порядке с некоторыми вероятностями. Пусть {.v,;, v₂; .— чистые стратегии первого игрока. При применении смешанных стратегий каждый игрок перед каждой партией выбирает свою чистую стратегию случайным образом, причем каждая чистая стратегия может быть выбрана с определенной для нее вероятностью. Вероятностное распределение определяет сам игрок, исходя из своих интересов (например, получение максимального среднего выигрыша). Это вероятностное распределение для чистых стратегий устанавливается каждым игроком перед игрой и не изменяется в ходе игры.

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

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

Игра с использованием чистых стратегий является частным случаем игры с использованием смешанных стратегий, когда для некоторого значения г имеем /). = 1, а все остальные стратегии (г Ф Г) имеют нулевую вероятность.

Если Pj > 0 для всех г, то смешанная стратегия называется полностью смешанной.

Исходом игры, предусматривающей смешанные стратегии игроков, является пара векторов (р; q).

Смешанную стратегию мы также будем записывать в виде сумм X РД,

i

или Яjtj чистых стратегий s, и Ц первого и второго игроков соответственно.

j

Например, 0,2s₂ +0,8s₄ означает смешанную стратегию, в которой играются строки и S4 с вероятностями соответственно 0,2 и 0,8.

Рассмотрим смешанную стратегию ps_i+(lp)s₂ двух чистых стратегий, V| и % приносящих выигрыши ci и а₂. Тогда ожидаемый выигрыш для смешанной стратегии равен U (p) = ра_л +(1 -р)а₂ — это линейная функция отр, и множество ее значений ?(i7) = [min (a₁;a₂);max (a₁;a₂)]- Это утверждение можно распространить на смешанную стратегию нескольких чистых стратегий.

Теорема 2.1. Пусть {a_va₂,…, a_n} — выигрыши, соответствующие чистым стратегиям {s₁, s₂,—-, 5"} одного из игроков. Тогда множество значений выигрыша Uсмешанной стратегии р = (р_{, р₂,…, р_п) равно

Доказательство. Пусть т = min («, а₂,…, ««); М = шах (й, а₂…а»)• Рассмотрим смешанную стратегию? p, s_:. Ожидаемый выигрыш равен U (p)='? p_ia_i. Имеем i i.

В силу непрерывности линейной функции Щр) заключаем, что E (U) = т;М.

Если, например, в результате выбора чистых стратегий игрок может получить выигрыши соответственно {2; 5; — 3; 8}, то в результате выбора им смешанной стратегии он сможет получить при различных значениях вероятностей выигрыши в промежутке [ —3; 81.

Смешанная стратегия может строго доминировать чистую стратегию. Тогда последняя играться, очевидно, не будет и ее можно исключить, как мы это делали раньше.

Если выбор чистой стратегии заключается в выборе номера строки для первого или столбца для второго игрока, то выбор смешанной стратегии — это выбор векторов вероятности р для первого и q для второго игрока.

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

Решение

Поскольку в первой колонке (d) максимальный элемент (10) расположен в первой строке, то стратегия а не может быть строго доминируема.

Действительно, если бы существовала смешанная стратегия pb + (lр)с, которая строго доминировала стратегию а, то это означало бы, что существует такая вероятность р, при которой выполняется неравенство р -0 + (1 — р) ? 6 > 10. Такой вероятности, очевидно, не существует. Поскольку во второй колонке максимальный элемент (12) расположен во второй строке, то стратегия b также нс может быть строго доминируема. Выясним, может ли смешанная стратегия первого игрока (смесь первых двух стратегий), строго доминировать его третью стратегию: pa + (1 — р) Ь > с. Имеем.

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

Пример 2.10. Дана антагонистическая игра.

Найти все значения х, при которых стратегия с может быть строго доминируема смешанной стратегией ра + (-р)Ь.

Решение

Очевидно, стратегии а и b не доминируют стратегию с. Выясним, существует ли смешанная стратегия а и Ь, строго доминирующая стратегию с: ра + [-р)Ь>с.

Для этого необходимо, чтобы существовало решение системы неравенств.

Решаем эту систему неравенств графически (рис. 2.1).

Рис. 2.1.

Из рисунка очевидно, что решение системы существует при х > -18.

Ответ: хе (-18;°°).

Теорема 2.2 (основная теорема теории игр. Джон фон Нейман, 1928)^[1].

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

При выборе первым игроком г'-й чистой стратегии и вторым игрокому'-й чистой стратегии выигрыш первого игрока будет равен и_1}. Но поскольку это событие наступает с вероятностью, равной произведению вероятностей PiPj (в предположении независимости выбора стратегий игроками), математическое ожидание выигрыша первого игрока будет равно YjPidj^uij' или в матричных обозначениях р⁷ t/q. О

Определение 2.9. Решением игры двух игроков называется пара стратегий (в общем случае смешанных), обладающих следующим свойством: если один из игроков придерживается своей оптимальной стратегии, то для другого не может быть выгодным отклоняться от своей оптимальной стратегии. Мы будем говорить тогда, что на таких стратегиях достигнуто положение равновесия. Если р и q — оптимальные стратегии соответственно первого и второго игроков, то для любых векторов вероятностей р и q (смешанных стратегий первого и второго игроков) имеем

Предположим, первый игрок избрал г-ю чистую стратегию. Второй игрок будет тогда строить свою смешанную стратегию q так, чтобы максимизировать свой выигрыш или, что-то же, минимизировать выигрыш первого игрока:

Обозначим этот гарантированный для первого игрока выигрыш через ф (/). Если же теперь первый игрок выбирает г-ю чистую стратегию с вероятностью pj, то он заинтересован выбрать вероятности р, таким образом, чтобы максимизировать средний гарантированный выигрыш: шах р,<�р (г).

р Иными словами, стратегия первого игрока заключается в выборе им максиминной стратегии.

Аналогичные рассуждения в отношении второго игрока приведут к его минимаксной стратегии.

Теорема о минимаксе утверждает, что существуют решения задач (2.1), (2.2) и они совпадают. Обозначим эти решения через (р, q), а цену игры через V = p^rUq. Очевидно, V удовлетворяет условиям.

В случае матричной игры 2×2 с матрицей.

характер изменения платежной функции p⁷f/q как функции от выбираемых стратегий р и q представлен на рис. 2.2.

Цена игры Vявляется и максимальным ожидаемым средним выигрышем первого игрока, и минимальным ожидаемым средним проигрышем второго игрока при проведении серии игр. Таким образом, любая конечная игра двух лиц с противоположными интересами имеет седловую точку в пространстве векторов вероятностей. Эта точка (р, q) называется решением игры, а сами стратегии р и q называются оптимальными стратегиями. Цена игры единственна, но достигаться она может либо в одной точке (р, q) в пространстве IV" ^+п, либо на некотором множестве точек. В последнем случае это множество представляет собой замкнутый выпуклый многогранник. Во всех его точках целевая функция постоянна.

Рис. 2.2.

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

• [1] Доказательство теоремы можно найти, например, в [5].