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 <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$$[0,1]$$</EquationSource> </InlineEquation> that show that FP fails to find a solution having an additive approximation guarantee significantly better than <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$$1/2$$</EquationSource> </InlineEquation>. Our construction shows that for <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$$n\times n$$</EquationSource> </InlineEquation> games, in the worst case both players may perpetually have mixed strategies whose payoffs fall short of the best response by an additive quantity <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$$1/2 - O(1/n^{1-\delta })$$</EquationSource> </InlineEquation> for arbitrarily small <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$$\delta $$</EquationSource> </InlineEquation>. We also show an essentially matching upper bound of <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$$1/2 - O(1/n)$$</EquationSource> </InlineEquation>. Copyright Springer-Verlag Berlin Heidelberg 2013