Game theory complexity and computing Nash Equilibrium

In 1944 von Neumann and Morgenstern introduced the subject of Game Theory in their book Theory of Games and Economic Behavior.  von Neumann and Morgenstern showed that there always exists a equilibrium solution to any two-person zero-sum game.   (They also showed any n-person non-zero-sum game can be trivially turned into a (n+1)-person zero-sum game by adding a player who represents the net global profit or loss.)  Nash extended this work to show that there exists a equilibrium for any (zero or non-zero-sum) n-person game.  (A Nash Equilibrium is a set of mixed strategies for the players such that each individual player has perfect knowledge of the other players' strategies and has no benefit from changing their strategy unilaterally under this knowledge.)

However, Nash's proof is not constructive in a computational sense, in that it does not imply a general algorithm for determining the equilibrium point for an arbitrary game. There is good reason for this.  We can show that there is no general algorithm for determining the equilibrium of a given game on the reals.

We must first give a definition of what we mean by a computable real.  In this analysis, I will use the definition given in Computability in Analysis and Physics by Pour-El and Richards.  We say a real number x is computable if there exists a computable sequence of rationals that converge effectively to x.  (Converges effectively means that for some sequence of rationals ${r}_k$ there is a computable function $e$:$\mathbb{N}\to\mathbb{N}$  such that for all $N$, $k \geq e(N)$ implies $|{r}_k-x|\leq {2}^{-N}$ )  A computable sequence of reals is defined similarly (There is a computable double sequence of rationals $\{{r}_nk\}$  that converges effectively to ${x}_n$ as $n,k\rightarrow \inf$ )  Finally, a computable function is defined by saying that every computable sequence of inputs ${x}_n$  yields a computable sequence of outputs $f({x}_n)$, and that the function is effectively uniformly continuous.  (Generally, given a computable function $d(n)$, for all $x,y\in \mathbb{R}$, $|x-y|\leq d(n)\implies |f(x)-f(y)|\leq {2}^{-n}$.) 

Now that we have a framework to examine computability in the reals, we can move to the question of the computability of Nash equilibrium.  Obviously, if the payoffs are given as uncomputable functions, determining an equilibrium is also uncomputable.  However, if every payoff is computable, there does exist a computable equilibrium.  The proof relies on the fact that we can generate a function that is maximized at the equilibrium of the game ($h(s)$), and we can computably determine the maximal value of a computable function.   From this we can get finer and finer approximations of the maximal input to the function (since $h$ is effectively uniformly continuous), thus generating a sequence that converges to a maximal input.

But, we can also show that not every sequence of computable games is computable.  This implies that there is no general procedure to compute Nash equilibrium (The proof of this relies on constructing a sequence of computable games that are not computable by using payoffs generated from two recursively inseparable sets and then showing a computable equilibrium sequence would separate them.)

We can do one better by showing that for a limited set of games, given a computable sequence of strategies for one player, the sequence of best response strategies for the other player is not computable.  (Motivation for this is the idea that actually playing a game involves observing the opponent's strategy over time and computing a best response.)  The proof involves showing the result for a specific, simple game.

Allowing players to make some amount of error in their responses does lead to computable strategies, however.  Consider the logistic quantal response function: ${\sigma}_{ij}(\pi)=(exp(\lambda u_{ij}(\pi))/(\sum_{k\in A_{i}}   exp(\lambda u_{ik}(\pi)))$,  where $u_{ij}(\pi)$  is the payoff to $i$ from using pure strategy $j$ given a strategy profile (list of all player's strategies) $\pi$, and $A_{i}$ is the set of actions available to $i$.  If we allow players to choose strategies with probabilities given by the logistic quantal response function for a given $\lambda$, instead of choosing a best response with certainty, then we can generate a computable "equilibrium".  Note however, that no matter how tight we make this function, we have no guarantees that the resulting strategies are anywhere near a true equilibrium.

Looking at the problem of Nash equilibrium from another viewpoint entirely, we can examine the complexity of  $\epsilon$-equilibrium.  An $\epsilon$-Nash equilibrium is one in which each player has knowledge of other player's strategies and has at most an $epsilon$ benefit from changing their strategies under this knowledge.  By taking $\epsilon=1/{2}^k$ for $k$ related to the length of the description of the given game, we can show that $r$-player $\epsilon$-Nash equilibrium is complete for the class PPAD.

PPAD is defined as (taken from Wikipedia): 

G is a (possibly exponentially large) directed graph with no isolated vertices, and with every vertex having at most one predecessor and one successor. G is specified by giving a polynomial-time computable function f(v) that returns the predecessor and successor (if they exist) of the vertex v. Given a vertex s in G with no predecessor, find a vertex t≠s with no predecessor or no successor. In other words, we want any source or sink of the directed graph other than s.  

PPAD is a subclass of TFNP, which is the set of FNP problems that are total. (A binary relation P(x,y) is in TFNP if and only if there is a deterministic polynomial time algorithm that can determine whether P(x,y) holds given both x and y, and for every x, there exists a y such that P(x,y) holds. (again, taken from Wikipedia))

The proof that  $r$-player $\epsilon$-Nash equilibrium is PPAD-complete was show in a sequence of papers that first showed that 4-or-more player games can be reduced to 4-player graphical games (graphical games are ones in which the players can be viewed as vertices on a graph, and each player's payoffs are only related to the actions of that player's direct graphical neighbors), and then showing that 4-player games are PPAD-complete by reducing another PPAD-complete problem to it, and then separate proofs were given for 3 and 2-player games.

This work places Nash equilibrium into a concrete place in the complexity hierarchy as well as expanding the interest and scope of the class PPAD.

References:

Prasad, Kislaya. "The rationality/computability trade-off in finite games." Journal of Economic Behavior & Organization 69(2009): 17-26. Print.  Link

Chen, Xi; Deng, Xiaotie "Settling the complexity of 2-player Nash equilibrium" Electronic Colloquium on Computational Complexity, Revision 1 of Report No. 140  Link

Daskalakis, Constantinos; Goldberg, Paul W.; Papadimitriou, Christos H. "The complexity of computing Nash equilibrium" Link

-Kevin Mc Inerney