# Nash Equilibrium for Sparse Games: Part Deux

* 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 -Nash equilibrium of a -sparse game—the expected payoff from any row is at most 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 and want to find an so that

of course, we call a root. Usually is not a rational number, so we cannot write it down exactly. Thus, what we do is try to find a so that

where is the required precision and are integers.

There is a fundamental problem: simply because is small does that mean that it is near an actual root of ? It does not, in general. What we want are the stronger statements:

- The value of is near ;
- There is a so that and is also small.

In this case we can say that is an *approximate root* of the polynomial. If there is no such , then 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:

*exact*NE.

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 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 is an matrix with entries in , such that each row and column in has at most ‘s. Then, for the symmetric game defined by , we can find an -NE in time bounded by

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 . The number of such strategies for either player is at most

This follows since the number of strategies are bounded by the number of ways to place objects into “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 -near NE. Consider an exact NE say . Notice that there exist strategies such that the following are satisfied:

- For all : and .
- For all : if then , and if then .

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

which will make it a probability vector. The same method works for . Now we need to prove that this strategy pair is an -near NE. The payoff for the row player is and for the column player is . Let denote a unit vector with at -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 and the NE satisfy:

- , for all .
- , for all .

The first claim follows from the fact that

The second claim is analogous. This is where we use that has at most ‘s in each row/column. Therefore, the total error from the NE is at most

It follows from the above that is an -near NE of the game.

The above proof shows the *existence* of an -near NE in the search space formed by the strategies that are multiples of . This strategy pair is near the exact NE . However, because of the difficulty of searching for an -near NE, an exhaustive search in this space can only guarantee that we would find an -NE, and not an -near NE.

** Open Problems **

An interesting open problem is to try to found an -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 1′s in all, the problem of finding a PTAS is still, I believe, open.

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).

That sounds right…

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.

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.

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.

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.

Thanks for this link. I just read the story and find it a wonderful example of conventional wisdom being wrong. What is even better is that there is now hope for millions who suffer from MS.

Thanks again.

I like your initial example using roots of polynomials. Interestingly, if you have access to the coefficients of a real polynomial, you can in fact distinguish (real) points that make the absolute value of the function very small but are not near zeroes from points that are actually near zeroes, using “Sturm’s algorithm.” See here and also here, which is where I originally found this gem (or rather, I found it in a physical copy of Cutland).