Wednesday, April 08, 2009

Localising Nash equilibria

In an epsilon-Nash equilibrium, the players choose distributions over their actions in such as way that no player can gain more than epsilon (in expected utility) by switching to some alternative strategy. But in general, there is no guarantee that an epsilon-Nash equilibrium is anywhere near a true Nash equilibrium. ("near" can be defined by using the variation distance between two probability distributions.)

After my talk at BCTCS (on algorithms for computing approximate Nash equilibria) Arno Pauly asked me the following interesting question. How hard is it to find an epsilon-Nash equilibrium that is guaranteed to be within epsilon of a true Nash equilibrium? (My immediate answer: don't know.)

Focus on the 2-player case. The problem is in TFNP, because a non-deterministic Turing machine can find a genuine Nash equilibrium, which of course qualifies. But there's an interesting twist here, which is that a solution to the problem cannot, on its own, in any obvious way, be checked in deterministic polynomial time. This is in contrast to most search problems. A solution does not seem to constitute its own certificate. By contrast, an unrestricted epsilon-Nash equilibrium is its own certificate.

I guess that any NP search problem (not just total ones) have related ones where a solution cannot be checked in deterministic poly-time. e.g. SAT: suppose you ask for an assignment to the propositional variables that is Hamming distance at most n/4 from a satisfying assignment. It's still in NP but you can't (seemingly) deterministically check a solution. The problem of finding an approximation to a genuine Nash equilibrium looks more natural, of course.

So, is this problem any harder than finding an unrestricted epsilon-Nash equilibrium? As explained in the talk, little is known about the complexity of finding epsilon-Nash equilibria, although the fact that they can be found in subexponential time for any epsilon>0 suggests that maybe the answer is that the problem should be in P.

On the other hand, finding epsilon-approximations to true Nash equilibria feels like it ought to be tougher. One possibility that I would be tempted to look for: any such algorithm can be modified to find genuine Nash equilibria. A possible analogy is with boosting in computational learning theory, where in Schapire's classical paper, a PAC algorithm that guarantees to end up doing slightly better than random guessing, can have its performance boosted (by running it repeatedly on variously filtered data) to end up with standard PAC learning.

3 comments:

Alex F said...

Is the distinction from the Etessami&Yannakakis work on the class they called "FIXP" that you're asking for a point that is _both_ an eps-NE _and_ eps-close to a true NE?

par...alogos said...

I think Mihalis Giannakakis answers to this question with this paper:
"On the Complexity of Nash Equilibria and Other Fixed Points":
link
[FOCS 2007]


Full version here:
link

Paul Goldberg said...

Thanks for those comments, and apologies for not writing sooner; I have been on holiday for the last week. That paper (I should now read it more carefully) answers (negatively) at least one version of my question. Not sure if it does the 2-player case though.

A "weaker" version of the question is to ask: in (say) 3-player games, whether you can find a 2/3-Nash equilibrium that is within variation distance 1/2 of a 1/2-Nash equilibrium. (Maybe that question's getting too artificial?) That version of the question gets away from the algebraic obstacle of genuine Nash equilibria when there are >2 players. (Note that it's easy to find 2/3-Nash equilibria in the 3-player case if you don't care about being within some distance of a better approximation.)