Графический метод решения игры

Решение игры в смешанных стратегиях допускает графическую интерпретацию в том и только в том случае, если хотя бы один игрок имеет всего лишь две стратегии, т.е. игры размерности 2 х 2, 2 х n и m x 2.

Рассмотрим игру в 2 х n. Матрица игры имеет вид

Н =

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

1) вычислить вероятности р₁* и р₂*, при которых реализуется максиминная стратегия игрока А;

2) цену игры V.

Стратегии игроков А и В покажем в виде таблицы 5.

Таблица 5 – Стратегии игроков в игре 2 x n

Так как р₁ + р₂ = 1, то р₂ = 1 - р₁ , и соответственно, т. к. q₁ + q₂ = 1, то q₂ = 1 - q₁.

Учитывая это, запишем выражение для минимального ожидаемого среднего выигрыша игрока А при применении игроком В стратегии S₁

(5.1)

Аналогично запишем выражение для минимального ожидаемого среднего выигрыша игрока А при применении игроком В стратегии S₂

(5.2)

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

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

y = k x + b,

где y – это ;

k = разность элементов соответствующего столбца матрицы игры;

b – значение соответствующего элемента последней строки матрицы игры.

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

В декартовой системе координат по оси х (ось вероятности р₁) отложим единичный отрезок (рисунок 5.1). Точка х = 0 соответствует р₁ = 0, точка х = 1 соответственно р₁ = 1.

Рисунок 5.1 – Графическая интерпретация игры 2 х 2 в смешанных стратегиях

(для игрока А)

Из точки х = 0 проведем вертикальную линию (левую ось ординат - ось 1). Из точки х = 1 проведем вертикальную линию (правую ось ординат- ось 2).

Пусть игрок В применяет свою чистую стратегию S₁, то при p₁ = 0 из (5.1) M₁[S₁] = a₂₁. Отложим эту точку на вертикальной оси 1 (точка S₁). При p₁ = 1 из (5.1) M₁[S₁] = a₁₁. Отложим эту точку на вертикальной оси 2 (точка S₁₁). Соединим эти точки прямой линией (получим прямую S₁-S₁₁). Ординаты этой прямой будут соответствовать минимальному среднему ожидаемому выигрышу игрока А при применении игроком В стратегии S₁ и изменении вероятности применения игроком А стратегии R₁ от 0 до 1 (р₁ меняется от 0 до 1)..

Пусть игрок В применяет свою чистую стратегию S₂, то при p₁ = 0 из (5.2) M₁[S₂] = a₂₂. Отложим эту точку на вертикальной оси 1 (точка S₂). При p₁ = 1 из (5.2) M₁[S₂] = a₁₁. Отложим эту точку на вертикальной оси 2 (точка S₂₂). Соединим эти точки прямой линией (получим прямую S₂-S₂₂). Ординаты этой прямой будут соответствовать минимальному ожидаемому выигрышу игрока А при применении игроком В стратегии S₂ и изменении вероятности применения игроком А стратегии R₁ от 0 до 1 (р₁ меняется от 0 до 1). Точка пересечения этих двух прямых и была бы решением игры, если бы у игрока В было тоже всего две стратегии. Ордината этой точки дает максимальный из минимальных выигрышей игрока А, т.е. это и есть цена игры V. Расстояние от точки р₁ = 0 до точки М – показывает оптимальное значение р₁ (значение р₁*, при котором игрок А будет получать максимальный из минимальных выигрышей при применении игроком В стратегий S₁ и S₂. Расстояние от точки М до точки р₁ = 1 даст значение р₂*.

Цену игры V можно получить и аналитически, вычислив любое из выражений (5.1, 5.2, …).

Аналогично можно построить прямые для других стратегий игрока В. В этом случае на графике, изображенном на рисунке 5.1 будет не две, а несколько пересекающихся (или не пересекающихся) прямых. Решение игры (цену игры и значения вероятностей р₁*, р₂*) даст та точка, которая будет иметь минимальную ординату.

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

На рисунке 5.1 прямые, соответствующие стратегиям S₁, S₂ пересекаются. Однако так бывает далеко не всегда. Отсутствие точки пересечения сигнализирует о том, что у игрока В имеется доминируемая стратегия.

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

Задача 3. Решить игру 2 х n, заданную матрицей игры

А = .