Game Theoretic Optimization via Gradientbased NikaidoIsoda Function
[edit]
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:52915300, 2019.
Abstract
Computing Nash equilibrium (NE) of multiplayer games has witnessed renewed interest due to recent advances in generative adversarial networks. However, computing equilibrium efficiently is challenging. To this end, we introduce the Gradientbased NikaidoIsoda (GNI) function which serves: (i) as a merit function, vanishing only at the firstorder stationary points of each player’s optimization problem, and (ii) provides error bounds to a stationary Nash point. Gradient descent is shown to converge sublinearly to a firstorder stationary point of the GNI function. For the particular case of bilinear minmax games and multiplayer 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). In our numerical experiments, we observe that the GNI formulation always converges to the firstorder stationary point of each player’s optimization problem.
Related Material


