2006 | OriginalPaper | Buchkapitel
A Note on Approximate Nash Equilibria
verfasst von : Constantinos Daskalakis, Aranyak Mehta, Christos Papadimitriou
Erschienen in: Internet and Network Economics
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.