TITLE:
Nash Equilibrium of a Fixed-Sum Two-Player Game
AUTHORS:
Yoshihiro Tanaka
KEYWORDS:
Nash Equilibrium, Fixed-Sum Two-Player Game, Principal-Dual Interior Point Method
JOURNAL NAME:
American Journal of Computational Mathematics,
Vol.14 No.3,
September
25,
2024
ABSTRACT: It is well established that Nash equilibrium exists within the framework of mixed strategies in strategic-form non-cooperative games. However, finding the Nash equilibrium generally belongs to the class of problems known as PPAD (Polynomial Parity Argument on Directed graphs), for which no polynomial-time solution methods are known, even for two-player games. This paper demonstrates that in fixed-sum two-player games (including zero-sum games), the Nash equilibrium forms a convex set, and has a unique expected payoff. Furthermore, these equilibria are Pareto optimal. Additionally, it is shown that the Nash equilibrium of fixed-sum two-player games can theoretically be found in polynomial time using the principal-dual interior point method, a solution method of linear programming.