Hardness of finding NE
From Theory
Notes for CS 8803 - Game Theory and Computer Science. Spring 2008
Consider the problem of finding a Nash equilibrium in a two-person 
normal-form game, where all entries are rational. By our algorithm for finding Nash equilibrium, we can conclude that any such game must have a Nash equilibrium with probabilities that are rational real numbers. Hence, the problem of 2-NASH means, given a normal form game represented as a pair of matrices with rational values, output a vector of rational numbers that is an equilibrium, i.e., find any Nash equilibrium. We note that the problem of checking whether something is a Nash equilibrium is computationally easy.
The problem (2,ε)-NASH is, given a two-person normal form game and a rational number ε > 0 reprsented as a binary decimal, output a vector of rational numbers which is an ε-NE.
Nobody knows how to solve these two problems.
For N > 2 players, the problem of finding any Nash equilibrium is a bit more tricky to define for a computer. The reason is that there are finite three-player games where all Nash eq. have mixed strategies that consist of irrational numbers. Hence, it is hard to think of how one would represent, in general, the outputs for this problem.
However, for ε equilibrium, this problem makes sense. The problem (N,ε)-NASH is, given an N-person normal form game and a rational number ε > 0 reprsented as a binary decimal, output a vector of rational numbers which is an ε-NE.
The problem of (2,ε)-NASH is as hard as the problem of (N,ε)-NASH.
However, the following problem is a great open problem. Solve (2,ε)-NASH in time polynomial in the size of the game, with no restriction on the runtime in terms of ε.
The production of this material was supported in part by NSF award SES-0734780.
