Arbitrarily Slow Polynomial Convergence of Fictitious Play
Jacob Abernethy John Lazarsfeld Andre Wibisono
作者信息
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 $Î(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 $Î(t^{-1/3})$ construction of Wang (2025) to arbitrarily slow polynomial rates.引用本文复制引用
Jacob Abernethy,John Lazarsfeld,Andre Wibisono.Arbitrarily Slow Polynomial Convergence of Fictitious Play[EB/OL].(2026-10-06)[2026-10-08].https://arxiv.org/abs/2610.08768.学科分类
数学
|国家预印本平台