Чистые стратегии и седловая точка: максимин и минимакс матрицы

Маркетологи двух сетей кофеен посчитали ожидаемый прирост выручки (в миллионах) для каждой пары решений: сеть A открывает точку в одном из трёх районов, сеть B в тот же сезон выбирает свой. Таблица лежит перед вами. Брать максимум по всей матрице? Наивно: клетка, жирная для A, болото для B — и B сделает всё, чтобы туда не пойти. Игры считаются по другому правилу, которое называют принципом осторожности. Во введении в теорию игр мы договорились, что игра — это конфликт с числами; теперь эти числа считаем.

Как гарантировать себе лучший из худших исходов?#

Игрок A максимизирует выигрыш. Выбрав строку, он не контролирует столбец — значит, рассчитывать нужно на худший столбец этой строки. Минимум строки — гарантия A при этой стратегии. Лучшая из таких гарантий — нижняя цена игры $\alpha$:

Игрок B зеркален: он минимизирует выигрыш A. Выбрав столбец, B готовится к худшей для себя строке — максимуму столбца. Лучшая из таких верхних границ — верхняя цена игры $\beta$:

Здесь $a_{ij}$ — элемент платёжной матрицы (выигрыш A), $i$ пробегает строки, $j$ — столбцы. Алгоритм для A: «сначала минимум по строке, потом максимум между строками». Для B: «сначала максимум по столбцу, потом минимум между столбцами». Порядок операций и есть максимин/минимакс — перепутать их легче, чем кажется, поэтому ниже есть целый раздел про ошибки.

1. Выпишите матрицу выигрышей: строки за A, столбцы за B, в клетках — выигрыши A.
2. Проверьте доминирование и вычеркните строки и столбцы, которые никто не сыграет.
3. Посчитайте минимум каждой строки; максимум из них — это $\alpha$, нижняя цена.
4. Посчитайте максимум каждого столбца; минимум из них — это $\beta$, верхняя цена.
5. Сравните: $\alpha =\beta$ — назовите седловую клетку и цену игры; $\alpha <\beta$ — чистых стратегий мало, идите за смешанными.

Что если осторожность сходится? Матрица 3×3 с седловой точкой#

Считаем честно. Минимумы строк: $2$, $2$, $4$ — A может гарантировать себе максимум $\alpha =4$ (третья строка). Максимумы столбцов: $5$, $5$, $4$ — B удержит A не выше $\beta =4$ (третий столбец). Границы сошлись: $\alpha =\beta =4$. Клетка $a_{33}=4$ — минимум своей строки (среди $5,4,4$) и максимум своего столбца (среди $2,3,4$) одновременно. Это седловая точка, а $v=\alpha =\beta =4$ — цена игры.

Что это значит содержательно. Сеть A, открыв точку по третьей строке, гарантирует себе не меньше 4 млн при любом выборе B. Сеть B третьим столбцом гарантирует, что A получит не больше 4 млн. Отходить от этих стратегий невыгодно отклонившемуся: A, сместившись, рискует получить и $2$; B, сместившись, рискует отдать и $5$. Пара чистых стратегий, приводящая в седловую точку, — чистые оптимальные стратегии. Седловых клеток может быть несколько, но цена у них всегда одна.

Число $v$ называют также значением игры: это справедливая ставка. Если A и B сыграют много раз, каждый своей чистой оптимальной стратегией, средний выигрыш A будет прижиматься к $v$ — не выше по воле B и не ниже по воле A. Любопытно, что для игрока с гарантированной четвёркой «рискованные» строки с пятёрками бессмысленны: их лучший исход зависит от доброй воли соперника, а гарантия у них хуже.

Когда седловой точки нет?#

Сменим раскладку маркетологов — и осторожность перестанет сходиться:

Минимумы строк: $-3$, $-2$, $-4$, значит $\alpha =-2$ (вторая строка). Максимумы столбцов: $3$, $5$, $6$, значит $\beta =3$ (первый столбец). Ни одна клетка не является одновременно минимумом строки и максимумом столбца — седловой точки нет, и $\alpha <\beta$: гарантия A ($-2$) строго хуже потолка B ($3$). Разрыв в пять единиц — место, где живут смешанные стратегии: как их считать — сюжет следующего урока.

