Reducibility among equilibrium problems

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.

Authors

• Paul W. Goldberg
• Christos H. Papadimitriou

Keywords

No keywords are indexed for this paper.