Under the auspices of the Computational Complexity Foundation (CCF)

TR05-115 | 27th September 2005

The complexity of computing a Nash equilibrium

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 >>>

TR05-134 | 17th November 2005
Xi Chen, Xiaotie Deng

more >>>

TR05-139 | 21st November 2005

Three-Player Games Are Hard

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.

more >>>

TR05-140 | 30th November 2005
Xi Chen, Xiaotie Deng

Settling the Complexity of 2-Player Nash-Equilibrium

Revisions: 1

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

more >>>

TR06-023 | 7th February 2006
Xi Chen, Xiaotie Deng, Shang-Hua Teng

Computing Nash Equilibria: Approximation and Smoothed Complexity

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 >>>

TR06-037 | 10th February 2006
Xi Chen, Xiaotie Deng

On the Complexity of 2D Discrete Fixed Point Problem

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 >>>

ISSN 1433-8092 | Imprint