2006 | OriginalPaper | Buchkapitel
A Note on Approximate Nash Equilibria
Autoren: Constantinos Daskalakis, Aranyak Mehta, Christos Papadimitriou
Verlag: Springer Berlin Heidelberg
In view of the intractability of finding a Nash equilibrium, it is important to understand the limits of approximation in this context. A subexponential approximation scheme is known [LMM03], and no approximation better than
$1\over 4$
is possible by any algorithm that examines equilibria involving fewer than log
n
strategies [Alt94]. We give a simple, linear-time algorithm examining just two strategies per player and resulting in a
$1\over 2$
-approximate Nash equilibrium in any 2-player game. For the more demanding notion of
well-supported approximate equilibrium
due to [DGP06] no nontrivial bound is known; we show that the problem can be reduced to the case of win-lose games (games with all utilities 0–1), and that an approximation of
$5\over 6$
is possible contingent upon a graph-theoretic conjecture.
