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

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

Что такое решение в чистых стратегиях

Пусть матрица выигрышей A имеет размер m на n, где $a_{ij}$ - выигрыш игрока A, если он играет строку $i$, а игрок B играет столбец $j$. Игра с нулевой суммой означает, что выигрыш A равен проигрышу B, поэтому B стремится минимизировать то же самое число, которое A стремится максимизировать. Чистая стратегия - это выбор одной конкретной строки (для A) или одного конкретного столбца (для B), который игрок использует всегда, без всякой случайности. Если для такой пары строка-столбец ни одному из игроков не выгодно в одиночку менять свой выбор, это и есть устойчивое решение игры - оно называется седловой точкой, а стоящее в ней число - ценой игры.

Алгоритм: нижняя и верхняя цена игры

Проверка решения в чистых стратегиях всегда начинается с одной и той же процедуры, не требующей никаких вероятностей:

1. Для каждой строки найти минимальный элемент - это худший для A исход, если он выбрал именно эту строку, а B сыграл против него наилучшим образом.
2. Из всех найденных минимумов строк взять максимум. Это нижняя цена игры, или максимин: $\alpha = \max_i \min_j a_{ij}.$
3. Для каждого столбца найти максимальный элемент - худший для B исход в этом столбце.
4. Из всех найденных максимумов столбцов взять минимум. Это верхняя цена игры, или минимакс: $\beta = \min_j \max_i a_{ij}.$

Смысл прост: строка с максимальным минимумом - это самая безопасная стратегия A, при которой он гарантированно получит не меньше $\alpha$, что бы ни делал соперник. Аналогично столбец с минимальным максимумом - самая безопасная стратегия B, при которой он гарантированно отдаст не больше $\beta$.

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

Всегда выполняется неравенство $\alpha \le \beta$: A никогда не может гарантировать себе больше, чем позволяет минимаксная защита B. Если это неравенство обращается в строгое равенство, значит, найдена клетка, которая одновременно является минимумом своей строки и максимумом своего столбца, - именно она и есть седловая точка.

Когда существует седловая точка

Седловая точка существует тогда и только тогда, когда нижняя цена равна верхней: $\alpha = \beta$. В этом случае решение в чистых стратегиях не просто существует - оно единственно устойчиво в следующем смысле. Если A отклонится от строки седловой точки на любую другую, а B продолжит играть свой столбец, выигрыш A может только уменьшиться. Если же отклонится B, а A останется на месте, проигрыш B может только увеличиться. Поэтому обеим сторонам невыгодно менять свой выбор в одиночку - ровно это и требуется от устойчивого решения игры. Цена игры $v = \alpha = \beta$ показывает, сколько A получит от B при разумной игре обеих сторон, и это число не зависит от того, знает ли соперник заранее вашу стратегию: седловая точка устойчива к разглашению.

Если же $\alpha < \beta$, седловой точки нет вообще, ни в одной клетке матрицы, и чистой оптимальной стратегии не существует: любой фиксированный выбор строки соперник рано или поздно раскроет и подстроится под него. В таком случае переходят к решению в смешанных стратегиях, где игроки чередуют ходы случайно с расчётными вероятностями.

Метод доминирования: как упростить большую матрицу

Прежде чем вручную искать минимумы строк и максимумы столбцов в большой матрице, её часто удаётся сократить методом доминирования. Строка $i$ доминирует строку $k$, если каждый элемент строки $i$ не меньше соответствующего элемента строки $k$: тогда A никогда не выгодно играть строку $k$, её можно вычеркнуть. Симметрично столбец $j$ доминирует столбец $l$, если каждый элемент столбца $j$ не больше соответствующего элемента столбца $l$: тогда B никогда не выгодно играть столбец $l$, его тоже вычёркивают. Цена игры при этом не меняется - доминируемые строки и столбцы попросту никогда не входят в оптимальную стратегию ни одного из игроков.

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

