Game Theoretic Optimization via Gradient-based Nikaido-Isoda Function

Arvind Raghunathan, Anoop Cherian, Devesh Jha
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:5291-5300, 2019.

Abstract

Computing Nash equilibrium (NE) of multi-player 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 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 stationary Nash point. 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). In our numerical experiments, we observe that the GNI formulation always converges to the first-order stationary point of each player’s optimization problem.

Cite this Paper

BibTeX
@InProceedings{pmlr-v97-raghunathan19a, title = {Game Theoretic Optimization via Gradient-based Nikaido-Isoda Function}, author = {Raghunathan, Arvind and Cherian, Anoop and Jha, Devesh}, booktitle = {Proceedings of the 36th International Conference on Machine Learning}, pages = {5291--5300}, year = {2019}, editor = {Chaudhuri, Kamalika and Salakhutdinov, Ruslan}, volume = {97}, series = {Proceedings of Machine Learning Research}, month = {09--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v97/raghunathan19a/raghunathan19a.pdf}, url = {https://proceedings.mlr.press/v97/raghunathan19a.html}, abstract = {Computing Nash equilibrium (NE) of multi-player 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 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 stationary Nash point. 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). In our numerical experiments, we observe that the GNI formulation always converges to the first-order stationary point of each player’s optimization problem.} }
Endnote
%0 Conference Paper %T Game Theoretic Optimization via Gradient-based Nikaido-Isoda Function %A Arvind Raghunathan %A Anoop Cherian %A Devesh Jha %B Proceedings of the 36th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Ruslan Salakhutdinov %F pmlr-v97-raghunathan19a %I PMLR %P 5291--5300 %U https://proceedings.mlr.press/v97/raghunathan19a.html %V 97 %X Computing Nash equilibrium (NE) of multi-player 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 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 stationary Nash point. 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). In our numerical experiments, we observe that the GNI formulation always converges to the first-order stationary point of each player’s optimization problem.
APA
Raghunathan, A., Cherian, A. & Jha, D.. (2019). Game Theoretic Optimization via Gradient-based Nikaido-Isoda Function. Proceedings of the 36th International Conference on Machine Learning, in Proceedings of Machine Learning Research 97:5291-5300 Available from https://proceedings.mlr.press/v97/raghunathan19a.html.

Related Material