How to find approximate Nash equilibrium for sparse games

Constantinos Daskalakis is one of the experts in modern game theory, especially the structure of Nash Equilibrium for non-zero sum games. He has written a wonderful paper with Christos Papadimitriou On oblivious PTAS’s for nash equilibrium. Also see his nice survey for more information.

Today I want to talk about Costis and Christos’ paper as it relates to sparse games. This is another example of the Iceberg Effect: their paper has a beautiful result on game theory, but I missed another of their results.

Constantinos, Costis, was kind enough to point out two things about sparse games after my earlier discussion on games. First, that in his paper with Christos at STOC 2009, they stated a theorem that solves the sparse case of symmetric games. He went on to sketch the proof, which they did not include in their paper: I will give their proof in a moment.

Second, he points out that Shanghua Teng has observed that the uniform distribution is trivially a ${(k/n)}$-Nash equilibrium of a ${k}$-sparse game—the expected payoff from any row is at most ${k/n}$ for the row player and similarly for the column player.

His second point is one that I would like to discuss, since it raises an issue by what we mean to approximate a Nash Equilibrium (NE).

Let’s turn to discuss first NE and then their theorem.

Nash Equilibrium: Exact and Approximate

What does it mean to find an approximate NE? I think it will be easier to first explain the main issue involved by an analogy. Anyway I love analogies.

Suppose that you have a polynomial ${f(x)}$ and want to find an ${r}$ so that

$\displaystyle f(r) = 0,$

of course, we call ${r}$ a root. Usually ${r}$ is not a rational number, so we cannot write it down exactly. Thus, what we do is try to find a ${p/q}$ so that

$\displaystyle |f(p/q)| \le \epsilon$

where ${\epsilon>0}$ is the required precision and ${p,q}$ are integers.

There is a fundamental problem: simply because ${f(p/q)}$ is small does that mean that it is near an actual root of ${f(x)}$? It does not, in general. What we want are the stronger statements:

1. The value of ${f(p/q)}$ is near ${0}$;
2. There is a ${b}$ so that ${f(b)=0}$ and ${|b-p/q|}$ is also small.

In this case we can say that ${p/q}$ is an approximate root of the polynomial. If there is no such ${b}$, then ${p/q}$ is an interesting point, but it is not correct to call it an approximate zero.

This behavior is analogous to what happens with “approximate NE’s.” There are two types of interpretations of what an approximate NE is:

• An ${\epsilon}$-near NE: This is a pair of strategies that are within an ${\epsilon}$ of an exact NE.
• An ${\epsilon}$-NE: This is a pair of strategies such that a player who defects from their strategy can gain at most an ${\epsilon}$.

Costis, in his survey, points out that the first notion is reasonable, but the latter is the one that we usually use: Note also that it is easy for a player to check the approximate optimality of the actions used by her mixed strategy. So the notion of an approximate Nash equilibrium is much more appealing ${\dots}$ and, in fact, this is the notion most commonly used.

Note, the analogy to the root problem: in the first we are near a root, and in the second we are at a small value. As Costis points out the latter can be checked easily, while checking that a point is near an exact root is not as easy.

Sparse Games

I will now state their theorem:

Theorem: Suppose that ${A}$ is an ${n \times n}$ matrix with entries in ${\{0,1\}}$, such that each row and column in ${A}$ has at most ${k}$ ${1}$‘s. Then, for the symmetric game defined by ${A}$, we can find an ${\epsilon}$-NE in time bounded by

$\displaystyle n^{2k/\epsilon + O(1)}.$

Here is a sketch of their proof:

Proof:

The key insight is that it is enough to consider strategies for the row and column player where the probabilities are integer multiples of ${\delta = \epsilon/2k}$. The number of such strategies for either player is at most

$\displaystyle n^{1/\delta}.$

This follows since the number of strategies are bounded by the number of ways to place ${1/\delta}$ objects into ${n}$ “bins.”

We now have a “small” set of strategies, the following argument will show that one of these strategies contains a pair that is an ${\epsilon}$-near NE. Consider an exact NE say ${(x,y)}$. Notice that there exist strategies ${(x',y')}$ such that the following are satisfied:

1. For all ${i}$: ${| x'_{i} - x_{i} | \le \delta}$ and ${| y'_{i} - y_{i} | \le \delta}$.
2. For all ${i}$: if ${x_{i} =0}$ then ${x'_{i} =0}$, and if ${y_{i}=0}$ then ${y'_{i}=0}$.

