EUVIMEDEUVIMED entdecken
Crossref

On Finding Local Nash Equilibria (and only Local Nash Equilibria) in Zero-Sum Games

Eric Mazumdar, S. Shankar Sastry, Michael I. Jordan

ACM / IMS Journal of Data Science · 2025

DOI: 10.1145/3728479 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM / IMS Journal of Data Science, 2025. Verfasst von Eric Mazumdar und 2 weiteren Autor:innen. Die Arbeit wurde bisher 2-mal zitiert (Crossref) und nennt 51 Literaturangaben. Gefördert von: NSF.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We propose local symplectic surgery , a two-timescale procedure for finding local Nash equilibria in two-player zero-sum games. We first show that previous gradient-based algorithms cannot guarantee convergence to local Nash equilibria due to the existence of non-Nash stationary points. By taking advantage of the differential structure of the game, we construct an algorithm for which the local Nash equilibria are the only attracting fixed points. Further, we show that the algorithm exhibits no oscillatory behavior in neighborhoods of equilibria and that it has the same per-iteration complexity as other recently proposed algorithms. Furthermore, we give convergence rates in structured classes of zero-sum games. We conclude by validating the algorithm on two numerical examples: a toy example with multiple Nash equilibria and a non-Nash equilibrium, and the training of a small generative adversarial network (GAN).

Förderung

  • NSF

Zitieren

APA

Mazumdar, E., Sastry, S. S., & Jordan, M. I. (2025). On Finding Local Nash Equilibria (and only Local Nash Equilibria) in Zero-Sum Games. ACM / IMS Journal of Data Science. https://doi.org/10.1145/3728479

Vancouver

Mazumdar E, Sastry SS, Jordan MI. On Finding Local Nash Equilibria (and only Local Nash Equilibria) in Zero-Sum Games. ACM / IMS Journal of Data Science. 2025. doi:10.1145/3728479

BibTeX
@article{Mazumdar2025,
  author = {Mazumdar, Eric and Sastry, S. Shankar and Jordan, Michael I.},
  title = {On Finding Local Nash Equilibria (and only Local Nash Equilibria) in Zero-Sum Games},
  journal = {ACM / IMS Journal of Data Science},
  year = {2025},
  doi = {10.1145/3728479}
}
Kostenlos starten →