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. LinkChen, 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

## No comments:

## Post a Comment

Note: Only a member of this blog may post a comment.