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

План.

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

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

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

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

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

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

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

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

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

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

¼,

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

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

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

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

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

Решение:

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

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

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

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

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

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

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

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

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

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

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

Рисунок 13.1

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

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

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

Оптимальная стратегия первого игрока Лекция 13. Графическое решение игр - student2.ru , при этом цена игры v = 2½.

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

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

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

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

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

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

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

Рисунок 13.2

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

Оптимальная стратегия второго игрока: Лекция 13. Графическое решение игр - student2.ru при цене игры v = 2½.

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

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

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

Решение: Лекция 13. Графическое решение игр - student2.ru Лекция 13. Графическое решение игр - student2.ru Лекция 13. Графическое решение игр - student2.ru .

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

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

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

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

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

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

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

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

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

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

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

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

Рисунок 13.3

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

Оптимальная стратегия второго игрока Лекция 13. Графическое решение игр - student2.ru , при этом цена игры v = 8/3.

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

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

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

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

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

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

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

Оптимальное решение первого игрока: Лекция 13. Графическое решение игр - student2.ru . Цена игры v = 8/3.

Наши рекомендации