Как найти нижнюю цену игры: разбор матрицы 3 на 4

Дано: платёжная матрица 3 на 4, строки - стратегии игрока A, столбцы - стратегии игрока B: 5 3 8 2; 7 6 4 9; 4 5 6 3. Найти: нижнюю и верхнюю цену игры, проверить наличие седловой точки.

Нижняя цена ищется по строкам: в каждой строке берётся минимум, а из этих минимумов - максимум. Минимумы строк здесь равны 2, 4 и 3, наибольший из них 4. Ответ: нижняя цена игры $\alpha = 4$ и достигается на строке $A_2$, верхняя цена $\beta = 6$ на столбце $B_2$; цены не совпали, седловой точки нет, и цена игры лежит между 4 и 6. Калькулятор сверху считает обе цены под любые свои числа.

Решение по шагам

Дано. Платёжная матрица $A = (a_{ij})$, где $a_{ij}$ - выигрыш игрока A, если он выбрал строку $A_i$, а игрок B ответил столбцом $B_j$. Сумма игры нулевая: сколько получает A, столько теряет B.

Шаг 1. Минимум каждой строки. В строке $A_1$ числа 5, 3, 8, 2, минимальное из них 2. В строке $A_2$ числа 7, 6, 4, 9, минимум равен 4. В строке $A_3$ числа 4, 5, 6, 3, минимум равен 3. Каждое из этих чисел показывает, сколько получит A, если выберет данную строку и нарвётся на самый неудобный для себя ответ соперника.

Шаг 2. Максимум из минимумов - нижняя цена. Из трёх гарантий 2, 4 и 3 игрок A выберет самую большую:

$$\alpha = \max_i \min_j a_{ij} = \max(2,\ 4,\ 3) = 4.$$

Максимум достигается на строке $A_2$, поэтому $A_2$ и есть максиминная стратегия игрока A.

Шаг 3. Максимум каждого столбца. Теперь те же рассуждения для соперника. В столбце $B_1$ числа 5, 7, 4, максимум 7. В столбце $B_2$ числа 3, 6, 5, максимум 6. В столбце $B_3$ числа 8, 4, 6, максимум 8. В столбце $B_4$ числа 2, 9, 3, максимум 9. Столбцовый максимум - это худший для B исход при выбранном им столбце, ведь B платит и хочет отдать поменьше.

Шаг 4. Минимум из максимумов - верхняя цена.

$$\beta = \min_j \max_i a_{ij} = \min(7,\ 6,\ 8,\ 9) = 6.$$

Минимум достигается на столбце $B_2$, значит минимаксная стратегия игрока B - это $B_2$.

Шаг 5. Сравнение цен. Получилось $\alpha = 4 < \beta = 6$. Значит, ни одна клетка матрицы не является одновременно минимумом своей строки и максимумом своего столбца, седловой точки нет и решения в чистых стратегиях не существует.

Ответ: нижняя цена игры $\alpha = 4$ на стратегии $A_2$, верхняя цена $\beta = 6$ на стратегии $B_2$, седловой точки нет, цена игры удовлетворяет неравенству $4 \le v \le 6$.

Формула нижней цены и что она гарантирует

Формула $\alpha = \max_i \min_j a_{ij}$ читается изнутри наружу, и порядок операций в ней не случаен. Внутренний минимум описывает пессимистичный взгляд: игрок A предполагает, что соперник разгадал его выбор строки и ответил наихудшим для A столбцом. Внешний максимум - это уже выбор самого A: из всех пессимистичных сценариев он берёт наименее плохой.

Отсюда и смысл слова «гарантия». Выбрав строку $A_2$, игрок A получит не меньше 4 при любом поведении соперника: в этой строке просто нет чисел меньше четырёх. Ни одна другая строка такой планки не даёт - у $A_1$ гарантия всего 2, у $A_3$ она равна 3. Поэтому нижнюю цену часто называют гарантированным выигрышем: это максимум того, что A может себе обеспечить в одиночку, не рассчитывая на ошибки соперника.

Верхняя цена симметрична и читается с другой стороны стола. Выбрав столбец $B_2$, игрок B отдаст не больше 6 при любой строке соперника, и ни один другой столбец не удерживает потери ниже. Поэтому $\beta$ - это гарантированный потолок проигрыша B.

Из определений сразу следует и главное неравенство теории матричных игр: $\alpha \le v \le \beta$, где $v$ - истинная цена игры при разумном поведении обеих сторон. Нижняя цена никогда не превосходит верхнюю, и если при расчёте вышло наоборот, значит где-то перепутаны минимум и максимум. Это самая быстрая проверка работы.

Та же максиминная логика встречается и вне игр двух лиц: критерий Вальда в задаче на матрицу рисков - это ровно $\max_i \min_j a_{ij}$, только вторым игроком там выступает природа, которая ничего не выбирает осознанно, и потому верхняя цена и седловая точка в таких задачах не рассматриваются.

Проверка: когда нижняя цена совпадает с верхней

Возьмём другую матрицу, чтобы увидеть второй исход той же процедуры:

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

