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.
Originalsprog | Engelsk |
---|---|
Tidsskrift | Algorithmica |
Vol/bind | 76 |
Udgave nummer | 2 |
Sider (fra-til) | 297-319 |
Antal sider | 23 |
ISSN | 0178-4617 |
DOI | |
Status | Udgivet - 2015 |
Emneord
- Bimatrix games
- Nash equilibria
- Well-supported approximate equilibria