Матричная игра: решение в смешанных стратегиях

Матричная игра - это модель конфликта двух игроков с противоположными интересами, заданная таблицей выигрышей: строки соответствуют стратегиям одного игрока, столбцы - стратегиям другого, а число в клетке - выигрыш первого игрока (второй его же теряет, поэтому сумма нулевая). Задача решения такой игры - найти оптимальные стратегии обеих сторон и цену игры, то есть результат, на который может рассчитывать каждый игрок при разумной игре противника. Не всегда достаточно один раз выбрать строку или столбец: если чистой оптимальной стратегии нет, решение ищут в смешанных стратегиях - вероятностных распределениях по строкам и столбцам. Ниже разберём алгоритм по шагам: как проверить седловую точку, а если её нет, как вывести p, q и цену игры v и что показывает графический метод. Задайте свою матрицу 2x2 в калькуляторе ниже - он сразу проверит седловую точку и покажет решение.

Что такое матричная игра и когда чистой стратегии недостаточно

Рассмотрим игру двух лиц с матрицей выигрышей размера 2x2:

$$A = \begin{pmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{pmatrix}.$$

Игрок A выбирает строку и стремится максимизировать выигрыш, игрок B выбирает столбец и стремится этот же выигрыш минимизировать. Если бы оба играли только чистыми стратегиями (одна строка или один столбец всегда), то естественная логика такая: A хочет застраховаться от худшего исхода в каждой строке и выбирает строку с наибольшим из этих худших значений, а B симметрично выбирает столбец с наименьшим из наихудших для себя значений. Первое число называется нижней ценой игры, второе - верхней.

Если нижняя и верхняя цена совпадают, чистое решение существует, и дальше можно не искать вероятностей: обе стороны раз и навсегда фиксируют по одной строке и столбцу. Но чаще, особенно в учебных примерах на смешанные стратегии, нижняя цена оказывается строго меньше верхней. Тогда чистой оптимальной стратегии не существует: любой фиксированный выбор строки или столбца соперник использует против вас, поэтому устойчивый вариант один - играть непредсказуемо, выбирая строки и столбцы случайно с определёнными вероятностями.

Алгоритм решения: сначала седловая точка, потом смешение

Решение матричной игры всегда начинается с одной и той же проверки:

1. Для каждой строки найти минимальный элемент, из этих минимумов взять максимум - это нижняя цена игры (максимин).
2. Для каждого столбца найти максимальный элемент, из этих максимумов взять минимум - это верхняя цена игры (минимакс).
3. Сравнить два числа. Если они равны, седловая точка найдена, игра решается в чистых стратегиях, а их общее значение и есть цена игры.
4. Если нижняя цена меньше верхней, седловой точки нет, и нужно переходить к смешанным стратегиям.

Шаг 4 можно проверить и графически: постройте линии ожидаемого выигрыша A для каждой из двух чистых стратегий как функции от вероятности хода соперника. Если линии пересекаются внутри отрезка [0, 1], их точка пересечения даёт оптимальную вероятность, а высота точки - цену игры.

Рассчитать для своей задачи

Именно это движение объясняет суть графического метода: B хочет опустить как можно ниже верхнюю огибающую двух линий (худший для себя случай), а минимум этой огибающей у пары прямых всегда лежит либо на конце отрезка, либо в точке их пересечения - в примере без седловой точки это всегда пересечение.

Формулы для матричной игры 2x2 без седловой точки

Пусть A играет строку 1 с вероятностью $p$ и строку 2 с вероятностью $1 - p$, а B играет столбец 1 с вероятностью $q$ и столбец 2 с вероятностью $1 - q$. Оптимальные вероятности находятся из условия, что каждому игроку становится безразлично, какую из своих чистых стратегий использовать против оптимальной смеси соперника. Решение этой системы для матрицы 2x2 даёт готовые формулы:

$$p = \frac{a_{22} - a_{21}}{a_{11} - a_{12} - a_{21} + a_{22}}, \qquad q = \frac{a_{22} - a_{12}}{a_{11} - a_{12} - a_{21} + a_{22}},$$ $$v = \frac{a_{11} a_{22} - a_{12} a_{21}}{a_{11} - a_{12} - a_{21} + a_{22}}.$$

Знаменатель во всех трёх формулах один и тот же - назовём его $D = a_{11} - a_{12} - a_{21} + a_{22}$. Если седловой точки нет, $D$ гарантированно отличен от нуля, а получившиеся $p$ и $q$ автоматически попадают в отрезок [0, 1]. Формулы удобны именно тем, что не требуют явного решения системы уравнений на бумаге - достаточно подставить четыре числа матрицы.

Почему цена игры лежит между нижней и верхней ценой

Смешанная цена игры $v$ не берётся из ниоткуда - она всегда зажата между нижней и верхней ценой чистых стратегий:

$$\text{нижняя цена} \le v \le \text{верхняя цена}.$$

Рассчитать для своей задачи

Смысл прост: смешивая стратегии, A не может получить меньше, чем гарантирует самая осторожная чистая стратегия (нижняя цена), но и не может рассчитывать на больше, чем позволяет минимаксная защита B (верхняя цена). Равенство наступает только при седловой точке, когда смешивать уже нечего. Это неравенство - быстрый способ проверить вычисленное $v$: если цена игры выпала за пределы отрезка между нижней и верхней ценой, где-то перепутаны знаки или строки со столбцами.

Геометрический смысл вероятностей p и q

Вероятность $p$ удобно представлять точкой на отрезке от 0 до 1: она делит его на две части - $p$ слева и $1 - p$ справа, - и это отношение определяет, как часто A будет играть каждую из двух строк в длинной серии партий.

Рассчитать для своей задачи

Ту же картину рисуют и для вероятности $q$ игрока B. Смешанная стратегия - это не «случайное блуждание», а посчитанное число: если A отклонится от найденного $p$ в любую сторону, разумный B использует это отклонение и снизит выигрыш A ниже цены игры.

Пример решения матричной игры

Возьмём матрицу

$$A = \begin{pmatrix} 4 & 1 \\ 2 & 3 \end{pmatrix}.$$

Сначала проверяем седловую точку. Минимумы строк: $\min(4, 1) = 1$ и $\min(2, 3) = 2$, максимин равен 2. Максимумы столбцов: $\max(4, 2) = 4$ и $\max(1, 3) = 3$, минимакс равен 3. Нижняя цена (2) меньше верхней (3), значит, седловой точки нет и нужно искать смешанное решение.

Вычисляем знаменатель: $D = 4 - 1 - 2 + 3 = 4$. Тогда

$$p = \frac{3 - 2}{4} = 0{,}25, \qquad q = \frac{3 - 1}{4} = 0{,}5, \qquad v = \frac{4 \cdot 3 - 1 \cdot 2}{4} = \frac{10}{4} = 2{,}5.$$

Проверка: цена игры 2,5 действительно лежит между нижней ценой 2 и верхней ценой 3, как и требует неравенство выше. Значит, A должен играть первую строку с вероятностью 0,25 и вторую с вероятностью 0,75, а B должен играть первый столбец с вероятностью 0,5 и второй тоже с вероятностью 0,5. При такой игре обеих сторон средний выигрыш A за большую серию партий стремится к 2,5.

Частые ошибки

• Пропуск проверки седловой точки. Формулы для $p$, $q$, $v$ подставляют, даже когда в матрице уже есть седловая точка. Знаменатель $D$ тогда может обратиться в ноль или дать вероятности вне [0, 1] - формулы для смешанных стратегий на этот случай не рассчитаны.
• Путаница, какая цена нижняя, а какая верхняя. Нижняя цена - максимин по строкам, верхняя - минимакс по столбцам. Перепутать их - частая ошибка, которая сразу видна по нарушению неравенства нижняя цена $\le$ верхняя цена.
• Неверный знак в знаменателе $D$. Нужно именно $a_{11} - a_{12} - a_{21} + a_{22}$, а не сумма всех четырёх элементов с одним знаком. Ошибка в знаке уводит $p$ и $q$ за пределы [0, 1].
• Игнорирование проверки $p, q \in [0, 1]$. Отрицательное число или число больше единицы значит: либо в матрице есть седловая точка, либо где-то арифметическая ошибка.
• Путаница ролей игроков. A максимизирует по строкам, B минимизирует по столбцам. Перепутав их местами, нижнюю и верхнюю цену посчитают неверно.

FAQ

Как проверить, есть ли седловая точка в матричной игре? Нужно найти максимин (максимум минимумов строк) и минимакс (минимум максимумов столбцов). Если эти два числа равны, седловая точка есть и игра решается в чистых стратегиях; если нижняя цена меньше верхней, седловой точки нет и нужны смешанные стратегии.

Что означает вероятность p в смешанной стратегии? Это не единичный выбор, а доля партий в длинной серии: игрок A должен играть первую строку в долях $p$ случаев и вторую строку в долях $1 - p$ случаев, чтобы сопернику было невыгодно подстраиваться под какую-то одну его чистую стратегию.

Может ли цена игры быть отрицательной? Да, если элементы матрицы содержат отрицательные числа (проигрыш для A). Формулы работают одинаково для любых чисел, знак цены игры просто показывает, в чью пользу смещён средний результат.

Коротко

Решение матричной игры начинается с проверки седловой точки: сравниваются нижняя цена (максимин по строкам) и верхняя цена (минимакс по столбцам). Если они равны, оптимальны чистые стратегии. Если нет, оптимальные вероятности находятся по формулам $p = (a_{22} - a_{21})/D$, $q = (a_{22} - a_{12})/D$ и цена игры $v = (a_{11}a_{22} - a_{12}a_{21})/D$, где $D = a_{11} - a_{12} - a_{21} + a_{22}$. Найденная цена игры всегда лежит между нижней и верхней ценой чистых стратегий, а графический метод показывает то же решение как точку пересечения линий ожидаемого выигрыша.