Under the auspices of the Computational Complexity Foundation (CCF)
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.