♟️ Теория игр

Максимин и минимакс

Q: Почему максимин не превышает минимакс?

Возьмём любой столбец $j'$. Каждый строковый минимум не больше любого элемента своей строки, в частности элемента столбца $j'$, поэтому и наибольший из минимумов не превосходит максимума этого столбца. Минимизируя по всем столбцам, получаем $\max_i \min_j a_{ij} \le \min_j \max_i a_{ij}$. Неравенство грубое и не требует вычислений сверх перебора — этим оно и удобно для быстрой оценки.

англ. Maximin and minimax

Гарантийные цены игры: максимин — наибольший из минимумов строк, минимакс — наименьший из максимумов столбцов; между ними лежит цена игры.

Играя строку $i$ , игрок A гарантированно получает её минимум $min_{j} a_{ij}$ — худший ответ B. Лучшая из таких гарантий — максимин $\underline{v} = max_{i} min_{j} a_{ij}$ , нижняя цена игры, а строка-рекордсмен — максиминная стратегия. Симметрично B ограничивает свой проигрыш: столбец с наименьшим из столбцовых максимумов $\overline{v} = min_{j} max_{i} a_{ij}$ — это минимакс и верхняя цена игры. Обе величины — цены осторожности, принцип гарантированного результата.

Всегда $\underline{v} \leq \overline{v}$ . Для $A = (4213)$ строковые минимумы равны $1$ и $2$ , значит $\underline{v} = 2$ ; столбцовые максимумы равны $4$ и $3$ , значит $\overline{v} = 3$ . Разрыв $\overline{v} - \underline{v} = 1$ показывает, что седла нет и предсказуемость наказуема; смешанные стратегии закрывают щель и дают цену $v = 2, 5$ . В играх с природой те же идеи превращаются в критерии выбора — см. урок критерии принятия решений; базовые определения — в материале игры с чистыми стратегиями.

\underline{v} = i max j min a_{ij} \leq \overline{v} = j min i max a_{ij}

нижняя и верхняя цены игры; равенство выполняется тогда и только тогда, когда в матрице есть седловая точка

Частые вопросы

Почему максимин не превышает минимакс?

Возьмём любой столбец $j^{'}$ . Каждый строковый минимум не больше любого элемента своей строки, в частности элемента столбца $j^{'}$ , поэтому и наибольший из минимумов не превосходит максимума этого столбца. Минимизируя по всем столбцам, получаем $max_{i} min_{j} a_{ij} \leq min_{j} max_{i} a_{ij}$ . Неравенство грубое и не требует вычислений сверх перебора — этим оно и удобно для быстрой оценки.

О чём говорит разрыв между нижней и верхней ценой?

О неустойчивости чистых стратегий: седловой точки нет, и осторожные цены расходятся. Кто ходит предсказуемо, получает лишь свою нижнюю цену; соперник, зная выбор, забирает разницу. Случайное смешивание переводит конфликт в средние величины и сжимает щель до цены игры $v$ , лежащей между $\underline{v}$ и $\overline{v}$ — в примере это ровно $2, 5$ .