Name
Abstract | ||
|---|---|---|
We study the performance of Fictitious Play (FP), when used as a heuristic for finding an approximate Nash equilibrium of a two-player game. We exhibit a class of two-player games having payoffs in the range \([0,1]\) that show that FP fails to find a solution having an additive approximation guarantee significantly better than \(1/2\). Our construction shows that for \(n\times n\) games, in the worst case both players may perpetually have mixed strategies whose payoffs fall short of the best response by an additive quantity \(1/2 - O(1/n^{1-\delta })\) for arbitrarily small \(\delta \). We also show an essentially matching upper bound of \(1/2 - O(1/n)\). |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1007/s00182-012-0362-6 | International Journal of Game Theory |
Keywords | DocType | Volume |
Fictitious play, Approximate Nash equilibria, Decentralized dynamics | Conference | 42 |
Issue | ISSN | Citations |
4 | 1432-1270 | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Paul W. Goldberg | 1 | 759 | 98.26 |
| Rahul Savani | 2 | 243 | 30.09 |
| Troels Bjerre Sørensen | 3 | 181 | 18.08 |
| Carmine Ventre | 4 | 181 | 24.54 |