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