Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Graphical Game:
TR05-134 | 17th November 2005
Xi Chen, Xiaotie Deng

3-NASH is PPAD-Complete

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

TR05-139 | 21st November 2005
Constantinos Daskalakis, Christos H. Papadimitriou

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

ISSN 1433-8092 | Imprint