Name
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. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/978-3-642-33996-7_10 | algorithmic game theory |
Keywords | DocType | Volume |
Bimatrix games,Nash equilibria,Well-supported approximate equilibria | Conference | abs/1204.0707 |
Issue | ISSN | Citations |
2 | 0178-4617 | 15 |
PageRank | References | Authors |
0.88 | 11 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| John Fearnley | 1 | 134 | 17.49 |
| Paul W. Goldberg | 2 | 759 | 98.26 |
| Rahul Savani | 3 | 243 | 30.09 |
| Troels Bjerre Sørensen | 4 | 181 | 18.08 |
| SØrensenTroels Bjerre | 5 | 15 | 0.88 |