文章基本信息

标题：Polynomial Time Method for Solving Nash Equilibria of Zero-Sum Games
本地全文：下载
作者：Yoshihiro Tanaka ; Mitsuru Togashi
期刊名称：American Journal of Computational Mathematics
印刷版ISSN：2161-1203
电子版ISSN：2161-1211
出版年度：2021
卷号：11
期号：1
页码：23-30
DOI：10.4236/ajcm.2021.111002
语种：English
出版社：Scientific Research Publishing
摘要：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