Равновесие Нэша

Материал из MachineLearning.

Статья написана с использованием LLM DeepSeek-V4 и проверена участником Oleg Aleksandrov 14:52, 15 июля 2026 (MSD)

Равнове́сие Нэ́ша — центральная концепция решения в некооперативной теории игр, описывающая такой профиль стратегий игроков, при котором ни одному из участников невыгодно в одностороннем порядке менять свою стратегию. В машинном обучении и искусственном интеллекте равновесие Нэша выступает естественным формализмом для моделирования взаимодействия нескольких обучающихся агентов, состязательного обучения, а также для анализа сходимости алгоритмов в генеративно-состязательных сетях и многоагентном обучении с подкреплением (англ. multi-agent reinforcement learning, MARL).

Содержание

1 Интуитивное определение
2 Формальное определение
- 2.1 Смешанное расширение
3 Классические примеры
4 Равновесие Нэша в машинном обучении и ИИ
5 Вычислительные аспекты и алгоритмы поиска
6 Математическая структура и связь с оптимизацией
7 Критика и открытые вопросы в контексте ML
8 Литература

Интуитивное определение

Рассмотрим систему из нескольких рациональных агентов, каждый из которых выбирает действие (стратегию), максимизируя собственный выигрыш, зависящий от действий всех участников. Равновесие Нэша — такое состояние, в котором стратегия каждого агента является наилучшим ответом на стратегии остальных. Если все придерживаются равновесных стратегий, ни один не может увеличить свой выигрыш, отклонившись в одиночку. Такая самоподдерживающаяся природа превращает равновесие Нэша в ключевое предсказание исхода стратегического взаимодействия.

Формальное определение

Рассматривается конечная игра в нормальной форме с $N$ игроками. Пусть $\mathcal{I} = \{1, \ldots, N\}$ — множество игроков, $S_i$ — множество доступных стратегий (действий) игрока $i$ , $u_i: S_1 \times \cdots \times S_N \to \mathbb{R}$ — функция полезности (выигрыша) игрока $i$ .

Профиль стратегий $\mathbf{s} = (s_1, \ldots, s_N)$ , где $s_i \in S_i$ , называется равновесием Нэша в чистых стратегиях, если для каждого игрока $i$ и любой его альтернативной стратегии $s_i' \in S_i$ выполняется: $u_i(s_i, \mathbf{s}_{-i}) \ge u_i(s_i', \mathbf{s}_{-i})$ где $\mathbf{s}_{-i}$ обозначает стратегии всех игроков, кроме $i$ .

Смешанное расширение

Многие игры не имеют равновесий в чистых стратегиях. Понятие обобщается на смешанные стратегии — распределения вероятностей на множестве чистых стратегий. Пусть $\Sigma_i = \Delta(S_i)$ — симплекс смешанных стратегий игрока $i$ . Смешанный профиль $\sigma = (\sigma_1, \ldots, \sigma_N)$ является равновесием Нэша, если для любого $i$ и любой $\sigma_i' \in \Sigma_i$ : $\mathbb{E}_{\mathbf{s} \sim \sigma}\big[u_i(\mathbf{s})\big] \ge \mathbb{E}_{s_i' \sim \sigma_i',\; \mathbf{s}_{-i} \sim \sigma_{-i}}\big[u_i(s_i', \mathbf{s}_{-i})\big]$

Джон Нэш (1950) доказал, что в любой конечной игре существует хотя бы одно равновесие в смешанных стратегиях. Существование опирается на теорему Какутани о неподвижной точке, применённую к отображению наилучшего ответа.

Классические примеры

Дилемма заключённого: два игрока выбирают «сотрудничать» или «предать». Равновесие Нэша в чистых стратегиях — взаимное предательство, хотя обоюдное сотрудничество принесло бы больший суммарный выигрыш. Пример показывает, что равновесие не обязано быть Парето-оптимальным.
Семейный спор (координационная игра): два равновесия в чистых стратегиях с разными выигрышами. Возникает проблема выбора равновесия.
Орлянка (matching pennies): игра с нулевой суммой без равновесия в чистых стратегиях. Единственное равновесие в смешанных стратегиях — каждому игроку выбирать свои действия равновероятно.

Равновесие Нэша в машинном обучении и ИИ

Современные системы машинного обучения всё чаще работают с многоагентными, состязательными и иерархическими сценариями. Равновесие Нэша задаёт естественный язык для постановки целей обучения и критериев сходимости.

Генеративно-состязательные сети (GAN)

