 |
Fakultät für Informatik - Technische Universität MünchenLehrstuhl für Effiziente Algorithmen |
 |
Die bibliographische Datenbank LEABib
Suchen •
Liste der Journale •
Liste der Serien •
Liste der Konferenzen •
Ausgewählte Publikationen 
|
Hilfe 
|
 |
|
| Suche: Author="Savani, Rahul" |
|
On the approximation performance of Fictitious Play We study the performance of Fictitious Play, 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 Fictitious Play 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).in finite games
Paul W. Goldberg, Rahul Savani, Troels Bjerre Srensen, Carmine Ventre
Proceedings of the 19th Annual European Symposium on Algorithms, ESA'2011, (Saarbrücken, Germany, September 5-9, 2011)
Lecture Notes in Computer Science
6942
, 2011, pp. 93-105
| Editors | Camil Demetrescu, Magnús M. Halldórsson | |
| Publisher: | Springer-Verlag | |
| Address: | Berlin-Heidelberg | |
| URL: |
http://dx.doi.org/10.1007/978-3-642-23719-5_9 | |
|
|
|
|