On the approximation performance of fictitious play in finite games

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)$$ . Copyright Springer-Verlag Berlin Heidelberg 2013