Задачи на матричную игру 2×2

Матричная игра 2×2 — самая компактная модель конфликта: у каждого из двух игроков по две стратегии, выигрыши первого заданы матрицей $2\times 2$, второй получает то же самое со знаком минус (игры с нулевой суммой). Вопрос задачи звучит всегда одинаково: как играть рационально и сколько это стоит? Тема — прикладное ядро курса теории игр: базовые понятия — в уроке введение в теорию игр, сам термин — в матричная игра.

Рациональность здесь означает осторожность: каждый игрок считает, что противник сыграет наихудшим для него образом, и максимизирует гарантированный выигрыш. Для первого игрока это нижняя цена игры $\alpha$ — лучшее из худших по строкам; для второго — верхняя цена $\beta$ — худшее из лучших по столбцам. Если $\alpha =\beta$, у игры есть седловая точка, и решение — пара чистых стратегий. Если нет, чистые стратегии бессильны: игрок обязан тасовать свои ходы случайно — это смешанные стратегии, и вся арифметика 2×2 сводится к трём формулам.

Жанр любит коварные матрицы: без седловой точки, с отрицательными элементами, с доминируемыми стратегиями, которые нужно вычеркнуть до всего остального. Разберём оба случая — с седловой точкой и без неё — и соберём набор проверок, который ловит почти все арифметические промахи. Смежный сюжет про выбор в условиях неопределённости без противника — в уроке критерии принятия решений.

Классификация: 4 случая#

Метод: от матрицы к вероятностям#

1. 1
   Выпишите платёжную матрицу и проверьте доминирование: строка, построчно не лучше другой, вычёркивается — то же со столбцами для второго игрока.
2. 2
   Найдите нижнюю цену $\alpha ={\max }_i{\min }_j{a}_{ij}$: минимум в каждой строке, максимум из них.
3. 3
   Найдите верхнюю цену $\beta ={\min }_j{\max }_i{a}_{ij}$: максимум в каждом столбце, минимум из них.
4. 4
   Если $\alpha =\beta$ — седловая точка: чистые стратегии и цена $v$. Задача решена.
5. 5
   Если $\alpha <\beta$: посчитайте $\Delta =a_{11}+a_{22}-a_{12}-a_{21}$; при $\Delta \ne 0$ примените формулы смешанных стратегий.
6. 6
   Проверьте ответ: цена игры должна лежать между $\alpha$ и $\beta$, вероятности — быть положительными и давать в сумме единицу, ожидаемые выигрыши против обеих стратегий противника — совпадать с $v$.

Разобранный пример 1: седловая точка#

Платёжная матрица первого игрока: $A=\left(\begin{array}{cc}4& 5\\ 3& 2\end{array}\right)$. Найти решение игры. Начинаем с цен — возможно, смешивать стратегии не придётся.

1. 1
   Минимумы строк: $\min (4,5)=4$, $\min (3,2)=2$. Нижняя цена $\alpha =\max (4,2)=4$.
2. 2
   Максимумы столбцов: $\max (4,3)=4$, $\max (5,2)=5$. Верхняя цена $\beta =\min (4,5)=4$.
3. 3
   $\alpha =\beta =4$ — седловая точка на пересечении строки 1 и столбца 1: $a_{11}=4$ одновременно минимум своей строки и максимум своего столбца.
4. 4
   Решение: первый играет первую стратегию, второй — первую, цена игры $v=4$.
5. 5
   Смысл: второму невыгодно уходить из первого столбца — иначе он платит 5; первому невыгодно менять строку — гарантия упадёт до 2.

Разобранный пример 2: смешанные стратегии#

Матрица $A=\left(\begin{array}{cc}2& 3\\ 4& 1\end{array}\right)$. Здесь осторожность первого игрока даёт $\alpha =\max (2,1)=2$, осторожность второго — $\beta =\min (4,3)=3$. Границы не совпали: седловой точки нет, чистые стратегии не оптимальны — переходим к смешанным.

1. 1
   $\Delta =a_{11}+a_{22}-a_{12}-a_{21}=2+1-3-4=-4$.
2. 2
   Определитель: $a_{11}{a}_{22}-a_{12}{a}_{21}=2\cdot 1-3\cdot 4=-10$. Цена игры $v=\frac{-10}{-4}=2,5$ — действительно между $\alpha =2$ и $\beta =3$.
3. 3
   Стратегия первого: $p_1=\frac{a_{22}-a_{21}}{\Delta }=\frac{1-4}{-4}=\frac{3}{4}$, значит $p_2=\frac{1}{4}$.
4. 4
   Стратегия второго: $q_1=\frac{a_{22}-a_{12}}{\Delta }=\frac{1-3}{-4}=\frac{1}{2}$, значит $q_2=\frac{1}{2}$.
5. 5
   Проверка равновесия: против первого столбца первый получает $2\cdot \frac{3}{4}+4\cdot \frac{1}{4}=2,5$; против второго $3\cdot \frac{3}{4}+1\cdot \frac{1}{4}=2,5$. Совпало — противнику нет способа ухудшить результат.

Типичные ошибки#

• Переходят к смешанным стратегиям, не проверив седловую точку.
• Путают $\Delta$ с определителем матрицы: $\Delta$ — разность сумм диагоналей, определитель — $a_{11}{a}_{22}-a_{12}{a}_{21}$.
• Отрицательную вероятность «чинят» сменой знака вместо пересчёта формул.
• Забывают, что матрица платит первому игроку: второй игрок минимизирует, а не максимизирует.
• Не проверяют сумму вероятностей и совпадение ожидаемых выигрышей — главные бесплатные проверки.

Проверьте себя#

Что смотреть дальше#

1. Чистые стратегии и седловые точки — урок чистые стратегии в играх.
2. Смешанные стратегии в общем виде — урок смешанные стратегии.
3. Термины с определениями — цена игры, максимин и минимакс, смешанная стратегия.
4. Классическая модель конфликта — термин дилемма заключённого.
5. Упрощение матриц — термин доминирование стратегий.
6. Матричная техника для вычислений — тип задач матрицы и тренажёр матриц.

Пример на смешанные стратегии с числами: матрица $\left(\begin{array}{cc}3& -1\\ & \\ -2& 4\end{array}\right)$. Максимин $\alpha =\max (-2,-1)=-1$, минимакс $\beta =\min (3,4)=3$: седловой точки нет, играется смесь. Доля первой строки для игрока A: $p=\frac{4-(-2)}{3+4-(-1)-(-2)}=\frac{6}{10}=0,6$. Цена игры $v=\frac{3\cdot 4-(-1)(-2)}{10}=\frac{10}{10}=1$. Проверка: при реакции B первым столбцом выигрыш A равен $0,6\cdot 3+0,4\cdot (-2)=1$; при втором — $0,6\cdot (-1)+0,4\cdot 4=1$. Обе реакции дают одно и то же — смесь неуязвима, решение верное.