Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR05-090 | 17th August 2005 00:00

Reducibility Among Equilibrium Problems

RSS-Feed




TR05-090
Authors: Paul Goldberg, Christos H. Papadimitriou
Publication: 17th August 2005 18:26
Downloads: 4492
Keywords: 


Abstract:

We address the fundamental question of whether the Nash equilibria of
a game can be computed in polynomial time. We describe certain
efficient reductions between this problem for
normal form games with a fixed number of players
and graphical games with fixed degree. Our main result is that the
problem of solving a game for any constant number of players, is
reducible to solving a 4-player game.



ISSN 1433-8092 | Imprint