The Library
On the approximation performance of fictitious play in finite games
Tools
Tools
Tools
Goldberg, Paul W., Savani, Rahul, Sørensen, Troels Bjerre and Ventre, Carmine (2012) On the approximation performance of fictitious play in finite games. International Journal of Game Theory . doi:10.1007/s00182-012-0362-6
Research output not available from this repository, contact author.
Official URL: http://dx.doi.org/10.1007/s00182-012-0362-6
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×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/n1−δ) for arbitrarily small δ . We also show an essentially matching upper bound of 1/2−O(1/n) .
| Item Type: | Journal Article | ||||
|---|---|---|---|---|---|
| Divisions: | Faculty of Science > Computer Science | ||||
| Journal or Publication Title: | International Journal of Game Theory | ||||
| Publisher: | Springer-Verlag | ||||
| ISSN: | 0020-7276 | ||||
| Official Date: | 2012 | ||||
| Dates: |
|
||||
| DOI: | 10.1007/s00182-012-0362-6 | ||||
| Status: | Peer Reviewed | ||||
| Publication Status: | Published | ||||
| Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
