Constantinos Daskalakis, Paul Goldberg, Christos H. Papadimitriou

We resolve the question of the complexity of Nash equilibrium by

showing that the problem of computing a Nash equilibrium in a game

with 4 or more players is complete for the complexity class PPAD.

Our proof uses ideas from the recently-established equivalence

between polynomial-time solvability of normal-form games and

more >>>

Xi Chen, Xiaotie Deng

In this paper, we improve a recent result of Daskalakis, Goldberg and Papadimitriou on PPAD-completeness of 4-Nash, showing that 3-Nash is PPAD-complete.

more >>>Constantinos Daskalakis, Christos H. Papadimitriou

We prove that computing a Nash equilibrium in a 3-player

game is PPAD-complete, solving a problem left open in our recent result on the complexity of Nash equilibria.

Xi Chen, Xiaotie Deng

We prove that finding the solution of two player Nash Equilibrium is PPAD-complete.

more >>>Xi Chen, Xiaotie Deng, Shang-Hua Teng

By proving that the problem of computing a $1/n^{\Theta(1)}$-approximate Nash equilibrium remains \textbf{PPAD}-complete, we show that the BIMATRIX game is not likely to have a fully polynomial-time approximation scheme. In other words, no algorithm with time polynomial in $n$ and $1/\epsilon$ can compute an $\epsilon$-approximate Nash equilibrium of an $n\times ... more >>>

Xi Chen, Xiaotie Deng

While the 3-dimensional analogue of the Sperner problem in the plane was known to be PPAD-complete, the complexity of the 2D-SPERNER itself is not known to be PPAD-complete or not. In this paper, we settle this open problem proposed by Papadimitriou~\cite{PAP90} fifteen years ago. This also allows us to derive ... more >>>