On the Approximation Performance of Fictitious Play in Finite Games

Paul W. Goldberg, Rahul Savani, Troels Bjerre Sørensen, Carmine Ventre

Abstract

We study the performance of Fictitious Play, when used as a heuristic for finding an approximate Nash equilibrium of a 2-player game. We exhibit a class of 2-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).
BibTeX
@article{goldberg2013approximation,
  author = {Paul W. Goldberg and Rahul Savani and Troels Bjerre Sørensen and Carmine Ventre},
  title = {{On the Approximation Performance of Fictitious Play in Finite Games}},
  journal = {Int. J. Game Theory},
  year = {2013},
  url = {https://openreview.net/forum?id=SOovsOrUYM5},
}

Loading related content...

Figure