On the Approximation Performance of Fictitious Play in Finite Games

摘要

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 × 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-δ))) for arbitrarily small δ. We also show an essentially matching upper bound of 1/2 - O(1).