Approximate Nash

June 7, 2009 by algorithmicgametheory

The basic computational problem in algorithmic game theory is that of computing a (mixed) Nash equilibrium of a given (non-cooperative) game. The computational complexity status of this problem has been recently settled by showing that it is “PPAD-complete” and thus “unlikely” to be efficiently computable (see this link for a nice overview). This may be considered as not very satisfying answer due to our incomplete understanding of the class PPAD, but at least the problem is now reduced to be a purely computational complexity one with no game theory aspects to it and no special role for the Nash problem. The main related problem remaining is whether approximating a Nash equilibrium may be done efficiently. This post will describe the current status of the approximation problem.

The approximate-Nash problem

Let us first settle on some notation. We are talking about a $n$ -player game, where each player $i$ has $m_i$ possible strategies, each player has a utility function $u_i : \{1..m_1\} \times \{1..m_2\} \times ... \times \{1..m_n\} \rightarrow \Re$ . We will denote by $\Delta_i$ the set of probability distributions on $\{ 1 ... m_i\}$ and for $x^1 \in \Delta_1 ... x^n \in \Delta_n$ we use $u_i(x^1 ... x^n)$ as a shorthand for $\sum_{j_1, ... , j_n} \Pi_i x^i_{j_i} u_i(j_1 ... j_n)$ , the expected value of $u_i(j_1 ... j_n)$ where each $j_i$ is chosen at random according to the probability $x^i$ .

We know by Nash’s theorem that a mixed Nash equilibrium of the game exists and the computational problem is to find one. Unfortunately, it is also known that when $n \ge 3$ then the Nash equilibria may all be irrational numbers. We thus cannot just ask our algorithm to output a Nash equilibrium since it may not have a finite representation and so we need to settle for approximation in order to even define the “exact” problem. So here is the carefully stated common definition of the Nash equilibrium computation problem:

Input: The input is given by $n$ tables $u_1 ... u_n$ each of dimensions $m_1 \times m_2 \times ... \times m_n$ . For finiteness of representation, each of the $n \Pi_i m_i$ numbers in the input is a rational number given by a $d$ -digit numerator and denominator. We are also give a rational number $\epsilon>0$ (with $d$ -digit numerator and denominator).

Output: $n$ rational vectors $x^1 \in \Delta_1, ..., x^n \in \Delta_n$ that are an $\epsilon$ -Nash equilibrium.

Definition: $x^1, ..., x^n$ are $\epsilon$ -Nash of the game defined by $u_1 ... u_n$ if for every $i$ and every $x^{i*} \in \Delta_i$ we have that $u_i(x^i, x^{-i}) \ge u_i(x^{i*},x^{-i}) - \epsilon$ .

Running time: we want the running time to be polynomial in the input size, i.e. polynomial in $n$ , $d$ , and $\Pi_i m_i$ .

It is quite useful to look carefully at various choices made here, and what we would get with slightly different choices:

Allowing any Nash equilibrium: our definition allowed any ( $\epsilon$ )-Nash rather than specifying which one we desire in case multiple ones exist. It is known that most ways of attempting to require a specific Nash point make the problem harder, NP-complete.
Approximation: as mentioned above when $n \ge 3$ we need to settle for a $\epsilon$ -approximation just to have a finite output. For $n=2$ there always exists an equilibrium which has rational numbers with $poly(d, n, \Pi_i m_i)$ -digit long numerator and denominator, and thus the exact version is equivalent to the problem as stated.
Approximation of best-response condition: our notion for approximation relaxed the best-response condition by $\epsilon$ rather than asking for some rational point that is $\epsilon$ -close to an exact Nash equilibrium point. The latter condition seems to be much harder and in not even known to be in NP (or in fact even in the polynomial time hierarchy) and is treated at length by this 57-page paper by Mihalis Yannakakis and Kousha Etessami. The crux of the difficulty is that getting some grip on an exact Nash point seems to require “infinite precision” arithmetic — the same type of problem encountered in trying to determine whether $\sum_i \sqrt{x_i} > T$ (discussed by Richard Lipton and see also this related post of his). (Thanks to Kousha Etessami for explaining these delicate issues to me.)
Having $\epsilon$ be given in binary: in our definition $\epsilon$ was given by $d$ -digit numerator and denominator and the running time was required to be polynomial in $d$ , i.e. in $\log \epsilon^{-1}$ . An alternative version would be to require $\epsilon$ to be “given in unary” i.e. allow the algorithm to run in time polynomial in $\epsilon^{-1}$ . This version is asking for a fully polynomial approximation scheme (FPTAS) and could be easier. However, it turns out that getting a FPTAS is also PPAD-hard and thus this is actually not the case.
Additive approximation: Our condition demands $u_i(x^i, x^{-i}) \ge u_i(x^{i*},x^{-i}) - \epsilon$ . We can not use the more natural relative error $u_i(x^i, x^{-i}) \ge u_i(x^{i*},x^{-i}) (1 - \epsilon)$ as the Nash equilibrium point $u_i$ may be arbitrarily close to zero which may again require an exponential-length answer.

