TITLE:
Polynomial Time Method for Solving Nash Equilibria of Zero-Sum Games
AUTHORS:
Yoshihiro Tanaka, Mitsuru Togashi
KEYWORDS:
Zero-Sum Games, Nash Equilibria, Karmarkar’s Method, Polynomial Time
JOURNAL NAME:
American Journal of Computational Mathematics,
Vol.11 No.1,
March
17,
2021
ABSTRACT: There are a few studies that focus on solution methods for finding a Nash equilibrium of zero-sum games. We discuss the use of Karmarkar’s interior point method to solve the Nash equilibrium problems of a zero-sum game, and prove that it is theoretically a polynomial time algorithm. We implement the Karmarkar method, and a preliminary computational result shows that it performs well for zero-sum games. We also mention an affine scaling method that would help us compute Nash equilibria of general zero-sum games effectively.