# Global Nash Equilibrium in Non-convex Multi-player Game: Theory and Algorithms

arXiv: https://arxiv.org/abs/2301.08015 · HTML: https://mlsanity.com/paper/2301.08015/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 80 references that are in the map.
- First posted on arXiv 19 Jan 2023.

## Builds on (most cited first, 28 of 28)

- [On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems](https://mlsanity.com/paper/1906.00331/) (2019)
- [A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning](https://mlsanity.com/paper/1711.00832/) (2017)
- [Training GANs with Optimism](https://mlsanity.com/paper/1711.00141/) (2017)
- [Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods](https://mlsanity.com/paper/1902.08297/) (2019)
- [A Variational Inequality Perspective on Generative Adversarial Networks](https://mlsanity.com/paper/1802.10551/) (2018)
- [The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimization](https://mlsanity.com/paper/1807.03907/) (2018)
- [Multi-Agent Generative Adversarial Imitation Learning](https://mlsanity.com/paper/1807.09936/) (2018)
- [Learning in games with continuous action sets and unknown payoff functions](https://mlsanity.com/paper/1608.07310/) (2016)
- [Weakly-Convex Concave Min-Max Optimization: Provable Algorithms and Applications in Machine Learning](https://mlsanity.com/paper/1810.02060/) (2018)
- [Multi-Agent Adversarial Inverse Reinforcement Learning](https://mlsanity.com/paper/1907.13220/) (2019)
- [Fault-Tolerant Federated Reinforcement Learning with Theoretical Guarantee](https://mlsanity.com/paper/2110.14074/) (2021)
- [Local Stochastic Gradient Descent Ascent: Convergence Analysis and Communication Efficiency](https://mlsanity.com/paper/2102.13152/) (2021)
- [Topology-aware Generalization of Decentralized SGD](https://mlsanity.com/paper/2206.12680/) (2022)
- [The Approximate Duality Gap Technique: A Unified Theory of First-Order Methods](https://mlsanity.com/paper/1712.02485/) (2017)
- [Structured Low-Rank Matrix Factorization: Global Optimality, Algorithms, and Applications](https://mlsanity.com/paper/1708.07850/) (2017)
- [Interaction-aware Multi-agent Tracking and Probabilistic Behavior Prediction via Adversarial Learning](https://mlsanity.com/paper/1904.02390/) (2019)
- [Triple Generative Adversarial Networks](https://mlsanity.com/paper/1912.09784/) (2019)
- [Benefits of Permutation-Equivariance in Auction Mechanisms](https://mlsanity.com/paper/2210.05579/) (2022)
- [Game Theoretic Optimization via Gradient-based Nikaido-Isoda Function](https://mlsanity.com/paper/1905.05927/) (2019)
- [On Stochastic Subgradient Mirror-Descent Algorithm with Weighted Averaging](https://mlsanity.com/paper/1307.1879/) (2013)
- [Asynchronous Schemes for Stochastic and Misspecified Potential Games and Nonconvex Optimization](https://mlsanity.com/paper/1711.03963/) (2017)
- [Variance Reduced methods for Non-convex Composition Optimization](https://mlsanity.com/paper/1711.04416/) (2017)
- [Distributed Algorithms for Aggregative Games on Graphs](https://mlsanity.com/paper/1605.00267/) (2016)
- [A distributed primal-dual algorithm for computation of generalized Nash equilibria with shared affine coupling constraints via operator splitting methods](https://mlsanity.com/paper/1703.05388/) (2017)
- [Approximate Nash equilibria in large nonconvex aggregative games](https://mlsanity.com/paper/2011.12604/) (2020)
- [Canonical duality for solving general nonconvex constrained problems](https://mlsanity.com/paper/1310.2014/) (2013)
- [Distributed GNE seeking under partial-decision information over networks via a doubly-augmented operator splitting approach](https://mlsanity.com/paper/1808.04465/) (2018)
- [Efficient algorithm for approximating Nash equilibrium of distributed aggregative games](https://mlsanity.com/paper/2108.12142/) (2021)

## Built on by (most cited first, 1 of 1)

- [Communication-Efficient Gradient Descent-Accent Methods for Distributed Variational Inequalities: Unified Analysis and Local Updates](https://mlsanity.com/paper/2306.05100/) (2023)

## Abstract (arXiv)

Wide machine learning tasks can be formulated as non-convex multi-player games, where Nash equilibrium (NE) is an acceptable solution to all players, since no one can benefit from changing its strategy unilaterally. Attributed to the non-convexity, obtaining the existence condition of global NE is challenging, let alone designing theoretically guaranteed realization algorithms. This paper takes conjugate transformation to the formulation of non-convex multi-player games, and casts the complementary problem into a variational inequality (VI) problem with a continuous pseudo-gradient mapping. We then prove the existence condition of global NE: the solution to the VI problem satisfies a duality relation. Based on this VI formulation, we design a conjugate-based ordinary differential equation (ODE) to approach global NE, which is proved to have an exponential convergence rate. To make the dynamics more implementable, we further derive a discretized algorithm. We apply our algorithm to two typical scenarios: multi-player generalized monotone game and multi-player potential game. In the two settings, we prove that the step-size setting is required to be O(1/k) and O(1/√ k) to yield the convergence rates of O(1/ k) and O(1/√ k), respectively. Extensive experiments in robust neural network training and sensor localization are in full agreement with our theory.