Consider ${x'}$. If ${x_{i}=0}$, then set ${x'_{i}}$ to ${0}$. Otherwise, set ${x'_{i}}$ to the nearest multiple of ${\delta}$. This almost works: the small issue is that if ${x_{i}}$ is not a exact multiple of ${\delta}$, then do we round up or down? Either rule will make ${x'}$ satisfy the needed conditions above. However, we also need ${x'}$ to be a probability vector: it is easy to see that by rounding some up or down we can adjust ${x'}$ to satisfy

$\displaystyle \sum_{i}x'_{i} = 1$

which will make it a probability vector. The same method works for ${y'}$. Now we need to prove that this strategy pair is an ${\epsilon}$-near NE. The payoff for the row player is ${x'Ay'}$ and for the column player is ${x'A^{T}y'}$. Let ${e_i}$ denote a unit vector with ${1}$ at ${i}$-th coordinate. For notational convenience, we omit the transform symbols on the vectors. The usage should be clear from the context.

Notice that the pair of strategies ${x', y'}$ and the NE ${x,y}$ satisfy:

1. ${| e_i A y' - e_i A y| \le \epsilon/2}$, for all ${i}$.
2. ${| x' A^{T} e_j - x A^{T} e_j| \le \epsilon/2}$, for all ${j}$.

The first claim follows from the fact that

$\displaystyle \sum_{j=1}^{n}{|(A y')_j - (A y)_j|} \le k\delta = k\cdot (\epsilon/2k) = \epsilon/2.$

The second claim is analogous. This is where we use that ${A}$ has at most ${k}$ ${1}$‘s in each row/column. Therefore, the total error from the NE ${(x,y)}$ is at most ${\epsilon/2 + \epsilon/2 = \epsilon}$

It follows from the above that ${(x', y')}$ is an ${\epsilon}$-near NE of the game. $\Box$

The above proof shows the existence of an ${\epsilon}$-near NE ${(x',y')}$ in the search space formed by the strategies that are multiples of ${\delta}$. This strategy pair is near the exact NE ${(x,y)}$. However, because of the difficulty of searching for an ${\epsilon}$-near NE, an exhaustive search in this space can only guarantee that we would find an ${\epsilon}$-NE, and not an ${\epsilon}$-near NE.

Open Problems

An interesting open problem is to try to found an ${\epsilon}$-near NE. The above proof shows that it is in a relatively “small” list of strategies. Is it possible to discriminate and determine which are near exact NE’s?

The above proof gives us a PTAS for games with a bounded number of 1′s in each row and column. However, for matrices with ${O(n)}$ 1′s in all, the problem of finding a PTAS is still, I believe, open.

1. November 17, 2009 5:02 pm

OK, regarding your open problems I think I can say something relevant for the 3-player case… For 3 players (or any constant number) a similar result to the above still seems to hold (making a similar sparsity assumption for the 3-dimensional arrays of payoffs for the players). But, for general payoff matrices, Etessami and Yannakakis show that the problem of localizing an exact NE is at least as hard as the square-root sum problem (as I was told in a comment here).

November 18, 2009 8:50 am

That sounds right…

2. November 18, 2009 6:24 pm

This looks like a nice topic, but I am a little bit confused, possibly about the definitions. At the end of your proof, it’s clear that the payoffs for each player in (x’, y’) is within epsilon of their payoff in (x, y). But isn’t the definition of eps-near NE that we want x to be close to x’, and y close to y’? I also wasn’t sure where symmetry came into play.

• November 19, 2009 5:35 am

That looks correct, the proof does not apply to ε-near equilibria, indeed if the only NE is the uniform distribution over the players’ actions, then the rounded version to multiples of δ is doomed to be far away from the uniform distribution. I think that very little is known about how to find ε-near NEs.

Regarding symmetry, symmetric 2-player games are computationally equivalent to general ones, so we might as well assume the game is symmetric.

November 19, 2009 4:54 pm

I think the point is that we can choose the \delta small enough to make (x’,y’) arbitrarily close to (x,y). Agree with Dave that it is a bit confusing. The proof shows that (x’,y’) is no more than \epsilon worse off in pay off. But (x’,y’) is also arbitrarily close to (x,y), by choice.

3. November 22, 2009 4:02 am

Completely off-topic, but it sounds like there’s huge news related to challenging the conventional wisdom about multiple sclerosis: http://www.ctv.ca/servlet/ArticleNews/story/CTVNews/20091120/W5_liberation_091121/20091121?s_name=W5

It needs more research of course, but if nothing else, it lends credibility to the idea of challenging the conventional wisdom in a scientific field when it’s fallen short for so long.