First-Order Algorithms for Nonlinear Generalized Nash Equilibrium Problems
This work addresses a computational bottleneck in game theory for researchers and practitioners, but it is incremental as it builds on existing asymptotic analyses to provide nonasymptotic bounds.
The paper tackles the problem of computing equilibria in nonlinear generalized Nash equilibrium problems (NGNEPs) with strategy sets defined by constraints, by proposing two first-order algorithms based on quadratic penalty and augmented Lagrangian methods, achieving global convergence guarantees and nonasymptotic complexity bounds in terms of gradient evaluations.
We consider the problem of computing an equilibrium in a class of \textit{nonlinear 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.