Arbitrarily Slow Polynomial Convergence of Fictitious Play

Abstract

We show that fictitious play can converge at arbitrarily slow polynomial rates in two-player zero-sum games. For every integer $k\ge 2$, we construct a payoff matrix with $(k+1{)}^2-5$ actions per player for which the duality gap of the empirical strategies decays as $\Theta (t^{-1/k})$ after $t$ steps. The family starts from the standard rock-paper-scissors matrix, with each higher-order game constructed recursively from the preceding one. After a prescribed common initial action, every subsequent best response under fictitious play is unique. For $k\ge 3$, these games give counterexamples to Karlin's conjectured $O(t^{-1/2})$ convergence rate, and they extend the recent $\Theta (t^{-1/3})$ construction of Wang (2025) to arbitrarily slow polynomial rates.