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

Пример 9. Найти решение игры, заданной платежной матрицей:

а) .

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

На плоскости хOу введём систему координат (рис. 7) и на оси Oх отложим отрезок единичной длины А₁А₂, каждой точке которого поставим в соответствие некоторую смешанную стратегию первого игрока – (х, 1–х). В частности, точке А₁(0;0) отвечает стратегия А₁, точке А₂(1;0) – стратегия А₂.

Рис. 7

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

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

(вспомните планиметрию и рассмотрите трапецию ).

Ординаты точек, принадлежащих ломаной , определяют минимальный выигрыш игрока 1 при применении им любых смешанных стратегий. Эта минимальная величина является максимальной в точке N. Следовательно, этой точке соответствует оптимальная смешанная стратегия , а ее ордината равна цене игры . Координаты точки N находим как точку пересечения прямых В₂В'₂ и В₃В'₃. Соответствующие два уравнения имеют вид

( при стратегии В₂)

( при стратегии В₃)

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

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

( при стратегии А₁)

( при стратегии А₂)

Следовательно, .

б) Найти решение игры, заданной платежной матрицей:

.

Решение. Матрица имеет размерность . Строим прямые (рис. 8), соответствующие стратегиям игрока 1 в системе координат yOx. Ломаная отвечает верхней границе выигрыша игрока 2, а отрезок KL – цене игры .

Рис. 8

Активными стратегиями для 1 игрока являются А₁ и А₄. Стратегии А₂ и А₃ входят в оптимальную смешанную стратегию с частотами, равными нулю. Решение игры сводится к нахождению оптимальных стратегий игры, заданной матрицей .

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

(при стратегии А₁)

(при стратегии А₄)

а для 1 игрока

(при стратегии В₁)

(при стратегии В₂)

Решение игры таково:

Таким образом, имеем следующую схему графического метода решения простейших матричных игр ( или ):

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

2. Строят нижнюю (верхнюю) границу выигрыша.

3. Определяют по чертежу пару «полезных» стратегий из числа построенных для второго (первого) игрока.

4. Выбирают на границе выигрыша точку с максимальной (минимальной) ординатой.

5. Находят решение игры.