Cheatsheet
Дифференциальные игры — all topics on one page
Введение в дифференциальные игры
История, постановка задач преследования-уклонения и основные классификации
Рождение теории: от ракет до экономики → Ключевое отличие от оптимального управления → Формальная постановка → Что значит «стратегия»? → Классификация игр → Связь с теорией оптимального управления → Примеры из реальной жизни → Историческое развитие → Современные численные методы → Применения
- •Игрок P (преследователь/минимизатор): min_u max_v J
- •Игрок E (убегающий/максимизатор): max_v min_u J
- •Конечно-разностные схемы для HJI: Lax-Friedrichs, ENO/WENO upwind, level-set (Osher-Sethian) — стандарт для задач малой размерности (n ≤ 4)
- •Метод полу-Лагранжа (Falcone, Ferretti): эффективен для задач с разрывами
- •Адаптивные сетки: AMR (Adaptive Mesh Refinement) для локального уточнения
- •Нейросетевые аппроксимации: Deep Galerkin, PINNs для HJI в высокой размерности — прорыв 2018-2023
- •Reach-avoid анализ: Hamilton-Jacobi reachability в библиотеках hj_reachability (Python), helperOC (MATLAB)
В 1950-е годы холодная война поставила военных аналитиков перед новой задачей: как перехватить высокоманёвренную ракету? Как уйти от перехватчика? Это не задача оптимального управления в обычном смысле — у «цели» есть собственная воля и она активно противодействует. Руфус Айзекс, работая в RAND C...
В задаче оптимального управления: один игрок управляет системой, минимизируя стоимость. Природа «не против» — нет противника. В дифференциальной игре: два (или более) игрока управляют совместно используемой системой, и их цели конфликтуют.
Это делает задачу принципиально сложнее: оптимальная стратегия одного игрока зависит от стратегии другого, и та — от стратегии первого. Это «петля»: нужно найти стратегии, которые одновременно оптимальны при заданных стратегиях противника.
Динамика: ẋ = f(x, u, v), x ∈ ℝⁿ (состояние), u ∈ U (управление игрока P, минимизатора), v ∈ V (управление игрока E, максимизатора).
От ГЯ-Беллмана к ГЯ-Айзекса → Функция ценности игры → Вывод уравнения HJI → Условие Айзекса → Оптимальные стратегии обратной связи → Регулярность и вязкостные решения → Полный разбор: простая игра преследования в ℝ → Применения → Численное решение HJI → Размерность как ограничение
- •Decomposition: разбиение задачи на подзадачи меньшей размерности (Mitchell, Tomlin)
- •Sparse grids (Smolyak): уменьшение числа узлов до O(N log^n)
- •Neural network approximation: Deep BSDE (E-Han-Jentzen, 2017), PINNs — нейросеть аппроксимирует V(x,t), решая HJI как loss function
- •Reinforcement learning: вместо явного решения HJI — обучение оптимальной политики через симуляцию
В теории оптимального управления ценовая функция V(x,t) удовлетворяет уравнению Гамильтона-Якоби-Беллмана (HJB). Когда появляется второй игрок с противоположными интересами, уравнение модифицируется: вместо min по u появляется min по u и max по v одновременно. Это уравнение Гамильтона-Якоби-Айзек...
Определение: V(x, t) = min_{u(·)} max_{v(·)} J(x, t; u(·), v(·)) — значение игры, начатой из состояния x в момент t.
где игровой гамильтониан: H*(x, t, p) = min_{u∈U} max_{v∈V} {F(x, u, v, t) + pᵀ f(x, u, v, t)}
Условие Айзекса: min_{u∈U} max_{v∈V} H(x,u,v,p) = max_{v∈V} min_{u∈U} H(x,u,v,p)
Самая старая игра мира → Постановка: простейший вариант → Три основных случая → Игра Айзекса «Homicidal Chauffeur» → Стратегия «упреждения» (Proportional Navigation) → Численный пример: оптимальное время захвата → Применения в автономных системах → Игры с препятствиями → Кооперативное преследование → Игры с неполной информацией
Formulas
- •Offline: предвычислить функцию ценности V на сетке состояний
- •Online: lookup ближайшего значения V и градиента, выбор оптимального управления
- •MPC (Model Predictive Control): на каждом шаге решать задачу оптимизации на коротком горизонте
- •Военная авиация: системы автоматического перехвата (AIM-120 AMRAAM, Patriot)
- •Космос: маневрирование спутников для уклонения от обломков
- •Безопасность: автоматические системы охраны периметра
- •Спорт: анализ оптимальных стратегий в командных играх (хоккей, футбол)
- •Биология: моделирование охоты хищников, эволюция систем «хищник-жертва»
Охотник преследует зайца. Лиса гонится за кроликом. Военный перехватчик — за целью. Задача преследования-уклонения (Pursuit-Evasion, PE) — одна из древнейших прикладных математических задач. Айзекс придал ей строгую математическую форму и открыл первые удивительные результаты: оптимальная стратег...
Два игрока в ℝ². Преследователь P с позицией xP ∈ ℝ², скорость |u| ≤ α. Убегающий E с позицией xE ∈ ℝ², скорость |v| ≤ β.
Захват: r(t) ≤ l (захватывающий радиус). P хочет достигнуть захвата, E — избежать.
Захват гарантирован при любой стратегии E. Оптимальная стратегия P: Pure Pursuit (просто лети к E) — обеспечивает захват за конечное время.
Игры с нулевой суммой и минимакс
Теория игр с нулевой суммой, теорема минимакса и стратегии обратной связи
Фундаментальный факт: оба игрока «знают» оптимальное значение → Теорема минимакса Неймана → Равновесие Нэша в матричных играх → Расширение на дифференциальные игры → Стратегии обратной связи vs разомкнутые → LQ-дифференциальные игры → Полный разбор: LQ-игра 1D → Седловые точки и равновесие → Алгоритмы поиска равновесия → Расширения
- •x* оптимальна при y*: xᵀAy* ≤ x*ᵀAy* для всех x ∈ Δₘ
- •y* оптимальна при x*: x*ᵀAy ≤ x*ᵀAy* для всех y ∈ Δₙ... нет, наоборот для максимизатора
- •Игры с информационными асимметриями: Stackelberg, leader-follower, с задержкой информации
- •Игры с сигналами: один игрок может «блефовать» — отправлять ложные сигналы (применение в кибербезопасности)
- •Робастная оптимизация как игра: «природа» как противник, выбирающий наихудший возможный сценарий — даёт устойчивые решения для финансовых портфелей и инженерных систем
В 1928 году Джон фон Нейман доказал поразительный факт: в любой матричной игре с нулевой суммой есть «равновесие». Минимизатор не может «ухудшить» результат ниже некоторого значения V, а максимизатор не может поднять его выше того же V. Это значение V — «цена игры». Теорема минимакса — это матема...
где Δₖ — стандартный симплекс смешанных стратегий (вероятностное распределение на k чистых стратегиях).
Смысл: максимальный «гарантированный» выигрыш игрока 1 = минимальный «гарантированный» проигрыш игрока 2. Это значение называется ценой игры.
Доказательство через ЛП: задача max_x min_y xᵀAy — это ЛП (можно ввести переменную v = min_y xᵀAy). Сильная двойственность ЛП → равенство min = max.
Проблема устойчивости при неизвестных возмущениях → H∞-задача: постановка → Игровая формулировка → LMI-решение H∞ → Физическая интерпретация → Полный разбор: H∞-синтез для подвески автомобиля → Применения → H∞-норма и интерпретация → Связь с дифференциальной игрой → Алгоритмы синтеза
- •min по u: 2EᵀCx + 2EᵀEu + BᵀP = 0 → u* = −(EᵀE)⁻¹(EᵀCx + (1/2)BᵀPx)
- •max по w: −2γ²w + DᵀPx = 0 → w* = DᵀPx/(2γ²)
- •Уравнения Риккати с γ-итерацией: бинарный поиск по γ + решение уравнения Риккати для каждого γ
- •LMI (Linear Matrix Inequalities): формулировка через выпуклые ограничения, решение через SDP-решатели (SeDuMi, MOSEK)
- •μ-синтез: учёт структурированной неопределённости (D-K iteration)
- •Loop-shaping: классическая методика H∞ через формирование частотной характеристики
В реальных системах управления — самолётах, энергосистемах, химических реакторах — всегда есть неизвестные возмущения: турбулентность, изменения нагрузки, параметрическая неопределённость. Классическое управление (LQR) оптимально при известной модели, но может «сломаться» при возмущениях. H∞-упра...
Задача H∞: найти управление u = K(x), минимизирующее «коэффициент усиления» от w к z в наихудшем случае:
‖T_{zw}‖_∞ — H∞-норма передаточной функции от w к z. Это «усиление наихудшего сигнала».
Как дифференциальная игра: управление u — минимизатор, возмущение w — максимизатор:
Терминальный момент: что происходит «в конце» → Структура решения через обратную индукцию → LQ-игра с конечным горизонтом → Зоны выживания и захвата → Полный разбор: двумерная игра захвата → Численные методы для HJI → Задачи с фиксированным временем → Принцип динамического программирования → Reachability и зоны достижимости → Применения
Formulas
- •Deep learning для HJI (DeepReach, 2021): нейросеть аппроксимирует V(x,t) → работает в высоких размерностях
- •Линеаризация: V ≈ xᵀP(t)x (LQ-приближение)
- •PINN (Physics-Informed Neural Networks): обучение нейросети удовлетворять HJI как физическому ограничению
- •Фиксированное T, свободное x(T): V(x, T) = g(x) — задача с терминальной стоимостью
- •Фиксированный xT: достичь заданного состояния — V(xT, T) = 0, V(x, T) = +∞ для x ≠ xT (вырождение)
- •Свободное T (момент остановки): T определяется первым моментом, когда x(T) попадает в целевое множество — игры с моментом остановки
В задачах с конечным горизонтом [0, T] состояние системы x(T) имеет особый статус: функция g(x(T)) задаёт «терминальный выигрыш». Это определяет «границы» — наборы начальных состояний x₀, из которых P или E могут гарантировать нужный исход. Математически: функция ценности определяется из HJI с те...
Принцип оптимальности даёт: V(x,t) = min_u max_v {F(x,u,v,t)dt + V(x+f·dt, t+dt)}.
Это «уравнение Беллмана» в обратном времени: зная V при t+dt, вычисляем V при t. Начинаем от T (где V(x,T) = g(x)) и «идём назад».
Для LQ-игр: V(x,t) = xᵀP(t)x (квадратичная по x), P(t) — матрица Риккати-Айзекса, удовлетворяющая ОДУ.
Многоигровые и кооперативные дифференциальные игры
N-игровые дифференциальные игры, Nash-равновесие и кооперативные решения
Когда игроков больше двух → Постановка N-игровой задачи → Равновесие Нэша (Nash Equilibrium) → Уравнения Нэша для LQ-игр → Равновесие Штакельберга → Полный разбор: ценовая конкуренция Бертрана → Вычисление NE на практике → N-игровые игры с ненулевой суммой → Существование и единственность → Применения
Formulas
- •Регуляторы и компании: правительство объявляет налоги (лидер), компании реагируют (последователи)
- •Поставщик-ритейлер: поставщик устанавливает оптовую цену, ритейлер — розничную
- •Патентные гонки: лидирующая компания инвестирует, конкурент реагирует
- •Равновесие Нэша: профиль (u₁*,...,u_N*), при котором никому не выгодно отклоняться в одиночку. J_i(u₁*,...,u_i,...,u_N*) ≥ J_i(u*) для всех u_i.
- •Парето-оптимум: профиль, который нельзя улучшить для одного без ухудшения для другого.
- •Stackelberg-равновесие: иерархия — лидер выбирает первым, последователи реагируют.
- •Олигополия Курно с динамикой запасов: компании выбирают объёмы производства, динамика — накопление запасов
- •Климатические переговоры: страны выбирают уровень сокращения выбросов, общий результат — изменение климата (общее благо)
- •Управление трафиком: каждый автомобиль выбирает маршрут, общая нагрузка на сеть формирует время в пути
- •Многоагентные роботы: распределённое управление дронами для общей задачи (поиск, наблюдение)
Реальная конкуренция редко бывает дуэлью. Три компании делят рынок. Пять государств управляют рыболовством. Сотня трейдеров торгуют на рынке. В таких ситуациях структура стратегического взаимодействия принципиально сложнее: каждый игрок оптимизирует против «всех остальных сразу», а не против одно...
Ключевое отличие от нулевой суммы: Σᵢ Jᵢ ≠ const в общем случае. Можно выиграть «сообща», или наоборот — все проигрывают.
Смысл: ни один игрок не может улучшить свой результат, в одностороннем порядке изменив свою стратегию (при фиксированных стратегиях остальных).
Существование: при разумных условиях (компактные Uᵢ, непрерывные Jᵢ) NE в смешанных стратегиях существует (теорема Нэша, 1950).
Когда вместе выгоднее → Характеристическая функция → Шепли-значение → Ядро игры (Core) → Динамическая согласованность → Применение: управление рыбными ресурсами → Полный разбор: трёхигровая модель → Кооперативные игры: формирование коалиций → Концепции дележа → Динамическая устойчивость
Definitions
Formulas
- •Эффективность: Σᵢ xᵢ = v(N)
- •Групповая рациональность: Σᵢ∈S xᵢ ≥ v(S) для всех S
- •Супераддитивность: v(S ∪ T) ≥ v(S) + v(T) для непересекающихся S, T — кооперация выгоднее
- •Выпуклость: v(S ∪ T) + v(S ∩ T) ≥ v(S) + v(T) — гарантирует устойчивость
- •Ядро (core): множество дележей, где никакая коалиция не может улучшить положение, выйдя из соглашения
- •Вектор Шепли: φ_i = (1/n!) Σ_π [v(S_π_i ∪ {i}) − v(S_π_i)] — средний вклад игрока i по всем порядкам присоединения
- •Нуклеолус (Шмайдлер): минимизирует «недовольство» наименее довольной коалиции
- •τ-значение (Тийс): компромисс между минимальными правами и максимальными претензиями
Nash-равновесие описывает «ситуацию без договорённостей»: каждый за себя. Но в реальности игроки часто могут договариваться о совместных стратегиях и делить выигрыш. Рыболовные государства договариваются об ограничении вылова. Страны создают климатические соглашения. Компании объединяются в консо...
v(S) = максимальный суммарный выигрыш, который S может гарантировать себе совместными действиями
Супераддитивность: v(S ∪ T) ≥ v(S) + v(T) при S ∩ T = ∅. Если есть «синергия» от кооперации — объединяться выгодно.
При супераддитивности: v(N) ≥ Σᵢ v({i}) — объединяться всем вместе выгоднее, чем действовать поодиночке.
Рынки, трафик и «безличная» конкуренция → Ключевая идея: среднее поле → Система уравнений MFG → Анализ уравнений → Применения MFG → Численные методы → Полный разбор: задача о скоплении → Mean Field Games: интуиция → Связанная система уравнений → Существование и численные методы
- •V(x,t) — «ценность» нахождения в состоянии x в момент t для типичного агента
- •m(x,t) — распределение агентов в пространстве состояний
- •Hₚ = ∂H/∂p — оптимальное «дрейфовое поле» (скорость движения агентов)
- •∆-члены — случайные флуктуации (диффузия)
- •Метод фиктивной игры (fictitious play): итеративно обновлять u по фиксированному m, затем m по новому u
- •Sinkhorn для энтропийной регуляризации
- •DeepLearning подходы: Deep MFG (Carmona-Laurière) — нейросети представляют u и m
- •Толпы и эвакуация: моделирование движения людей в зданиях, на стадионах
- •Энергетика: миллионы потребителей выбирают тарифы и потребление
- •Финансы: систематический риск, modeling crowded trades
- •Эпидемиология: индивидуальные решения о вакцинации с учётом популяционного эффекта
- •Криптовалюты: майнеры как игроки в MFG за вычислительные ресурсы
Представьте тысячи трейдеров на финансовом рынке. Каждый рационален и влияет на цену, но каждый «мал» по сравнению с рынком в целом. Или тысячи пешеходов в узком коридоре — каждый оптимально выбирает путь, но взаимодействует со «средней плотностью» толпы, а не с каждым человеком индивидуально. Me...
При N → ∞ «типичный» агент взаимодействует не с конкретными другими агентами, а с «распределением» всей популяции m(x, t) — плотностью агентов в состоянии x в момент t.
Предположение однородности: все агенты одинаковые (i.i.d. — независимые одинаково распределённые начальные состояния).
NE в пределе N → ∞: типичный агент оптимизирует свою стратегию, считая m(x,t) «данным» (не зависящим от его действий). В равновесии m(x,t) порождается именно этой оптимальной стратегией типичного агента — самосогласованность!
Стохастические дифференциальные игры
Игры в стохастической среде, стохастические HJB и BSDE
Неопределённость в стратегическом взаимодействии → Стохастическая динамика → Принцип Беллмана в стохастическом случае → Оптимальные стратегии и принцип минимакса → Связанные обратные стохастические дифференциальные уравнения → Полный разбор: стохастическая LQ-игра → Связь со стохастическим контролем и финансами → Стохастические дифференциальные игры → Связь с финансовой математикой → Численные методы
Definitions
- •X ∈ ℝⁿ — состояние
- •u ∈ U, v ∈ V — управления игроков
- •σ(X, t) ∈ ℝ^{n×m} — матрица волатильности
- •W — m-мерный стандартный броуновский процесс (Wiener process)
- •Детерминированная HJI: ∂V/∂t + H* = 0
- •Стохастическая HJI: ∂V/∂t + (σ²/2)∆V + H* = 0
- •Стохастические сетки: расширение конечных разностей
- •Symmetric splitting: разделение на детерминированную и шумовую части
- •Backward SDE (BSDE): представление V через стохастические уравнения, численное решение через метод Лонгстаффа-Шварца
- •Deep BSDE (E-Han-Jentzen, 2017): нейросетевая аппроксимация для высоких размерностей
- •Управление портфелем с риск-неопределённостью: робастная оптимизация Маркетти-Шейнинга
- •Распределённая энергетика: координация миллионов потребителей с шумовыми нагрузками
- •Беспилотный транспорт: учёт неопределённости поведения других участников
- •Робототехника в сложных условиях: квадрокоптеры в ветре
В детерминированных играх будущее предопределено: зная начальное состояние и стратегии обоих игроков, можно точно предсказать траекторию. В реальных системах всегда есть шум: рыночная волатильность, турбулентность, тепловые флуктуации. Стохастические дифференциальные игры (СДИ) расширяют детермин...
Дополнительный член (1/2)tr(σσᵀ ∇²V) — «итовский» член (следствие формулы Ито для стохастического дифференциала).
Стохастичность добавляет лапласиан ∆V = tr(∇²V), который «сглаживает» функцию ценности.
Оптимальный игровой гамильтониан: H*(x,t,p,Q) = min_{u∈U} max_{v∈V} [F + pᵀf + (1/2)tr(σσᵀQ)]
Когда аналитика недостаточно → Игровой RL: постановка → Independent Q-learning (IQL) → MADDPG (Multi-Agent DDPG) → Self-Play и конвергенция к Nash → Связь с уравнением HJI через Actor-Critic → Полный разбор: конвергенция MADDPG на задаче коопераций → Многоагентное обучение с подкреплением (MARL) → Алгоритмы MARL → Связь с дифференциальными играми
- •Состояние s ∈ S
- •Действия агентов: a₁ ∈ A₁, a₂ ∈ A₂
- •Переход: P(s' | s, a₁, a₂)
- •Награды: r₁(s, a₁, a₂), r₂(s, a₁, a₂)
- •Эпизод 1-100: агенты движутся случайно, средняя награда ≈ −15
- •Эпизод 100-500: агенты начинают двигаться к центру, но разными путями, ≈ −8
- •Эпизод 500-1000: конвергенция к «рандеву» стратегии, ≈ −2
- •Independent Q-learning: каждый агент учится независимо. Простой, но без гарантий сходимости.
- •MADDPG (Multi-Agent DDPG, Lowe et al., 2017): centralized training, decentralized execution — критик видит все стратегии при обучении, актор использует только свою наблюдаемость в исполнении.
- •Nash-Q learning: явный поиск равновесия Нэша на каждом шаге.
- •PSRO (Policy-Space Response Oracles): итеративно расширяет популяцию стратегий, ищет лучший ответ на текущее распределение.
- •MFRL (Mean Field RL): применение mean field approximation к большим N-агентным играм.
- •AlphaZero — аналог решения нулевой суммы игры (шахматы, Го) через self-play
- •AlphaStar — частичная информация (StarCraft II) через Counterfactual Regret Minimization
- •OpenAI Five — кооперация в команде против команды (Dota 2)
- •Гарантии сходимости MARL в общем случае
- •Масштабирование на тысячи агентов
- •Объяснимость стратегий
- •Безопасность (avoiding adversarial exploitation)
Дифференциальные игры обеспечивают красивую теорию, но на практике аналитическое решение HJI возможно лишь в немногих специальных случаях (LQ-игры, задачи с простой динамикой). В реальных задачах — нелинейная динамика, высокая размерность, неизвестная модель системы. Здесь на помощь приходит обуч...
Проблема нестационарности: если агент 1 обновляет свою политику, среда с точки зрения агента 2 меняется. «Цель» движется — сходимость Q-learning не гарантирована!
Каждый агент i учит свою Q-функцию Qᵢ(s, aᵢ) независимо, не учитывая действия других.
Недостатки: нет теоретических гарантий сходимости. Среда нестационарна. На практике часто работает!
Экономика как поле для игр → Дуополия Курно в непрерывном времени → Гонка вооружений: модель Ричардсона и её игровое обобщение → Конкуренция в НИОКР (модель Спенса) → Mean Field Game в финансах: оптимальная ликвидация → Международные экологические соглашения → Игры в финансовых рынках → Кооперативные игры в страховании → Игры в макроэкономике → Применения в реальной торговле
Formulas
- •Игры между правительствами: торговая политика (тарифы, квоты), денежно-кредитная политика — каждая страна оптимизирует свой результат, влияя на других
- •Stackelberg-игры центрального банка и рынка: ЦБ устанавливает ставку, рынок реагирует ожиданиями
- •Игры с общими ресурсами: рыболовство, нефть, водные ресурсы — классические задачи «трагедии общего достояния», моделируются как дифференциальные игры
- •Climate change negotiations: страны выбирают уровень сокращения выбросов; общий результат — глобальное потепление
- •HFT (High-Frequency Trading): алгоритмические торговые системы используют игротеоретические модели для прогнозирования действий конкурентов
- •Market microstructure: книги ордеров моделируются как игры между лимитными и рыночными ордерами
- •Algorithmic execution: VWAP, TWAP, Implementation Shortfall — все эти алгоритмы можно интерпретировать как стратегии в дифференциальной игре
- •Crypto markets: децентрализованные биржи (Uniswap, dYdX) создают новые игротеоретические задачи (front-running, MEV)
- •Risk management: расчёт VaR (Value at Risk) с учётом стратегического поведения других участников рынка
Финансовые рынки, олигополистическая конкуренция, переговоры о климате — это всё задачи стратегического взаимодействия в динамической среде. Дифференциальные игры дают строгий математический аппарат для их анализа. Ключевое преимущество перед статическими теориями игр: учёт динамики накопления ка...
Модель: два производителя выпускают qᵢ(t) единиц товара. Цена зависит от суммарного выпуска: P(t) = a − b(q₁(t) + q₂(t)).
Nash-равновесие: через уравнения Гамильтона или DP. Оптимальные инвестиции u*ᵢ(t) зависят от собственного капитала и капитала конкурента.
Стационарное Nash-состояние (при t → ∞): каждый производитель достигает стабильного уровня капитала K̄ᵢ* = argmax прибыли при равновесных ценах.