# First-Order Algorithms for Nonlinear Generalized Nash Equilibrium Problems

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 111 references that are in the map.
- First posted on arXiv 7 Apr 2022.

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

- [Learning in games with continuous action sets and unknown payoff functions](https://mlsanity.com/paper/1608.07310/) (2016)
- [Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems](https://mlsanity.com/paper/1808.02901/) (2018)
- [Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalities](https://mlsanity.com/paper/2002.08872/) (2020)
- [Simple and optimal methods for stochastic variational inequalities, I: operator extrapolation](https://mlsanity.com/paper/2011.02987/) (2020)
- [Accelerated Schemes For A Class of Variational Inequalities](https://mlsanity.com/paper/1403.4164/) (2014)
- [Projected Reflected Gradient Methods for Monotone Variational Inequalities](https://mlsanity.com/paper/1502.04968/) (2015)
- [Iteration complexity of inexact augmented Lagrangian methods for constrained convex programming](https://mlsanity.com/paper/1711.05812/) (2017)
- [Computational Results for Extensive-Form Adversarial Team Games](https://mlsanity.com/paper/1711.06930/) (2017)
- [Structured Nonconvex and Nonsmooth Optimization: Algorithms and Iteration Complexity Analysis](https://mlsanity.com/paper/1605.02408/) (2016)
- [Complexity of first order inexact Lagrangian and penalty methods for conic convex programming](https://mlsanity.com/paper/1506.05320/) (2015)
- [A Simple Parallel Algorithm with an O(1/t) Convergence Rate for General Convex Programs](https://mlsanity.com/paper/1512.08370/) (2015)
- [Coordination in Adversarial Sequential Team Games via Multi-Agent Deep Reinforcement Learning](https://mlsanity.com/paper/1912.07712/) (2019)
- [Stochastic generalized Nash equilibrium seeking under partial-decision information](https://mlsanity.com/paper/2011.05357/) (2020)
- [Augmented Lagrangian Methods for the Solution of Generalized Nash Equilibrium Problems](https://mlsanity.com/paper/1807.04474/) (2018)
- [Exact Penalization of Generalized Nash Equilibrium Problems](https://mlsanity.com/paper/1811.10674/) (2018)
- [Fast generalized Nash equilibrium seeking under partial-decision information](https://mlsanity.com/paper/2003.09335/) (2020)

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

- [Finite-Time Bounds for Two-Time-Scale Stochastic Approximation with Arbitrary Norm Contractions and Markovian Noise](https://mlsanity.com/paper/2503.18391/) (2025)
- [Online Learning under Adversarial Nonlinear Constraints](https://mlsanity.com/paper/2306.03655/) (2023)
- [Expected Variational Inequalities](https://mlsanity.com/paper/2502.18605/) (2025)
- [Learning to Control Unknown Strongly Monotone Games](https://mlsanity.com/paper/2407.00575/) (2024)
- [Primal Methods for Variational Inequality Problems with Functional Constraints](https://mlsanity.com/paper/2403.12859/) (2024)
- [Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Property](https://mlsanity.com/paper/2312.12067/) (2023)
- [An Online Feasible Point Method for Benign Generalized Nash Equilibrium Problems](https://mlsanity.com/paper/2410.02400/) (2024)
- [Nash Equilibria in Games with Playerwise Concave Coupling Constraints: Existence and Computation](https://mlsanity.com/paper/2509.14032/) (2025)
- [Mirror Descent-Type Algorithms for the Variational Inequality Problem with Functional Constraints](https://mlsanity.com/paper/2605.16262/) (2026)

## Abstract (arXiv)

We consider the problem of computing an equilibrium in a class of textitnonlinear generalized Nash equilibrium problems (NGNEPs) in which the strategy sets for each player are defined by equality and inequality constraints that may depend on the choices of rival players. While the asymptotic global convergence and local convergence rates of algorithms to solve this problem have been extensively investigated, the analysis of nonasymptotic iteration complexity is still in its infancy. This paper presents two first-order algorithms -- based on the quadratic penalty method (QPM) and augmented Lagrangian method (ALM), respectively -- with an accelerated mirror-prox algorithm as the solver in each inner loop. We establish a global convergence guarantee for solving monotone and strongly monotone NGNEPs and provide nonasymptotic complexity bounds expressed in terms of the number of gradient evaluations. Experimental results demonstrate the efficiency of our algorithms in practice.