OpenAlex ·
Arbitrarily Slow Polynomial Convergence of Fictitious Play
- Published
- Source
- OpenAlex
- Published in
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2610.08768
- Original
- Read it at the publisher
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Econometrics
Personalized Recommendations Without Inducing Congestion: Mitigating Disparities in the NYC High School Match
Validity Without Ground Truth: What Stated-Preference Economics Offers the Evaluation of Language Models
On the Complexity of Mixed Equilibria in First-Price Auctions with Correlated Priors
A Constant-Factor Approximation to Multidimensional Consumer Utility
Risk Ceilings and Development Deadlines: Pacing AI under Uncertain Safety Productivity
Get the few papers worth your time in Econometrics every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.