Polynomial Time Method for Solving Nash Equilibria of Zero-Sum Games

• 作者: Yoshihiro Tanaka Mitsuru Togashi
• 来源期刊: 美国计算数学期刊(英文)
• 学科: 数学
• 关键词: Zero-Sum Games Nash Equilibria Karmarkar’s Method Polynomial Time
• 年，卷（期）: 2021,（1）
• 页码范围: 23-30
• 页数: 8页
• 分类号: O17

摘要

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.