Минимакс-теорема и её расширения

Фундаментальный факт: оба игрока «знают» оптимальное значение

В 1928 году Джон фон Нейман доказал поразительный факт: в любой матричной игре с нулевой суммой есть «равновесие». Минимизатор не может «ухудшить» результат ниже некоторого значения V, а максимизатор не может поднять его выше того же V. Это значение V — «цена игры». Теорема минимакса — это математическое обоснование того, почему рациональные игроки с противоположными интересами придут к предсказуемому результату.

Теорема минимакса Неймана

Для матрицы выплат A ∈ ℝ^{m×n}:

max_{x∈Δₘ} min_{y∈Δₙ} xᵀAy = min_{y∈Δₙ} max_{x∈Δₘ} xᵀAy

где Δₖ — стандартный симплекс смешанных стратегий (вероятностное распределение на k чистых стратегиях).

Смысл: максимальный «гарантированный» выигрыш игрока 1 = минимальный «гарантированный» проигрыш игрока 2. Это значение называется ценой игры.

Доказательство через ЛП: задача max_x min_y xᵀAy — это ЛП (можно ввести переменную v = min_y xᵀAy). Сильная двойственность ЛП → равенство min = max.

Равновесие Нэша в матричных играх

Профиль стратегий (x*, y*) — Nash Equilibrium, если:

x* оптимальна при y*: xᵀAy* ≤ xᵀAy для всех x ∈ Δₘ
y* оптимальна при x*: xᵀAy ≤ xᵀAy* для всех y ∈ Δₙ... нет, наоборот для максимизатора

Для нулевой суммы: (x*, y*) — NE тогда и только тогда, когда xᵀAy — значение игры.

Алгоритм нахождения: записываем как ЛП. Обе задачи — ЛП, сильная двойственность.

Расширение на дифференциальные игры

При выполнении условия Айзекса (saddle point condition для H*):

min_{u(·)} max_{v(·)} J(x₀; u, v) = max_{v(·)} min_{u(·)} J(x₀; u, v) = V(x₀)

Это «теорема минимакса» в непрерывном времени. Доказательство (Evans-Souganidis, 1984): через теорию вязкостных решений HJI.

Стратегии обратной связи vs разомкнутые

Важный факт: для нулевых игр с фиксированными стратегиями — разница!

Разомкнутые стратегии: u = u(t), v = v(t) (до игры фиксируются). «Открытый» порядок ходов:

min_u max_v J vs max_v min_u J — могут не совпадать!

Стратегии обратной связи: u = α(x,t), v = β(x,t). При условии Айзекса: min max = max min = V(x₀). Стратегии обратной связи «обходят» проблему порядка ходов.

Пример: игра в монетки. Рассмотрим дискретную версию: A = [[1, -1], [-1, 1]] (нет чистого NE!). Смешанное равновесие: x* = y* = (1/2, 1/2). Значение игры = 0. Это подтверждает: в любой матричной игре с нулевой суммой есть смешанное NE.

LQ-дифференциальные игры

Линейно-квадратичная (LQ) игра: идеальный случай для явных решений.

ẋ = Ax + Bu + Cv, J = xᵀ(T)Gx(T) + ∫₀ᵀ [xᵀQx + uᵀRu − vᵀSv] dt

(минус перед vᵀSv: E хочет увеличить расход управления)

Решение: оптимальные стратегии линейны:

u*(t) = −R⁻¹Bᵀ P(t) x(t), v*(t) = S⁻¹Cᵀ P(t) x(t)

где P(t) удовлетворяет уравнению Риккати-Айзекса (матричное ОДУ):

Ṗ + AᵀP + PA + Q − PBR⁻¹BᵀP + PCS⁻¹CᵀP = 0, P(T) = G

Это уравнение 2-го порядка (содержит P² членов), в отличие от линейного Риккати для обычного LQ-управления.

Полный разбор: LQ-игра 1D

Задача: ẋ = u + v, x(0) = 1, J = x(T)² + ∫₀ᵀ [u² − v²] dt (T = 1).

Уравнение Риккати-Айзекса: Ṗ = −P² · 1 + P² · 1 = 0 → P = const. P(T) = 1 (терминальный вклад). Значит P(t) = 1 для всех t!

Оптимальные стратегии: u*(t) = −P(t)x(t) = −x(t), v*(t) = P(t)x(t) = x(t).

Замкнутая система: ẋ = u* + v* = −x + x = 0 → x(t) = x(0) = 1.

Стоимость: J = 1² + ∫₀¹[1 − 1]dt = 1. Значение игры V(1) = 1. ✓ (при P=1 оба игрока «нейтрализуют» друг друга)

Седловые точки и равновесие

В играх с нулевой суммой ключевое понятие — седловая точка: пара стратегий (u*, v*) такая, что J(u, v*) ≥ J(u*, v*) ≥ J(u*, v) для всех допустимых u, v. Игроку 1 не выгодно отклоняться при фиксированном v*, и наоборот. Если седловая точка существует, цена игры однозначно определена. Условие Айзекса в дифференциальных играх — это локальная (по гамильтониану) версия условия существования седловой точки.

Алгоритмы поиска равновесия

Для матричных игр седловая точка находится через ЛП за полиномиальное время. Для дифференциальных игр в общем случае — численное решение HJI. Для линейно-квадратичных игр (ЛКИ) задача сводится к сопряжённым уравнениям Риккати:

(d/dt)P = −AᵀP − PA − Q + P(BR⁻¹Bᵀ − γ⁻²DDᵀ)P

где γ — параметр робастности. Решение P даёт оптимальную обратную связь u* = −R⁻¹BᵀPx. Это основа H∞-управления.

Расширения

Игры с информационными асимметриями: Stackelberg, leader-follower, с задержкой информации
Игры с сигналами: один игрок может «блефовать» — отправлять ложные сигналы (применение в кибербезопасности)
Робастная оптимизация как игра: «природа» как противник, выбирающий наихудший возможный сценарий — даёт устойчивые решения для финансовых портфелей и инженерных систем