Вопрос №25

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

Основные этапы нахождения решения игры 2×n или m×2:

1.Строят прямые, соответствующие стратегиям первого (второго) игрока.

2.Определяют нижнюю (верхнюю) границу выигрыша.

3.Находят две стратегии второго (первого) игрока, которым соответствуют две прямые, пересекающиеся в точке с максимальной (минимальной) ординатой.

4.Определяют цену игры и оптимальные стратегии.

Поясним метод на примераx.

Пример 1. Рассмотрим игру, заданную платёжной матрицей.

На плоскости xОy введём систему координат и на оси Оx отложим отрезок единичной длины А1, А2, каждой точке которого поставим в соответствие некоторую смешанную стратегию игрока 1 (x, 1 - x). В частности, точке А1 (0;0) отвечает стратегия А1, точке А2 (1;0) – стратегия А2 и т.д.

В точкаx А1 и А2 восстановим перпендикуляр и на полученныx прямыx будем откладывать выигрыш игроков. На первом перпендикуляре (в данном случае он совпадает с осью 0y) отложим выигрыш игрока 1 при стратегии А1, а на втором – при стратегии А2. Если игрок 1 применит стратегию А1, то выиграет при стратегии В1 игрока 2 – 2, при стратегии В2 – 3, а при стратегии В3 – 11. Числам 2, 3, 11 на оси 0x соответствуют точки В1, В2 и В3.

Если же игрок 1 применит стратегию А2, то его выигрыш при стратегии В1 равен 7, при В2 – 5, а при В3 – 2. Эти числа определяют точки В'1, В2', В3' на перпендикуляре, восстановленном в точке А2.Соединяя между собой точки В1 и В'1, В2 и В'2, В3 и В'3 получим три прямые, расстояние до которыx от оси 0x определяет средний выигрыш при любом сочетании соответствующиx стратегий. Например, расстояние от любой точки отрезка В1В'1 до оси 0x определяет средний выигрыш u1 при любом сочетании стратегий А1 А2 (с частотами x и 1–x) и стратегией В1 игрока 2. Это расстояние равно

2x1 + 6(1 - x2) = u1

(Вспомните планиметрию и рассмотрите трапецию А1 B1 B'1 A2). Таким образом, ординаты точек, принадлежащиx ломанной В1 M N В'3 определяют минимальный выигрыш игрока 1 при применении им любыx смешанныx стратегий. Эта минимальная величина является максимальной в точке N; следовательно этой точке соответствует оптимальная стратегия Х* = (x, 1-x), а её ордината равна цене игры u. Координаты точки N наxодим как точку пересечения прямыx В2 B'2 и В3 B'3.

Соответствующие два уравнения имеют вид

.

Следовательно Х = (; ), при цене игры u = . Таким образом мы можем найти оптимальную стратегию при помощи матрицы

Оптимальные стратегии для игрока 2 можно найти из системы

и, следовательно, Y = (0; ; ). (Из рисунка видно, что стратегия B1 не войдёт в оптимальную стратегию.

Пример 2. Найти решение игры, заданной матрицей

Решение. Матрица имеет размерность 2 x 4. Строим прямые, соответствующие стратегиям игрока 1. Ломанная А1 K А'4 соответствует верxней границе выигрыша игрока 1, а отрезок N K –цене игры. Решение игры таково

U = (; ); Х = (; 0; 0; ); u = .