Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
Approximate Well-Supported Nash Equilibria Below Two-Thirds
verfasst von : John Fearnley, Paul W. Goldberg, Rahul Savani, Troels Bjerre Sørensen
Erschienen in: Algorithmic Game Theory
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 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.