Классическая GAN (англ. Generative Adversarial Network) (Goodfellow et al., 2014) формулируется как минимаксная игра двух игроков с нулевой суммой: генератор $G$ и дискриминатор $D$ . Функция ценности: $\min_G \max_D\; V(D,G) = \mathbb{E}_{\mathbf{x}\sim p_{\text{data}}}[\log D(\mathbf{x})] + \mathbb{E}_{\mathbf{z}\sim p_{\mathbf{z}}}[\log(1 - D(G(\mathbf{z})))]$ Оптимальный дискриминатор при фиксированном генераторе имеет вид $D^*_G(\mathbf{x}) = \frac{p_{\text{data}}(\mathbf{x})}{p_{\text{data}}(\mathbf{x}) + p_g(\mathbf{x})}$ . Подстановка $D^*_G$ в $V$ превращает задачу в минимизацию расстояния Йенсена–Шеннона между распределением данных и генерируемым распределением. Глобальное решение достигается при $p_g = p_{\text{data}}$ , когда $D(\mathbf{x}) = 1/2$ для всех $\mathbf{x}$ . Эта точка является равновесием Нэша: ни генератор, ни дискриминатор не могут односторонне улучшить свой выигрыш.

Обучение GAN одновременным или попеременным градиентным спуском не гарантирует сходимости к равновесию Нэша. Динамика в пространстве параметров часто демонстрирует циклы или расходимость, так как игра не является потенциальной. Это мотивировало развитие методов, явно нацеленных на поиск седловых точек и локальных равновесий, а также регуляризаций (например, градиентного штрафа) в рамках дифференцируемых игр.

Многоагентное обучение с подкреплением

В многоагентном обучении с подкреплением несколько агентов обучаются одновременно в общей среде. Формализм стохастических игр (англ. stochastic game) — обобщение марковских процессов принятия решений на несколько агентов — описывает динамику состояния и награды, зависящие от совместных действий. Стационарная марковская стратегия образует равновесие Нэша, если для каждого агента она служит наилучшим ответом на стратегии остальных при любом состоянии.

Ранние алгоритмы непосредственно вычисляли равновесие:

Minimax-Q (Littman, 1994) для игр двух агентов с нулевой суммой: вместо максимизации по следующему действию используется минимаксная оценка ценности, соответствующая равновесной стратегии.
Nash-Q (Hu & Wellman, 2003) обобщает идею на игры с ненулевой суммой, поддерживая оценки Q-функций и решая на каждом шаге задачу поиска равновесия Нэша в матричной игре. Алгоритм предполагает строгие условия (например, единственность равновесия) и вычислительно трудоёмок.

Современные подходы к независимому обучению чаще опираются на связь между обучением без сожаления (англ. no-regret learning) и сходимостью к множеству равновесий. Если каждый агент использует алгоритм с исчезающим средним сожалением (например, экспоненциальное взвешивание, Regret matching), то эмпирическое распределение сыгранных стратегий сходится к коррелированному равновесию или грубому коррелированному равновесию — ослабленным концепциям равновесия Нэша. Этот результат принципиален при анализе многопользовательских рекомендательных систем, аукционов и механизмов ценообразования.

Состязательное обучение и устойчивость

Состязательная тренировка (англ. adversarial training) нейронных сетей для повышения устойчивости к враждебным искажениям интерпретируется как игра: атакующий выбирает возмущение, максимизирующее потери, а модель обучается минимизировать потери на возмущённых примерах. Равновесие Нэша в такой игре соответствует оптимально устойчивому классификатору и наиболее сильной атаке. Вычислительные трудности поиска равновесия в пространстве параметров нейросетей остаются открытой областью исследований.

Вычислительные аспекты и алгоритмы поиска

Задача нахождения равновесия Нэша в общих играх с ненулевой суммой вычислительно трудна. Доказано (Daskalakis, Goldberg, Papadimitriou, 2009), что она является PPAD-полной даже для двух игроков, что означает маловероятность существования полиномиальных алгоритмов в худшем случае.

Для отдельных классов игр эффективные методы известны:

Игры двух лиц с нулевой суммой сводятся к задаче линейного программирования.
Фиктивное игра (англ. fictitious play) — итеративный процесс, в котором каждый игрок выбирает наилучший ответ на эмпирическое распределение стратегий оппонента. Сходится для игр с нулевой суммой, потенциальных игр и ряда других, но не универсален.
Методы на основе минимизации сожаления: counterfactual regret minimization (англ. counterfactual regret minimization, CFR) произвели революцию в решении крупных игр с неполной информацией (например, покер). CFR минимизирует контрфактуальное сожаление локально в каждом информационном состоянии и гарантирует сходимость к равновесию Нэша в играх с неполной информацией за конечное время с точностью $\varepsilon$ . Системы DeepStack и Libratus применяли эти идеи в комбинации с глубокими нейронными сетями.
В дифференцируемых играх (Balduzzi et al., 2018) предложены методы, стабилизирующие градиентную динамику путём симметризации векторного поля градиентов (Consensus Optimization) для сходимости к локальному равновесию Нэша.

