Author(s)

Yoshihiro Tanaka¹, Mitsuru Togashi²

¹Faculty of Economics and Business, Hokkaido University, Sapporo, Japan.
²Graduate School of Accountancy, Waseda University, Tokyo, Japan.

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.

Zero-Sum Games, Nash Equilibria, Karmarkar’s Method, Polynomial Time

Tanaka, Y. and Togashi, M. (2021) Polynomial Time Method for Solving Nash Equilibria of Zero-Sum Games. American Journal of Computational Mathematics, 11, 23-30. doi: 10.4236/ajcm.2021.111002.