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
To download the software, please enter some information about yourself, then review and agree to MERL's research-only licensing terms.