Почему α ≤ β всегда?#

Это не совпадение, а механика. Возьмём любую строку $i$ и любой столбец $j$. Минимум строки $i$ не превышает её элемента $a_{ij}$, а тот не превышает максимума столбца $j$. Значит, любая гарантия A не больше любого потолка B — в том числе $\alpha \le \beta$. Равенство — это и есть седловая точка. Если при подсчёте вышло $\alpha >\beta$ — где-то арифметика сломалась, перепроверяйте минимумы и максимумы.

Доминирование: как урезать матрицу перед решением?#

Перед поиском цен матрицу полезно почистить. Строка $i$ доминирует строку $k$, если в каждом столбце её элемент не меньше ($a_{ij}\ge a_{kj}$), а хотя бы в одном — строго больше: при любом ответе B она даёт A не меньше. Доминируемую строку A играть никогда не станет — вычёркиваем. Для B логика перевёрнута: столбец $j$ доминирует столбец $l$, если его элементы не больше, — B любит маленькие числа. Вернёмся к матрице 1.

Третья строка $(5,4,4)$ против второй $(4,2,3)$: $5\ge 4$, $4\ge 2$, $4\ge 3$ — вторая строка доминируется, вычёркиваем. В остатке третий столбец $(2,4)$ против первого $(3,5)$: каждый элемент меньше — первый столбец доминируется, вычёркиваем. Осталась матрица $2\times 2$ со строками $A_1,A_3$ и столбцами $B_2,B_3$:

$\alpha =4$, $\beta =4$, седло в $a_{33}$ — ровно тот же ответ, что и до сокращений. Доминирование не меняет цену игры, зато экономит силы: вместо $3\times 3$ вы решаете $2\times 2$, а иногда остаётся одна строка и ответ очевиден. Пример с двумя удалениями сразу: матрица со строками $(2,4,3)$, $(2,3,4)$, $(3,5,4)$. Третья строка $(3,5,4)$ не хуже первой ($3\ge 2$, $5\ge 4$, $4\ge 3$) и не хуже второй ($3\ge 2$, $5\ge 3$, $4\ge 4$) — вычёркиваем обе, остаётся $(3,5,4)$, B выбирает столбец с тройкой: $v=3$. Прямой счёт подтверждает: минимумы строк $2,2,3$ дают $\alpha =3$; максимумы столбцов $3,5,4$ дают $\beta =3$; седло — в третьей строке первого столбца.

Оговорка про строгость. Строгое доминирование (все сравнения строгие) позволяет вычёркивать смело. При слабом доминировании — как во втором примере, где было равенство $4\ge 4$ — цена игры сохраняется, но часть альтернативных решений может потеряться. Для учебных задач это не страшно; в серьёзных исследованиях разницу помнят.

Где теряют баллы: типичные ошибки#

• Максимин по столбцам вместо строк. Минимум по столбцу и максимум между столбцами — это $\beta$, вы посчитали цену за B. Запоминалка: A ходит по строкам — значит, и максимин идёт по строкам.
• Забыть, что B минимизирует. В строке «max по столбцу» B выбирает не наибольший столбец, а наименьший потолок.
• Искать седло как экстремум всей матрицы. Седловая точка — свойство клетки относительно её строки и столбца. В матрице 1 седловое значение $4$ — вовсе не максимум таблицы: в ней есть и $5$.
• Потерять номера стратегий после сокращений. Если вычеркнули строки 1 и 2, «оставшаяся первая строка» — исходная $A_3$. Ответ пишут в исходных стратегиях.
• Пугаться отрицательных выигрышей. Знак — это направление перевода денег, а не опечатка: проигрыш A в матричной игре встречается постоянно.

Что дальше. Если $\alpha =\beta$ — игра уже решена: назовите седловую клетку и цену. Если $\alpha <\beta$ — чистые стратегии дают лишь вилку, и её сужают вероятности: в следующем уроке считаем смешанные стратегии и решаем игру «пенальти» до конца. Для задач, где второй игрок не борется с вами, а просто случается (погода, спрос), есть отдельная линейка методов — игры с природой: критерии Вальда, Сэвиджа, Гурвица, Байеса. Матричную технику освежите по теме матрицы и операции или в словаре про матрицу, а руками потренируйтесь в тренажёре матриц.