Second-Order Algorithms for Finding Local Nash Equilibria in Zero-Sum Games
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915517672980480 |
|---|---|
| author | Gupta, Kushagra Liu, Xinjie Allen, Ross Topcu, Ufuk Fridovich-Keil, David |
| author_facet | Gupta, Kushagra Liu, Xinjie Allen, Ross Topcu, Ufuk Fridovich-Keil, David |
| contents | Zero-sum games arise in a wide variety of problems, including robust optimization and adversarial learning. However, algorithms deployed for finding a local Nash equilibrium in these games often converge to non-Nash stationary points. This highlights a key challenge: for any algorithm, the stability properties of its underlying dynamical system can cause non-Nash points to be potential attractors. To overcome this challenge, algorithms must account for subtleties involving the curvatures of players' costs. To this end, we leverage dynamical system theory and develop a second-order algorithm for finding a local Nash equilibrium in the smooth, possibly nonconvex-nonconcave, zero-sum game setting. First, we prove that this novel method guarantees convergence to only local Nash equilibria with an asymptotic local \textit{linear} convergence rate. We then interpret a version of this method as a modified Gauss-Newton algorithm with local \textit{superlinear} convergence to the neighborhood of a point that satisfies first-order local Nash equilibrium conditions. In comparison, current related state-of-the-art methods with similar guarantees do not offer convergence rates in the nonconvex-nonconcave setting. Furthermore, we show that this approach naturally generalizes to settings with convex and potentially coupled constraints while retaining earlier guarantees of convergence to only local (generalized) Nash equilibria. Code for our experiments can be found at https://github.com/CLeARoboticsLab/ZeroSumGameSolve.jl. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_03565 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Second-Order Algorithms for Finding Local Nash Equilibria in Zero-Sum Games Gupta, Kushagra Liu, Xinjie Allen, Ross Topcu, Ufuk Fridovich-Keil, David Computer Science and Game Theory Multiagent Systems Systems and Control Zero-sum games arise in a wide variety of problems, including robust optimization and adversarial learning. However, algorithms deployed for finding a local Nash equilibrium in these games often converge to non-Nash stationary points. This highlights a key challenge: for any algorithm, the stability properties of its underlying dynamical system can cause non-Nash points to be potential attractors. To overcome this challenge, algorithms must account for subtleties involving the curvatures of players' costs. To this end, we leverage dynamical system theory and develop a second-order algorithm for finding a local Nash equilibrium in the smooth, possibly nonconvex-nonconcave, zero-sum game setting. First, we prove that this novel method guarantees convergence to only local Nash equilibria with an asymptotic local \textit{linear} convergence rate. We then interpret a version of this method as a modified Gauss-Newton algorithm with local \textit{superlinear} convergence to the neighborhood of a point that satisfies first-order local Nash equilibrium conditions. In comparison, current related state-of-the-art methods with similar guarantees do not offer convergence rates in the nonconvex-nonconcave setting. Furthermore, we show that this approach naturally generalizes to settings with convex and potentially coupled constraints while retaining earlier guarantees of convergence to only local (generalized) Nash equilibria. Code for our experiments can be found at https://github.com/CLeARoboticsLab/ZeroSumGameSolve.jl. |
| title | Second-Order Algorithms for Finding Local Nash Equilibria in Zero-Sum Games |
| topic | Computer Science and Game Theory Multiagent Systems Systems and Control |
| url | https://arxiv.org/abs/2406.03565 |