REPORTS > KEYWORD > GRAPHICAL GAME:
Reports tagged with Graphical Game:
TR05-134
| 17th November 2005
Xi Chen, Xiaotie Deng
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
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 >>>