ECCC - TR05-139

ECCC

Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login

Register

Classic Style

REPORTS > DETAIL:

Paper:

TR05-139 | 21st November 2005 00:00

Three-Player Games Are Hard

Contact

Add Comment

TR05-139 Authors: Constantinos Daskalakis, Christos H. Papadimitriou
Publication: 29th November 2005 04:53
Downloads: 4035

Keywords:

Graphical Game, Nash equilibrium, PPAD-complete, Three Player Game

Abstract:

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.

ISSN 1433-8092 | Imprint