The complexity of computing a Nash equilibrium. (English) Zbl 1185.91019

The authors resolve the question that finding a Nash equilibrium in a three players game is indeed PPAD-complete which is established by a solid theoretical and mathematical foundation. A number of propositions, lemmas, theorems are proposed and presented with some illustration. Some of the algorithms developed are not performed for illustration. May be the authors will take it up in subsequent research papers. It is an interesting paper for researchers in the area of game theory.


91A05 2-person games
91A10 Noncooperative games
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Full Text: DOI Link