September 26, 2005 | Constantinos Daskalakis*, Paul W. Goldberg†, Christos H. Papadimitriou‡
The complexity of computing a Nash equilibrium in games with 4 or more players is shown to be complete for the complexity class PPAD. This result implies that a polynomial-time algorithm for computing Nash equilibria would also imply a polynomial-time algorithm for computing Brouwer fixpoints, which is known to have strong lower bounds. The paper demonstrates that any Brouwer function can be simulated by a game, showing that Nash equilibria correspond to Brouwer fixpoints. The proof uses a reduction from 3-dimensional Brouwer functions to 4-player games, leveraging "arithmetical gadgets" to simulate arithmetic operations. The key challenge is handling brittle comparators at the boundaries of cubelets, which are resolved by averaging over a "microlattice." The paper also shows that 4-NASH is PPAD-complete, completing the reduction from 3-dimensional Brouwer functions to 4-player games. The results highlight the computational difficulty of finding Nash equilibria in games with more than two players, leaving open the question of whether 2-player games can be solved in polynomial time.The complexity of computing a Nash equilibrium in games with 4 or more players is shown to be complete for the complexity class PPAD. This result implies that a polynomial-time algorithm for computing Nash equilibria would also imply a polynomial-time algorithm for computing Brouwer fixpoints, which is known to have strong lower bounds. The paper demonstrates that any Brouwer function can be simulated by a game, showing that Nash equilibria correspond to Brouwer fixpoints. The proof uses a reduction from 3-dimensional Brouwer functions to 4-player games, leveraging "arithmetical gadgets" to simulate arithmetic operations. The key challenge is handling brittle comparators at the boundaries of cubelets, which are resolved by averaging over a "microlattice." The paper also shows that 4-NASH is PPAD-complete, completing the reduction from 3-dimensional Brouwer functions to 4-player games. The results highlight the computational difficulty of finding Nash equilibria in games with more than two players, leaving open the question of whether 2-player games can be solved in polynomial time.