CaltechAUTHORS
  A Caltech Library Service

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

Mazumdar, Eric and Jordan, Michael I. and Sastry, S. Shankar (2019) On Finding Local Nash Equilibria (and Only Local Nash Equilibria) in Zero-Sum Games. . (Unpublished) https://resolver.caltech.edu/CaltechAUTHORS:20210903-213653378

[img] PDF - Submitted Version
See Usage Policy.

3MB

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20210903-213653378

Abstract

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. We also show that the algorithm exhibits no oscillatory behaviors in neighborhoods of equilibria and show that it has the same per-iteration complexity as other recently proposed algorithms. 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).


Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription
http://arxiv.org/abs/1901.00838arXivDiscussion Paper
ORCID:
AuthorORCID
Mazumdar, Eric0000-0002-1815-269X
Record Number:CaltechAUTHORS:20210903-213653378
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20210903-213653378
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:110719
Collection:CaltechAUTHORS
Deposited By: George Porter
Deposited On:07 Sep 2021 16:23
Last Modified:07 Sep 2021 16:23

Repository Staff Only: item control page