Лекция 13. Графическое решение игр

План.

13.1. Графическое решение игр размерности 2´n.

13.2. Графическое решение игр размерности m´2.

13.1. Графическое решение игр размерности 2´n

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

Рассмотрим игру (2´n), т.е. первый игрок имеет две стратегии, второй игрок имеет n стратегий. Предполагаем, что игра не имеет седловой точки.

Обозначим: х₁ – вероятность применения первым игроком 1 стратегии, х₂ – вероятность применения первым игроком 2 стратегии, причем х₂ = 1 – х₁; у₁ – вероятность применения вторым игроком 1 стратегии, у₂ – вероятность применения вторым игроком 2 стратегии и т.д., у_n – вероятность применения вторым игроком n-й стратегии.

Ожидаемый выигрыш первого игрока при применении вторым игроком 1 стратегии составит

.

Аналогично находится ожидаемый выигрыш первого игрока при применении вторым игроком 2, ¼, n стратегий:

,

¼,

.

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

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

Пример 1. Найти решение игры вида (2´n), заданной платежной матрицей:

.

Решение:

.

Игра не имеет седловой точки.

Ниже представлены ожидаемые выигрыши первого игрока, соответствующие чистым стратегиям второго игрока.

Чистые стратегии Ожидаемые выигрыши

второго игрока первого игрока

1

2

3

4

На оси Х₁ разместим точки х₁ = 0 и х₁ = 1, через которые проводим перпендикулярные оси Х₁ (рис. 13.1). Подставляя х₁ = 0 и х₁ = 1 в выражение – 2х₁ + 4, находим значения 4 и 2, которые откладываем на соответствующих перпендикулярных прямых. Соединив эти точки, получим прямую – 2х₁ + 4.

Рисунок 13.1

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

х₁ + 2 = – 7х₁ + 6, х₁ = ½, х₂ = 1 – х₁ = ½.

Цена игры определяется подстановкой переменной х₁ в уравнение любой из прямых, проходящих через максиминную точку: v = х₁ + 2 = ½ +2 = 2½ или v = – 7х₁ + 6 = – 7×½ + 6 =2½.

Оптимальная стратегия первого игрока , при этом цена игры v = 2½.

Найдем оптимальную стратегию второго игрока. Из рисунка 13.1 следует, что оптимальная стратегия первого игрока определяется как точка пересечения прямых, соответствующих выигрышу первого игрока при использовании вторым игроком третьей и четвертой стратегий, поэтому у₁ = у₂ = 0, а у₄ = 1 – у₃

Чистые стратегии Ожидаемые проигрыши

первого игрока второго игрока

1

2

Оптимальная стратегия второго игрока определится как точка пересечения прямых: 4y₃ – 1 = – 4y₃ + 6, y₃ = 7/8, y₄ = 1 – y₃ = 1 – 7/8 = 1/8 (рис.13.2).

Рисунок 13.2

Цена игры v = 4y₃ – 1 = 4×7/8 – 1 = 5/2 = 2½ или v = – 4y₃ + 6 = – 4×7/8 + 6 = 5/2 = 2½.

Оптимальная стратегия второго игрока: при цене игры v = 2½.

13.2. Графическое решение игр размерности m´2

Пример 2. Найти решение игры вида (m´2), заданной платежной матрицей:

.

Решение: .

Игра не имеет седловой точки.

Пусть у₁ и у₂ (причем у₂ = 1 – у₁) – смешанные стратегии второго игрока.

Ниже представлены ожидаемые проигрыши второго игрока, соответствующие чистым стратегиям первого игрока.

Чистые стратегии Ожидаемые проигрыши

первого игрока второго игрока

1

2

3

4

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

– 2у₁ + 4 = у₁ + 2, у₁ = 2/3, у₂ = 1 – у₁ = 1/3.

Рисунок 13.3

Цена игры определяется как v = – 2у₁ + 4 = – 2×2/3 + 4 = 8/3 или v = у₁ + 2 = 2/3 + 2 = 8/3.

Оптимальная стратегия второго игрока , при этом цена игры v = 8/3.

Поскольку прямые, пересекающиеся в минимальной точке, соответствуют первой и третьей стратегиям первого игрока, то это означает, что х₂ = х₄ = 0. Следовательно, х₃ = 1 – х₁.

Чистые стратегии Ожидаемые выигрыши

второго игрока первого игрока

1

2

Значение х₁ определяется из уравнения:

– х₁ + 3 = 2х₁ + 2, х₁ = 1/3, х₂ = 1 – х₁ = 2/3, v = – х₁ + 3 = – 1/3 +3 = 8/3 или v = 2х₁ + 2 = 2×1/3 + 2 = 8/3.

Оптимальное решение первого игрока: . Цена игры v = 8/3.