Approximate Well-supported Nash Equilibria Below Two-thirds

John Fearnley, Paul W. Goldberg, Rahul Savani, Troels Bjerre Sørensen

Publikation: Artikel i tidsskrift og konference artikel i tidsskriftTidsskriftartikelForskningpeer review

Abstract

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.
OriginalsprogEngelsk
TidsskriftAlgorithmica
Vol/bind76
Udgave nummer2
Sider (fra-til)297-319
Antal sider23
ISSN0178-4617
DOI
StatusUdgivet - 2015

Emneord

  • Bimatrix games
  • Nash equilibria
  • Well-supported approximate equilibria

Fingeraftryk

Dyk ned i forskningsemnerne om 'Approximate Well-supported Nash Equilibria Below Two-thirds'. Sammen danner de et unikt fingeraftryk.

Citationsformater