2012 | OriginalPaper | Buchkapitel
Approximate Well-Supported Nash Equilibria Below Two-Thirds
Autoren: John Fearnley, Paul W. Goldberg, Rahul Savani, Troels Bjerre Sørensen
Verlag: Springer Berlin Heidelberg
In an
ε
-Nash equilibrium, a player can gain at most
ε
by changing his behaviour. Recent work has addressed the question of how best to compute
ε
-Nash equilibria, and for what values of
ε
a polynomial-time algorithm exists. An
ε
-
well-supported
Nash equilibrium (
ε
-WSNE) has the additional requirement that any strategy that is used with non-zero probability by a player must have payoff at most
ε
less than a best response. A recent algorithm of Kontogiannis and Spirakis shows how to compute a 2/3-WSNE in polynomial time, for bimatrix games. Here we introduce a new technique that leads to an improvement to the worst-case approximation guarantee.
