Settling the Complexity of Computing Two-Player Nash Equilibria

Xi Chen, Xiaotie Deng, Shang-Hua Teng

We settle a long-standing open question in algorithmic game theory. We prove that Bimatrix, the problem of finding a Nash equilibrium in a two-player game, is complete for the comp…