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.
Daskalakis, C., Goldberg, P.W. and Papadimitriou, C.H. (2009) The Complexity of Computing a Nash Equilibrium. CommunicationsoftheACM, 52, 89-97. https://doi.org/10.1145/1461928.1461951
[3]
Bowling, M., Burch, N., Johanson, M. and Tammelin, O. (2015) Heads-Up Limit Hold’em Poker Is Solved. Science, 347, 145-149. https://doi.org/10.1126/science.1259433
[4]
Monderer, D. and Shapley, L.S. (1996) Potential Games. GamesandEconomicBehavior, 14, 124-143. https://doi.org/10.1006/game.1996.0044
[5]
Moulin, H. (1976) Cooperation in Mixed Equilibrium. MathematicsofOperationsResearch, 1, 273-286. https://doi.org/10.1287/moor.1.3.273
[6]
Friedman, J.W. (1983) On Characterizing Equilibrium Points in Two-Person Strictly Competitive Games. InternationalJournalofGameTheory, 12, 245-247. https://doi.org/10.1007/BF01769094
[7]
Kojima, M., Mizuno, S. and Yoshise, A. (1989) A Primal-Dual Interior Point Algorithm for Linear Programming. In: Megiddo, N., Ed., Progress in Mathematical Programming, Interior Point and Related Methods, Springer, 29-47.
[8]
Griva, I., Nash, S.G. and Sofer, A. (2009) Linear and Nonlinear Optimization. 2nd Edition, SIAM. https://doi.org/10.1137/1.9780898717730
[9]
Mizuno, S. (1992) A Primal-Dual Interior Point Method for Linear Programming. ProceedingsoftheInstituteofStatisticalMathematics, 40, 27-44. (In Japanese)
[10]
Mizuno, S. (1992) A New Polynomial Time Method for a Linear Complementarity Problem. MathematicalProgramming, 56, 31-43. https://doi.org/10.1007/BF01580891
Lustig, I.J., Marsten, R.E. and Shanno, D.F. (1991) Computation Experience with a Primal-Dual Interior Point Method for Linear Programming. Linear Algebra and Its Applications, 152, 191-222. https://doi.org/10.1016/0024-3795(91)90275-2