Математическая структура и связь с оптимизацией

Равновесие Нэша тесно связано с теорией неподвижных точек: профиль стратегий равновесен тогда и только тогда, когда он является неподвижной точкой отображения наилучших ответов. В смешанном расширении это отображение выпуклозначно и полунепрерывно сверху, что по теореме Какутани гарантирует существование неподвижной точки.

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

Формализм вариационного неравенства даёт унифицированный взгляд: в игре $N$ игроков с дифференцируемыми функциями выигрыша профиль стратегий $x^*$ является равновесием Нэша, если для всех допустимых $x$ выполняется $\langle F(x^*), x - x^* \rangle \ge 0$ , где $F(x) = (-\nabla_{x_i} u_i(x))_{i=1}^N$ — оператор игры. Когда $F$ — градиент потенциальной функции, игра относится к классу потенциальных игр, и равновесия совпадают со стационарными точками потенциала, что резко упрощает анализ.

Критика и открытые вопросы в контексте ML

Применение равновесия Нэша в ML сталкивается с рядом принципиальных трудностей.

Множественность равновесий: многие игры содержат континуум или множество изолированных равновесий. Без дополнительных критериев невозможно предсказать, к какому из них сойдётся обучение. Это особенно актуально для GAN и MARL.
Сходимость: стандартные градиентные методы не обязаны сходиться к равновесиям Нэша даже в простых дифференцируемых играх; возникают незатухающие осцилляции или предельные циклы.
Вычислительная эффективность: точный поиск равновесия часто нереализуем на практике. Широко применяются приближённые концепции (грубое коррелированное равновесие, локальное равновесие, Stackelberg) или эвристики.
Адекватность модели: предположение о полной рациональности и общем знании игры редко выполняется в многоагентных системах ИИ, обучающихся на ограниченных данных. В реальности агенты используют ограниченно рациональные или адаптивные стратегии.
Нестационарность среды: при одновременном обучении каждый агент сталкивается с меняющейся средой, так как политики других агентов нестационарны. Это нарушает марковское свойство с точки зрения отдельного агента и усложняет гарантии сходимости.

Активные направления исследований включают разработку масштабируемых приближённых методов поиска равновесий, интеграцию с глубокими нейронными сетями, изучение мета-игр и иерархических равновесий, а также приложения к задачам федеративного обучения, аукционов и экономических механизмов в системах ИИ.

Литература

Nash J. F. Equilibrium points in n-person games // Proceedings of the National Academy of Sciences. — 1950. — Т. 36. — № 1. — С. 48—49.
Fudenberg D., Tirole J. Game Theory. — MIT Press, 1991.
Goodfellow I. J., Pouget-Abadie J., Mirza M., Xu B., Warde-Farley D., Ozair S., Courville A., Bengio Y. Generative Adversarial Nets // Advances in Neural Information Processing Systems 27 (NIPS). — 2014. — С. 2672—2680.
Littman M. L. Markov games as a framework for multi-agent reinforcement learning // Proceedings of the 11th International Conference on Machine Learning (ICML). — 1994. — С. 157—163.
Hu J., Wellman M. P. Nash Q-learning for general-sum stochastic games // Journal of Machine Learning Research. — 2003. — Т. 4. — С. 1039—1069.
Brown G. W. Iterative solution of games by fictitious play // Activity Analysis of Production and Allocation, Cowles Commission Monograph No. 13. — Wiley, 1951. — С. 374—376.
Zinkevich M., Johanson M., Bowling M., Piccione C. Regret minimization in games with incomplete information // Advances in Neural Information Processing Systems 20 (NIPS). — 2007. — С. 1729—1736.
Daskalakis C., Goldberg P. W., Papadimitriou C. H. The complexity of computing a Nash equilibrium // SIAM Journal on Computing. — 2009. — Т. 39. — № 1. — С. 195—259.
Balduzzi D., Racaniere S., Martens J., Foerster J., Tuyls K., Graepel T. The mechanics of n-player differentiable games // Proceedings of the 35th International Conference on Machine Learning (ICML). — 2018. — С. 354—363.

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%A0%D0%B0%D0%B2%D0%BD%D0%BE%D0%B2%D0%B5%D1%81%D0%B8%D0%B5_%D0%9D%D1%8D%D1%88%D0%B0»