Arbitrarily Slow Polynomial Convergence of Fictitious Play

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 $\mathrm{\Theta }(t^{-1\mathrm{/}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\mathrm{/}2})$ convergence rate, and they extend the recent $\mathrm{\Theta }(t^{-1\mathrm{/}3})$ construction of Wang (2025) to arbitrarily slow polynomial rates.