First-Order Algorithms for Nonlinear Generalized Nash Equilibrium Problems
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Distributed Nash Equilibrium Seeking for Noncooperative Games of High-Order Nonlinear Multi-Agent Systems Over Weight-Unbalanced Digraphs
In this paper, we investigate the noncooperative games of multi-agent systems. Different from existing noncooperative games, our formulation involves the high-order nonlinear dynamics of players, and the communication to…
Learning generalized Nash equilibria in monotone games: A hybrid adaptive extremum seeking control approach
In this paper, we solve the problem of learning a generalized Nash equilibrium (GNE) in merely monotone games. First, we propose a novel continuous semi-decentralized solution algorithm without projections that uses firs…
Dimension-Free Bounds for Generalized First-Order Methods via Gaussian Coupling
We establish non-asymptotic bounds on the finite-sample behavior of generalized first-order iterative algorithms -- including gradient-based optimization methods and approximate message passing (AMP) -- with Gaussian dat…
Evolutionary Algorithms for Computing Nash Equilibria in Dynamic Games
Dynamic nonzero sum games are widely used to model multi agent decision making in control, economics, and related fields. Classical methods for computing Nash equilibria, especially in linear quadratic settings, rely on …
Decision MakingNash equilibria of games with generalized complementarities
To generalize complementarities for games, we introduce some conditions weaker than quasisupermodularity and the single crossing property. We prove that the Nash equilibria of a game satisfying these conditions form a no…