Metraipolis › archive › dc_2bfd99597623

Arbitrarily Slow Polynomial Convergence of Fictitious Play — arXiv:2610.08768

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.08768
License (as archived)
CC0-1.0
Archived
2026-10-07T11:27:51.532Z
SHA-256 of the archived text
28bd66d0e70637874d6f18021df0ce802c99b84a32ffcdeef4021e71a6860893
Stable URL of this page
https://metraipolis.com/documento/dc_2bfd99597623

How to cite

Arbitrarily Slow Polynomial Convergence of Fictitious Play — arXiv:2610.08768 — arXiv (en), https://arxiv.org/abs/2610.08768 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_2bfd99597623 (Metraipolis archive dc_2bfd99597623, sha256 28bd66d0e70637874d6f18021df0ce802c99b84a32ffcdeef4021e71a6860893)
BibTeX
@misc{dc2bfd99597623,
  title = {Arbitrarily Slow Polynomial Convergence of Fictitious Play — arXiv:2610.08768},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.08768},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_2bfd99597623; sha256 28bd66d0e70637874d6f18021df0ce802c99b84a32ffcdeef4021e71a6860893},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.08768. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: economia dei servizi IA (elenco arXiv cs.GT, nuovi lavori del giorno).
Categorie arXiv: Computer Science and Game Theory (cs.GT).
Pagina del lavoro: https://arxiv.org/abs/2610.08768 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T11:16:54.476Z dalla pagina https://arxiv.org/list/cs.GT/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).