Минимумы строк равны 6, 4 и 3, нижняя цена $\alpha = 6$ на строке $A_1$. Максимумы столбцов равны 9, 6 и 8, верхняя цена $\beta = 6$ на столбце $B_2$. Цены совпали, и клетка на их пересечении $a_{12} = 6$ и есть седловая точка: число 6 минимально в своей строке и максимально в своём столбце одновременно.

Проверять это стоит именно по паре условий, а не по совпадению цен на глаз. Если клетка прошла обе проверки, решение готово: A всегда играет $A_1$, B всегда играет $B_2$, цена игры $v = 6$. Такое решение устойчиво к разглашению - сопернику можно заранее сообщить свою стратегию, и ему всё равно не станет выгоднее менять свою. Полный разбор этого случая вместе с методом доминирования разобран в статье про решение матричной игры в чистых стратегиях.

Если нижняя цена меньше верхней

В исходной задаче разрыв между 4 и 6 означает, что фиксированная строка игрока A невыгодна: как только соперник заметит закономерность, он подстроится и сдвинет результат к 4. Выход - чередовать строки случайно с рассчитанными вероятностями, то есть перейти к смешанным стратегиям. Цена игры тогда окажется строго внутри найденного коридора, и посчитанные $\alpha$ и $\beta$ работают проверкой ответа: получилось значение вне отрезка от 4 до 6 - значит, ошибка в вычислениях.

Перед переходом матрицу пробуют сжать доминированием, вычеркнув заведомо невыгодные строки и столбцы; в нашей матрице ни одна строка не хуже другой во всех четырёх клетках, поэтому сжать её не удаётся и задача решается симплекс-методом или графически. А вот для игры 2 на 2 ответ выписывается формулами. Для матрицы со строками 4 1 и 2 5 нижняя цена равна 2, верхняя 4, седловой точки нет, и цена игры считается так:

$$v = \frac{a_{11}a_{22} - a_{12}a_{21}}{a_{11} + a_{22} - a_{12} - a_{21}} = \frac{4 \cdot 5 - 1 \cdot 2}{4 + 5 - 1 - 2} = \frac{18}{6} = 3.$$

Значение 3 действительно попало между 2 и 4, как и требует неравенство. Вероятности первой строки и первого столбца получаются равными $1/2$ и $2/3$; как выводятся эти формулы, показано в разборе смешанных стратегий матричной игры.

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

• Перепутан порядок операций. Для строк сначала берут минимум и только потом максимум из них; для столбцов наоборот. Максимум из максимумов строк даёт число 9 и не имеет отношения к цене игры.
• Минимумы ищут по столбцам, а максимумы по строкам. Строки принадлежат тому, кто выигрывает и максимизирует, столбцы - тому, кто платит и минимизирует. Поменяв роли местами, получают $\alpha = 6$ и $\beta = 4$, то есть заведомо невозможное $\alpha > \beta$.
• Вместо нижней цены выписывают номер строки. Ответ на вопрос о нижней цене - это число 4, а $A_2$ лишь указывает, где оно достигается. В контрольной требуют и то, и другое, но путать их нельзя.
• Седловую точку ищут перебором клеток до расчёта цен. Если $\alpha < \beta$, ни одна клетка условию не удовлетворяет, и перебор бессмысленен. Расчёт двух чисел закрывает вопрос быстрее.
• Матрица задана проигрышами A, а считают как выигрыши. Если в условии сказано «матрица потерь» или «затраты», роли максимизации и минимизации меняются местами, и формула нижней цены записывается для другого игрока.
• Теряется знак у отрицательных выигрышей. Минимум строки с числами 5 и минус 2 равен минус 2, а не 2; в играх с отрицательными клетками на этом ошибаются чаще всего.

FAQ

Чем нижняя цена отличается от цены игры? Нижняя цена - это гарантия игрока A при чистых стратегиях, а цена игры $v$ - результат при оптимальной игре обеих сторон, возможно, со смешанными стратегиями. Они совпадают только при наличии седловой точки; в остальных случаях $\alpha$ строго меньше $v$.

Может ли нижняя цена оказаться больше верхней? Нет, неравенство $\alpha \le \beta$ выполняется для любой матрицы. Если расчёт дал обратное, перепутаны строки со столбцами или минимум с максимумом; это надёжный признак арифметической ошибки.

Что делать, если максимум из минимумов достигается сразу на двух строках? Нижняя цена от этого не меняется, а у игрока A появляется две равноценные максиминные стратегии. В ответе указывают обе, а если дальше ищется седловая точка, проверяют каждую из них отдельно.

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

Коротко

1. Для каждой строки найти минимум - это гарантированный выигрыш соответствующей стратегии игрока A.
2. Нижняя цена $\alpha = \max_i \min_j a_{ij}$ - наибольший из минимумов строк; в примере $\max(2, 4, 3) = 4$ на строке $A_2$.
3. Верхняя цена $\beta = \min_j \max_i a_{ij}$ - наименьший из максимумов столбцов; в примере $\min(7, 6, 8, 9) = 6$ на столбце $B_2$.
4. Совпали цены - есть седловая точка и решение в чистых стратегиях; не совпали - решение ищется в смешанных стратегиях, а цена игры лежит между $\alpha$ и $\beta$.
5. Ответ примера: $\alpha = 4$, $\beta = 6$, седловой точки нет, $4 \le v \le 6$.