Game Theoretic Optimization via Gradient-based Nikaido-Isoda Function
Arvind Raghunathan · Anoop Cherian · Devesh Jha

Tue Jun 11th 11:20 -- 11:25 AM @ Room 102

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.

Author Information

Arvind Raghunathan (Mitsubishi Electric Research Laboratories)
Anoop Cherian (MERL)
Devesh Jha (Mitsubishi Electric Research Labs)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors