Why is computing pure Nash equilibria NP-complete?

Question

In this paper, it is claimed that computing pure-strategy Nash equilibria of games in standard normal form is NP-complete.

This confuses me, because I do not understand why it is hard to guess the right strategy profile (the authors call this the "global strategy") for a game. Surely if the Nash equilibrium of a game is written out in normal form, where every strategy profile is assigned its own cell, then it should take only linear time to run through every possible strategy profile that is a candidate for being a Nash equilibrium.

I do not understand what I am missing; please explain why Nash equilibrium computation is hard for standard normal form games. Thank you.

Answer 1

These are my two comments as an answer:

Of course you are right that if the strategic form (also called the normal form) is given explicitly then one can just check all pure strategy profiles. In that case, the problem of deciding if there is a pure equilibrium is clearly not likely to be NP-hard.

However, the paper shows in Theorem 3.1 hardness for graphical games (called in the paper, games in graphical normal form (GNF)), which are succinctly represented games. (It might not be the best phrasing in the statement of Theorem 3.1 to say "even for", which is fine as regards constant values of parameters, but not for the representation type itself).

In general, if each of $n$ players has $m$ actions then the the strategic form has $nm^n$ entries, but a graphical game has $O(nm^{d+1})$, where $d$ is the maximum degree in the graph. So for constant $d$, the graphical game representation is exponentially smaller than the strategic form. In their reduction $d$ can be 3 (and $m$ can also be 3, so only $n$ needs to vary).

For the strategic form (standard normal form, SNF, as they call it in the paper) they show that the problem is easy (Theorem 5.1), which is straightforward as you noted.

SNF and GNF are compared on page 6 of the paper.