N-игровые дифференциальные игры и Nash-равновесие

Когда игроков больше двух

Реальная конкуренция редко бывает дуэлью. Три компании делят рынок. Пять государств управляют рыболовством. Сотня трейдеров торгуют на рынке. В таких ситуациях структура стратегического взаимодействия принципиально сложнее: каждый игрок оптимизирует против «всех остальных сразу», а не против одного противника. Понятие Nash-равновесия обобщает минимаксное решение нулевых игр на ненулевую сумму и произвольное число игроков.

Постановка N-игровой задачи

N игроков, состояние системы x ∈ ℝⁿ, игрок i управляет uᵢ ∈ Uᵢ.

Динамика: ẋ = f(x, u₁, u₂, ..., uN, t).

Функционал игрока i: Jᵢ(u₁,...,uN) = gᵢ(x(T)) + ∫₀ᵀ Fᵢ(x, u₁,...,uN, t) dt.

Каждый игрок стремится min Jᵢ (или max — в зависимости от постановки).

Ключевое отличие от нулевой суммы: Σᵢ Jᵢ ≠ const в общем случае. Можно выиграть «сообща», или наоборот — все проигрывают.

Равновесие Нэша (Nash Equilibrium)

Профиль стратегий (u₁*,...,uN*) называется равновесием Нэша (NE), если:

Jᵢ(u₁*,...,uᵢ*,...,uN*) ≤ Jᵢ(u₁*,...,uᵢ,...,uN*) для всех uᵢ и всех i

Смысл: ни один игрок не может улучшить свой результат, в одностороннем порядке изменив свою стратегию (при фиксированных стратегиях остальных).

Существование: при разумных условиях (компактные Uᵢ, непрерывные Jᵢ) NE в смешанных стратегиях существует (теорема Нэша, 1950).

Уникальность: в общем случае NE может быть несколько или единственным. Для LQ-игр с «диагональной» структурой — единственное.

Уравнения Нэша для LQ-игр

Для N-игровой LQ-игры: ẋ = Ax + Σᵢ Bᵢuᵢ, Jᵢ = xᵀ(T)Gᵢx(T) + ∫ [xᵀQᵢx + uᵢᵀRᵢᵢuᵢ] dt.

NE-стратегии линейны: uᵢ* = −Rᵢᵢ⁻¹Bᵢᵀ Pᵢ(t) x(t).

Матрицы Pᵢ удовлетворяют системе связанных уравнений Риккати:

−Ṗᵢ = AᵀPᵢ + PᵢA + Qᵢ − Σⱼ PᵢBⱼRⱼⱼ⁻¹BⱼᵀPⱼ = 0, Pᵢ(T) = Gᵢ.

Это нелинейная система уравнений Риккати — в общем случае нет явного решения. Требуется итерационное решение.

Равновесие Штакельберга

В некоторых задачах существует иерархия: лидер объявляет стратегию первым, последователь реагирует оптимально.

Двухуровневая игра: лидер знает функцию реакции последователя R(uL) = argmin_{uF} JF(uL, uF). Лидер минимизирует JL(uL, R(uL)) — «решает сначала».

Равновесие Штакельберга: набор (uL*, uF*) с uF* = R(uL*), uL* = argmin_uL JL(uL, R(uL)).

Свойство: лидер всегда не хуже, чем в NE (имеет «advantage от первого хода»).

Применения:

Регуляторы и компании: правительство объявляет налоги (лидер), компании реагируют (последователи)
Поставщик-ритейлер: поставщик устанавливает оптовую цену, ритейлер — розничную
Патентные гонки: лидирующая компания инвестирует, конкурент реагирует

Полный разбор: ценовая конкуренция Бертрана

Две компании устанавливают цены p₁, p₂. Спросы: q₁ = a − bp₁ + cp₂, q₂ = a − bp₂ + cp₁ (c < b — конкуренция).

Прибыли: πᵢ = (pᵢ − k) qᵢ (k — производственные издержки).

Статическое NE: ∂π₁/∂p₁ = 0 и ∂π₂/∂p₂ = 0 → p₁* = p₂* = (a + bk)/(2b − c).

Динамика: цены меняются медленно, dpᵢ/dt = uᵢ, управление = скорость изменения цены.

Jᵢ = ∫₀^∞ e^{−ρt} πᵢ dt (дисконтированная прибыль).

Nash-равновесие: через уравнения Риккати. Траектории цен: p₁(t), p₂(t) сходятся к статическому NE — «динамика ценовой конкуренции».

Вычисление NE на практике

Точное NE для нелинейных динамик — открытая задача. Методы на практике:

Best Response Dynamics: каждый игрок по очереди оптимизирует свою стратегию при фиксированных стратегиях остальных. Сходимость к NE не гарантирована, но часто работает.

Multi-Agent Reinforcement Learning (MARL): Independent Q-learning (IQL), MADDPG, MAPPO. Каждый агент обучается максимизировать свою долгосрочную награду. При «самоигре» (self-play) конвергирует к NE для некоторых классов игр.

Deep Nash: явная формулировка Nash-условий как системы уравнений + нейросеть для совместного решения.

N-игровые игры с ненулевой суммой

В отличие от дуэли, в N-игровых дифференциальных играх каждый игрок i имеет свой функционал J_i(x; u₁,...,u_N), который он минимизирует. Понятие «оптимума» неоднозначно:

Равновесие Нэша: профиль (u₁*,...,u_N*), при котором никому не выгодно отклоняться в одиночку. J_i(u₁*,...,u_i,...,u_N*) ≥ J_i(u*) для всех u_i.
Парето-оптимум: профиль, который нельзя улучшить для одного без ухудшения для другого.
Stackelberg-равновесие: иерархия — лидер выбирает первым, последователи реагируют.

Эти концепции в общем случае не совпадают: «дилемма заключённого» показывает, что равновесие Нэша может быть Парето-неэффективным (взаимная защита приводит к худшему для всех результату).

Существование и единственность

Для N-игровых дифференциальных игр с обратной связью существование равновесия Нэша требует строгих условий. В линейно-квадратичном случае (LQG) равновесие даётся системой связанных уравнений Риккати — она может иметь несколько решений, что отражает множественность равновесий.

Применения

Олигополия Курно с динамикой запасов: компании выбирают объёмы производства, динамика — накопление запасов
Климатические переговоры: страны выбирают уровень сокращения выбросов, общий результат — изменение климата (общее благо)
Управление трафиком: каждый автомобиль выбирает маршрут, общая нагрузка на сеть формирует время в пути
Многоагентные роботы: распределённое управление дронами для общей задачи (поиск, наблюдение)