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