Learning Generalized Nash Equilibria in Non-Monotone Games with Quadratic Costs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908725184299008 |
|---|---|
| author | Tatarenko, Tatiana Hacker, Lucas Wey |
| author_facet | Tatarenko, Tatiana Hacker, Lucas Wey |
| contents | We study generalized Nash equilibrium (GNE) problems in games with quadratic costs and individual linear equality constraints. Departing from approaches that require strong monotonicity and/or shared constraints, we reformulate the KKT conditions of the (generally non-monotone) games into a tractable convex program whose objective satisfies the Polyak-Lojasiewicz (PL) condition. This PL geometry enables a distributed gradient method over a fixed communication graph with global geometric (linear) convergence to a GNE. When gradient information is unavailable or costly, we further develop a zero-order fully distributed scheme in which each player uses only local cost evaluations and their own constraint residuals. With an appropriate step size policy, the proposed zero-order method converges to a GNE, provided one exists, at rate O(1/t). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_18330 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Learning Generalized Nash Equilibria in Non-Monotone Games with Quadratic Costs Tatarenko, Tatiana Hacker, Lucas Wey Optimization and Control We study generalized Nash equilibrium (GNE) problems in games with quadratic costs and individual linear equality constraints. Departing from approaches that require strong monotonicity and/or shared constraints, we reformulate the KKT conditions of the (generally non-monotone) games into a tractable convex program whose objective satisfies the Polyak-Lojasiewicz (PL) condition. This PL geometry enables a distributed gradient method over a fixed communication graph with global geometric (linear) convergence to a GNE. When gradient information is unavailable or costly, we further develop a zero-order fully distributed scheme in which each player uses only local cost evaluations and their own constraint residuals. With an appropriate step size policy, the proposed zero-order method converges to a GNE, provided one exists, at rate O(1/t). |
| title | Learning Generalized Nash Equilibria in Non-Monotone Games with Quadratic Costs |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2512.18330 |