Software & Data Downloads — GNI

Computing Nash equilibrium (NE) of multiplayer games has witnessed renewed interest due to recent advances in generative adversarial networks (GAN). However, computing equilibrium efficiently is challenging. To this end, we introduce the Gradient-based Nikaido-Isoda (GNI) function which serves as a merit function, vanishing only at the first-order stationary points of each player’s optimization problem. Gradient descent is shown to converge sublinearly to a first-order stationary point of the GNI function. For the particular case of bilinear min-max games and multi-player quadratic games, the GNI function is convex. Hence, the application of gradient descent in this case yields linear convergence to an NE (when one exists).

This code takes as input the players' payoff functions and reformulates the game objective using the GNI formulation, which is then solved via gradient descent. We provide code to simulate four standard games: (i) bilinear min-max games, (ii) convex quadratic programs, (iii) non-convex quadratic programs, and (iv) strictly-convex quadratic programs. We also provide code to simulate a linear generative adversarial network and solve it using the GNI reformulation. Our software can work with any number of players. The approach presented in this code was published in the 2019 International Conference on Machine Learning (ICML) in a paper titled "Game Theoretic Optimization via Gradient-based Nikaido Isoda function

• Related Publications

   Raghunathan, A., Cherian, A., Jha, D.K., "Game Theoretic Optimization via Gradient-based Nikaido-Isoda Function", International Conference on Machine Learning (ICML), Lawrence, N. and Reid, M., Eds., June 2019, pp. 5291-5300.

  BibTeX TR2019-045 PDF Software

  • @inproceedings{Raghunathan2019jun,
  • author = {Raghunathan, Arvind and Cherian, Anoop and Jha, Devesh K.},
  • title = {Game Theoretic Optimization via Gradient-based Nikaido-Isoda Function},
  • booktitle = {International Conference on Machine Learning (ICML)},
  • year = 2019,
  • editor = {Lawrence, N. and Reid, M.},
  • pages = {5291--5300},
  • month = jun,
  • publisher = {PMLR},
  • issn = {2640-3498},
  • url = {https://www.merl.com/publications/TR2019-045}
  • }

Access software at https://github.com/merlresearch/GNIGAN.