# Game Theoretic Optimization via Gradient-based Nikaido-Isoda Function

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 May 2019.

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

- [Learning in Congestion Games with Bandit Feedback](https://mlsanity.com/paper/2206.01880/) (2022)
- [Adversarial Training for Process Reward Models](https://mlsanity.com/paper/2511.22888/) (2025)
- [Robust Forecasting for Robotic Control: A Game-Theoretic Approach](https://mlsanity.com/paper/2209.10802/) (2022)
- [Global Nash Equilibrium in Non-convex Multi-player Game: Theory and Algorithms](https://mlsanity.com/paper/2301.08015/) (2023)
- [ApproxED: Approximate exploitability descent via learned best responses](https://mlsanity.com/paper/2301.08830/) (2023)
- [Large deviations for interacting particle dynamics for finding mixed equilibria in zero-sum games](https://mlsanity.com/paper/2206.15177/) (2022)

## Abstract (arXiv)

Computing Nash equilibrium (NE) of multi-player games has witnessed renewed interest due to recent advances in generative adversarial networks. However, computing equilibrium efficiently is challenging. To this end, we introduce the Gradient-based Nikaido-Isoda (GNI) function which serves: (i) as a merit function, vanishing only at the first-order stationary points of each player's optimization problem, and (ii) provides error bounds to a stationary Nash point. Gradient descent is shown to converge sublinearly to a first-order stationary point of the GNI function. For the particular case of bilinear min-max games and multi-player quadratic games, the GNI function is convex. Hence, the application of gradient descent in this case yields linear convergence to an NE (when one exists). In our numerical experiments, we observe that the GNI formulation always converges to the first-order stationary point of each player's optimization problem.