pipette
ENEnglish

Arbitrarily Slow Polynomial Convergence of Fictitious Play

Jacob Abernethy, John Lazarsfeld, Andre Wibisono

Preprint

En palabras de los autores

We show that fictitious play can converge at arbitrarily slow polynomial rates in two-player zero-sum games. For every integer , we construct a payoff matrix with actions per player for which the duality gap of the empirical strategies decays as after 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 , these games give counterexamples to Karlin's conjectured convergence rate, and they extend the recent construction of Wang (2025) to arbitrarily slow polynomial rates.

Resultado principalEl resumen no menciona limitaciones.

Apareció: miércoles, 7 de octubre. arXiv. Preprint, todavía sin revisión por pares.