Game Theoretic Optimization via Gradient-based Nikaido-Isoda Function

Computing the Nash equilibrium (NE) of multi-player games has witnessed
renewed interest due to the recent advances in generative adversarial networks. For non-convex optimization formulations involving such games, a technique to analyze the quality of a solution is to resort to merit functions, among which the Nikaido-Isoda (NI) function is a suitable choice -- this function is positive and goes to zero only when each player is at their optima. However, computing equilibrium conditions efficiently is challenging. To this end, we introduce the Gradient-based Nikaido-Isoda (GNI) function which serves: (i) as a merit function,
vanishing only at the first order stationary points of each player's optimization problem, and (ii) provides error bounds to a first-order NE. Specifically, for bilinear min-max games and multi-player quadratic games, a reformulation using the GNI function results in convex optimization objectives -- the application of gradient descent on such reformulations yield linear convergence to an NE. For the general case, we provide conditions under which the gradient descent provides sub-linear convergence. We show experiments on different multi-player game settings, demonstrating the effectiveness of our scheme against other popular game-theoretic optimization methods.