An Exponentially Converging Particle Method for the Mixed Nash Equilibrium of Continuous Games
We consider the problem of computing mixed Nash equilibria of two-player zero-sum games with continuous sets of pure strategies and with first-order access to the payoff function. This problem arises for example in game-theory-inspired machine learning applications, such as distributionally-robust l...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Université de Montpellier
2025-01-01
|
| Series: | Open Journal of Mathematical Optimization |
| Online Access: | https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.37/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1825204986273857536 |
|---|---|
| author | Wang, Guillaume Chizat, Lénaïc |
| author_facet | Wang, Guillaume Chizat, Lénaïc |
| author_sort | Wang, Guillaume |
| collection | DOAJ |
| description | We consider the problem of computing mixed Nash equilibria of two-player zero-sum games with continuous sets of pure strategies and with first-order access to the payoff function. This problem arises for example in game-theory-inspired machine learning applications, such as distributionally-robust learning. In those applications, the strategy sets are high-dimensional and thus methods based on discretisation cannot tractably return high-accuracy solutions. In this paper, we introduce and analyze a particle-based method that enjoys guaranteed local convergence for this problem. This method consists in parametrizing the mixed strategies as atomic measures and applying proximal point updates to both the atoms’ weights and positions. It can be interpreted as an implicit time discretization of the “interacting” Wasserstein–Fisher–Rao gradient flow.We prove that, under non-degeneracy assumptions, this method converges at an exponential rate to the exact mixed Nash equilibrium from any initialization satisfying a natural notion of closeness to optimality. We illustrate our results with numerical experiments and discuss applications to max-margin and distributionally-robust classification using two-layer neural networks, where our method has a natural interpretation as a simultaneous training of the network’s weights and of the adversarial distribution. |
| format | Article |
| id | doaj-art-79554f456bf24ccca22cdeb6ec57a91e |
| institution | Kabale University |
| issn | 2777-5860 |
| language | English |
| publishDate | 2025-01-01 |
| publisher | Université de Montpellier |
| record_format | Article |
| series | Open Journal of Mathematical Optimization |
| spelling | doaj-art-79554f456bf24ccca22cdeb6ec57a91e2025-02-07T14:03:15ZengUniversité de MontpellierOpen Journal of Mathematical Optimization2777-58602025-01-01616610.5802/ojmo.3710.5802/ojmo.37An Exponentially Converging Particle Method for the Mixed Nash Equilibrium of Continuous GamesWang, Guillaume0Chizat, Lénaïc1Institute of Mathematics, École polytechnique fédérale de Lausanne (EPFL), Station Z, CH-1015 LausanneInstitute of Mathematics, École polytechnique fédérale de Lausanne (EPFL), Station Z, CH-1015 LausanneWe consider the problem of computing mixed Nash equilibria of two-player zero-sum games with continuous sets of pure strategies and with first-order access to the payoff function. This problem arises for example in game-theory-inspired machine learning applications, such as distributionally-robust learning. In those applications, the strategy sets are high-dimensional and thus methods based on discretisation cannot tractably return high-accuracy solutions. In this paper, we introduce and analyze a particle-based method that enjoys guaranteed local convergence for this problem. This method consists in parametrizing the mixed strategies as atomic measures and applying proximal point updates to both the atoms’ weights and positions. It can be interpreted as an implicit time discretization of the “interacting” Wasserstein–Fisher–Rao gradient flow.We prove that, under non-degeneracy assumptions, this method converges at an exponential rate to the exact mixed Nash equilibrium from any initialization satisfying a natural notion of closeness to optimality. We illustrate our results with numerical experiments and discuss applications to max-margin and distributionally-robust classification using two-layer neural networks, where our method has a natural interpretation as a simultaneous training of the network’s weights and of the adversarial distribution.https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.37/ |
| spellingShingle | Wang, Guillaume Chizat, Lénaïc An Exponentially Converging Particle Method for the Mixed Nash Equilibrium of Continuous Games Open Journal of Mathematical Optimization |
| title | An Exponentially Converging Particle Method for the Mixed Nash Equilibrium of Continuous Games |
| title_full | An Exponentially Converging Particle Method for the Mixed Nash Equilibrium of Continuous Games |
| title_fullStr | An Exponentially Converging Particle Method for the Mixed Nash Equilibrium of Continuous Games |
| title_full_unstemmed | An Exponentially Converging Particle Method for the Mixed Nash Equilibrium of Continuous Games |
| title_short | An Exponentially Converging Particle Method for the Mixed Nash Equilibrium of Continuous Games |
| title_sort | exponentially converging particle method for the mixed nash equilibrium of continuous games |
| url | https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.37/ |
| work_keys_str_mv | AT wangguillaume anexponentiallyconvergingparticlemethodforthemixednashequilibriumofcontinuousgames AT chizatlenaic anexponentiallyconvergingparticlemethodforthemixednashequilibriumofcontinuousgames AT wangguillaume exponentiallyconvergingparticlemethodforthemixednashequilibriumofcontinuousgames AT chizatlenaic exponentiallyconvergingparticlemethodforthemixednashequilibriumofcontinuousgames |