At this point we can start talking about the approximate version of this problem. For this we will allow an arbitrary dependence of the running time on $\epsilon$ and even allow $\epsilon$ be fixed (e.g. $\epsilon=0.1$ ) . As the original problem scales, for the approximation to make sense, we need to normalize $\epsilon$ by the sizes of the numbers in the probem.

$\epsilon$ -Approximation Problem: This is the same problem as above but scaled so that the utilities all satisfy $0 \le u_i(j_1 ... j_n) \le 1$ .

A Quasi-polynomial-time Algorithm

The key result by Richrad Lipton, Evangelos Marakakis, and Aranyak Metha is that the approximation problem can be solved in “quasi-polynomial” time — in this case time $N^{\log N}$ where $N$ is the input size. The algorithm is very simple and is based on the existence of approximate equilibria with strategies that have only small support. In many “non-uniform” models, randomization over a large domain can be replaced by randomization over a much smaller domain. (One nice example is the simulation of public coins by private ones in communication complexity.) This is the situation here and some background is given in a recent blog post by Richard Lipton.

Definition: Let $k$ be an integer, then a distribution $\tilde{x}^i \in \Delta_i$ is $k$ -simple if all its coordinates are integer multiples of $1/k$ . I.e. it is a uniform distribution on a multi-set of size $k$ of pure strategies. A random $k$ -simplification of $x^i$ is obtained by choosing at random $k$ elements (with repetitions) according to the distribution specified by $x^i$ and then taking the uniform distribution on this multiset.

Proposition: For every $x^1 \in \Delta_1$ and fixed pure strategies $j_2 ... j_n$ , if we chose a random $k$ -simplification $\tilde{x}^1$ of $x^1$ then $Pr[|u_i(\tilde{x}^1,j_2,...,j_n) - u_i(x^1,j_2,...,j_n)| > \epsilon] \le e^{-\Omega(k\epsilon^2)}$ .

The proof is by observing that $u_i(x^1,j_2,...,j_n)$ is the expected value of $u_i(j_1,j_2,...,j_n)$ when $j_1$ is chosen according to $x_1$ , while $u_i(\tilde{x}^1,j_2,...,j_n)$ is the average value of $u_i(j_1,j_2,...,j_n)$ over $k$ random choices of $j_1$ according to $x_1$ , and thus the proposition is just a direct use of the Hoeffding tail inequalities.

Now, if we choose $k = O(\log N / \epsilon^2)$ , where $N=\Pi_i m_i$ , then, with high probability (due to the union bound), the previous proposition holds for all pure strategies $j_2 ... j_n$ and all $u_i$ for $i = 1 ...n$ . In this case, by averaging, it also holds for all mixed strategies $x^2 ... x^n$ :

Definition: $\tilde{x^1}$ is an $\epsilon$ -approximation of $x^1$ (relative to $u_1 ... u_n$ ) if for all $x^{2} \in \Delta_2 .... x^{n} \in \Delta_n$ and all $i$ we have $|u_i(\tilde{x}^1,x^{2},...,x^{n}) - u_i(x^1,x^{2},...,x^{n})| \le \epsilon$ .

Corollary: For every $x^1 \in \Delta_1$ there exists an $\epsilon$ -approximation $\tilde{x}^1$ which is $k$ -simple, for $k = O(\log N / \epsilon^2)$ .

The main lemma now follows:

Lemma: Every game has an $\epsilon$ -Nash equilibrium where all player strategies are $k$ -simple, with $k = O(\log N / \epsilon^2)$ .

The proof starts with any Nash equilibrium $x^1 ... x^n$ and chooses a $k$ -simple $\epsilon'$ -approximation $\tilde{x}^i$ for each $x^i$ (where $\epsilon'=\epsilon/(2n)$ ). Since $x^1 ... x^n$ are an exact Nash equilibrium, in order to show that $\tilde{x^1} ... \tilde{x^n}$ are an approximate equilibrium, it suffices to show that changing the $x^i$ ‘s to $\tilde{x}^i$ ‘s changes things by at most $\epsilon$ — but this is exactly what being an $\epsilon'$ -approximation means for replacing a single $x^i$ by $\tilde{x}^i$ , and the approximation errors $\epsilon'$ ‘s simply add up.

Once the existence of a $k$ -simple $\epsilon$ -equilibrium is known, an $O(n^k)$ algorithm follows simply by exhaustive search, and thus we get our algorithm.

Notice that we have actually shown a stronger theorem: not only can we find some $\epsilon$ -approximation but in fact we can find an approximation to any equilibrium, and our approximated equilibrium maintains also player’s utilities. This for example also provides an approximate equilibrium with approximately optimal social welfare.

A polynomial time algorithm?

The existence of a quasi-polynomial time algorithm may often be viewed as a hint that a polynomial-time algorithm exists as well. In our case the main open problem is whether such a polynomial time algorithm exists for every fixed value of $\epsilon>0$ . The upper bounds for the approximation problem are rater weak and the best that is known is a polynomial time approximation for $\epsilon=0.3393...$ .