На схеме видно, как матрица $\begin{pmatrix} 5 & 3 & 6 \\ 2 & 1 & 3 \\ 7 & 4 & 8 \end{pmatrix}$ сжимается шаг за шагом. Строка 2 вычеркивается первой: каждый её элемент не больше соответствующего элемента строки 3, значит A всегда предпочтёт строку 3. Дальше сравниваются столбцы оставшихся двух строк: второй столбец (3, 4) поэлементно не больше первого (5, 7) и третьего (6, 8), поэтому оба вычёркиваются. Остаётся один столбец с двумя числами 3 и 4 - A выбирает строку с большим значением, и матрица схлопывается до единственного ответа: седловая точка в клетке строка 3, столбец 2 со значением 4. Метод доминирования особенно полезен для матриц 4 на 4 и крупнее, где перебор всех строк и столбцов вручную занимает много времени.

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

Возьмём матрицу выигрышей

$$A = \begin{pmatrix} 3 & 2 & 4 \\ 6 & 5 & 7 \\ 8 & 4 & 9 \end{pmatrix}.$$

Находим минимум каждой строки: $\min(3, 2, 4) = 2$, $\min(6, 5, 7) = 5$, $\min(8, 4, 9) = 4$. Нижняя цена - максимум из этих чисел: $\alpha = \max(2, 5, 4) = 5$, достигается во второй строке.

Находим максимум каждого столбца: $\max(3, 6, 8) = 8$, $\max(2, 5, 4) = 5$, $\max(4, 7, 9) = 9$. Верхняя цена - минимум из этих чисел: $\beta = \min(8, 5, 9) = 5$, достигается во втором столбце.

Поскольку $\alpha = \beta = 5$, седловая точка найдена: это клетка на пересечении второй строки и второго столбца, $a_{22} = 5$. Проверим определение напрямую: в строке $(6, 5, 7)$ число 5 действительно минимально, а в столбце $(2, 5, 4)$ число 5 действительно максимально - оба условия выполнены одновременно, значит клетка и правда седловая. Значит, игроку A достаточно всегда играть вторую строку, игроку B - всегда второй столбец, а цена игры равна 5: именно столько A будет получать от B при любой стратегии соперника, если сам не отклонится от найденной строки.

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

• Путаница, что берётся первым - минимум или максимум. Для строк сначала берут минимум (худший исход A), а из этих минимумов - максимум. Для столбцов наоборот: сначала максимум (худший исход B), а из этих максимумов - минимум. Перепутанный порядок сразу даёт неверные числа.
• Остановка после первого совпадающего числа. Нужно сравнивать именно посчитанные нижнюю и верхнюю цену игры целиком, а не одну случайно совпавшую пару элементов - седловая клетка обязана быть одновременно минимумом своей строки и максимумом своего столбца, оба условия проверяются отдельно.
• Применение доминирования с нестрогим неравенством не в ту сторону. Строка доминируется, если она не лучше другой строки в каждой клетке; попытка вычеркнуть строку, которая лучше хотя бы в одной клетке, разрушает решение.
• Поиск седловой точки в игре, где её нет. Если после подсчёта нижняя цена оказалась строго меньше верхней, седловой точки нет ни в одной клетке - дальнейшая ручная проверка клеток бессмысленна, нужно переходить к смешанным стратегиям.
• Путаница ролей игроков. A выбирает строку и максимизирует число в клетке, B выбирает столбец и минимизирует то же число. Перепутав, кто есть кто, нижнюю и верхнюю цену игры считают наоборот.

FAQ

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

Может ли седловых точек быть несколько? Да, если несколько клеток одновременно являются минимумом своей строки и максимумом своего столбца, все они дают одну и ту же цену игры. Игроку достаточно выбрать любую из них - результат не изменится.

Что делать, если после доминирования матрица не сжимается до одной клетки? Значит, доминируемых строк или столбцов больше нет, но матрица всё ещё больше 1 на 1. Тогда нужно напрямую посчитать нижнюю и верхнюю цену игры для оставшейся матрицы; если они не совпадут, решение придётся искать в смешанных стратегиях.

Коротко

Решение матричной игры в чистых стратегиях начинается с расчёта нижней цены (максимин по минимумам строк) и верхней цены (минимакс по максимумам столбцов). Если они равны, найдена седловая точка - клетка, которая одновременно минимальна в своей строке и максимальна в своём столбце, а её значение и есть цена игры. Метод доминирования позволяет заранее вычеркнуть заведомо невыгодные строки и столбцы и сократить перебор в больших матрицах. Если нижняя цена оказалась строго меньше верхней, чистой оптимальной стратегии не существует, и решение нужно искать среди смешанных стратегий.