One possible approach is to see whether the parameter $k$ above may be reduced to being constant when $\epsilon$ is constant. This however is not the case. Consider a zero-sum two-player game where each utility is chosen at random to be 0 or 1. The following statements can be easily shown to hold with high probability over the random choice of the game: (a) for each row or column, the fraction of 1-entries is very close to 1/2 and thus a value of close to 1/2 can be obtained by any player by using a uniform distribution on his rows or columns (b) for any $k=o(\log n)$ rows there exists a single column which has all 0 entries in these rows. Thus any mixed strategy that is $o(\log n)$ -simple cannot ensure positive value. It follows that there does not exists a $\epsilon$ -approximate Nash which is $k$ -simple for any $\epsilon<1/2$ and $k = o(\log n)$ . A recent paper of Constantinos Daskalakis and Christos Papadimitriou generalizes this impossibility not only to simples strategies but to more general “oblivious” algorithms.

Another difficulty is shown by a recent paper of Elad Hazan and Robert Krauthgamer. They consider the harder problem of approximating a specific Nash equilibrium — specifically the one with highest social welfare — for which the technique above also provides a quasi-polynomial-time algorithm. They show that this problem is at least as hard as the known problem of finding a small randomly planted clique in a graph, providing some evidence for its difficulty.

Posted in Uncategorized | Tagged complexity of equilibria, technical | 11 Comments

11 Responses

on June 8, 2009 at 7:47 am | Reply Anonymous

I have a question unrelated to this post. I have never seen revenue maximizing auctions in the setting of Vickrey’s second price auction, i.e., private values, no probabilistic assumptions about the values, auction of a single item using sealed bids. It would be great if you could explain why that is.
- on June 8, 2009 at 10:44 am | Reply Noam
  
  Indeed unrelated to the post, but the problem is a definitional one: for each specific instance of valuations you can obviously extract the full 1st price, but this cannot be done by a single auction for all valuations, so you need some quantification over players’ valuation. The distributional one is natural and has a developed theory. It is not easy to think of another meaningful quantification in this general setting. In various special cases interesting competitive results are known. Chapter 13 of the “agt book” deals with these issues.
on June 9, 2009 at 2:55 am | Reply Kate Nash-Merry Happy | Fundawn News

[…] Approximate Nash « Algorithmic Game Theory […]
on June 11, 2009 at 8:54 am | Reply Constantinos Daskalakis

Regarding relative approximations for the Nash equilibrium, it should be noted that for two-player games there always exists an exact Nash equilibrium of description complexity polynomial in the size of the game. This follows from the Lemke-Howson algorithm, or even from the simple fact that, once the support of the equilibrium is known, the probabilities can be found with an LP.

Hence, for two-player games the relative notion of approximation does not run into the trouble of exponentially long answers and finding it is a valid algorithmic question.

The two notions of approximation, additive and relative, inherit different invariance properties of the exact Nash equilibrium (with respect to changing the payoffs of the game): the additive approximations are shift invariant and the relative scale invariant. Which of the two invariance properties of an approximate notion of equilibrium is more natural depends on the underlying application…
on June 14, 2009 at 4:33 am | Reply Kate Nash - Pumpkin Soup | Fundawn News

[…] Approximate Nash « Algorithmic Game Theory […]
on June 17, 2009 at 10:34 pm | Reply Kate Nash Birds | Fundawn News

[…] Approximate Nash « Algorithmic Game Theory […]
on September 30, 2009 at 4:33 pm | Reply Communication Complexity of Mixed-Nash Equilibria « Algorithmic Game Theory

[…] the output to be, and the algorithm is allowed to run in time that is polynomial in . (See a previous post on the subtleties of this approximation parameter .) Taking this approach, the lower bound is […]
on December 31, 2009 at 12:16 pm | Reply AGT decade in review « Algorithmic Game Theory

[…] Much work during this decade has gone into determining the computational complexity of various types of equilibria in games and in markets. The class PPAD has been pointed as the complexity of many of these problems, and in particular of the problem of finding a Nash equilibrium. This last result by Daskalakis, Goldberg, and Papadimitriou and Chen and Deng gets the “AGT result of the decade” award. While there are still open problems regarding the complexity of equilibria, especially in markets, it seems to me that — in the limited sense of pinpointing the right complexity class — most of the picture is understood at this point, with the most significant remaining open problem being the computation of approximate Nash equilibria. […]
on May 21, 2013 at 5:34 pm | Reply Ron Peretz

I’m new to NE computation, so please don’t be harsh with me. In the main lemma, is the epsilon^2 inside the log? I guess not. In that case where has a factor of n^2 disappeared?
on June 4, 2016 at 6:22 am | Reply (visit)

Hello, the whole thing is going perfectly here and ofcourse every one is sharing information, that’s really excellent,
keep up writing.
on February 20, 2017 at 11:08 pm | Reply home page

If you would like to obtain a good deal from this article then you have to
apply these strategies to your won blog.