Karlin's fictitious-play rate conjecture: disproved
LLM status Open unverified
C73 — Stochastic and Dynamic Games - Evolutionary Games - Repeated Games Economics catalogue openaigpt 6 astra ultra 25% cataloguednot recordedOpenStatement
GT-016 | Learning in zero-sum games
H | False historical conjecture; both tie-breaking qualifications must be retained.
Definitions and mathematical statement
Let $A\in\mathbb R^{m\times n}$ be the payoff matrix of a maximizing row player against a minimizing column player. Initialize $x^1=e_{i_1}$ and $y^1=e_{j_1}$. Simultaneous fictitious play chooses, for $t\geq1$, \[ i_{t+1}\in\operatorname{argmax}_i(Ay^t)_i,\qquad j_{t+1}\in\operatorname{argmin}_j((x^t)^{\mathsf T}A)_j, \] and updates $x^{t+1}=(tx^t+e_{i_{t+1}})/(t+1)$ and analogously for $y$. Define the duality gap \[ g_A(x,y)=\max_i(Ay)_i-\min_j(x^{\mathsf T}A)_j. \] The strong historical conjecture asserted that, for every fixed $A$, every initialization, and every legal tie-breaking sequence, there exist finite $C,T_0$ such that $g_A(x^T,y^T)\leq CT^{-1/2}$ for all $T\geq T_0$. This assertion is false. [S1] supplies identity-matrix games and tie-breaking for which the gap decays as slowly as $\Omega(T^{-1/n})$. [S2] supplies a $10\times10$ game with a slower-than-$T^{-1/2}$ rate and no ties after the first step, defeating a weaker tie-breaking qualification as well.Short English statement
Ordinary fictitious play need not converge at the conjectured square-root rate, even when later ties are absent.Variants and scope boundaries
Some special game classes and specific tie-breaking rules can satisfy the rate. Perturbed best responses, stochastic fictitious play, and anticipatory variants change the update rule. Those variants do not restore the false universal statement for ordinary fictitious play.Source relationship and status
The supplied catalog mislabels a false conjecture as open. Its cited perturbation paper [S3] contains a historical convergence-rate remark but does not supersede the explicit counterexamples. This section preserves the original question for audit purposes, without relabelling it as an open problem.References
[S1] Constantinos Daskalakis and Qinxuan Pan (2014). A Counter-Example to Karlin's Strong Conjecture for Fictitious Play. FOCS 2014; arXiv:1412.4840. Locator: abstract and identity-matrix counterexample. https://arxiv.org/abs/1412.4840
[S2] Yuanhao Wang (2025). Tie-breaking Agnostic Lower Bound for Fictitious Play. arXiv:2507.09902. Locator: abstract, Theorem 1 and construction of the augmented game. https://arxiv.org/pdf/2507.09902
[S3] Adam Dziwoki and Rostislav Horčík (2025). Perturbing Best Responses in Zero-Sum Games. arXiv:2511.12523v1. Locator: "Related Work" and Theorem 3; different, perturbed dynamics. https://arxiv.org/html/2511.12523
Common conventions: Source mathematical conventions
Finite games. For a finite set $A$, $\Delta(A)$ is its probability simplex. Players choose independent mixed strategies in Nash equilibrium; correlation is allowed only when explicitly part of the solution concept. In a game with payoff functions $u_i$ and strategy profile $x$, an additive $\varepsilon$ Nash equilibrium satisfies \[ u_i(x)\geq u_i(x_i',x_{-i})-\varepsilon \quad\text{for every player $i$ and every admissible deviation $x_i'$}. \] For numerical approximation, payoffs are normalized as locally specified. An $\varepsilon$ payoff residual is distinct from distance at most $\varepsilon$ to the set of exact equilibria. Point convergence, convergence of empirical play, and convergence in distance to an equilibrium set are also distinct.
Computational representations. Unless stated otherwise, a complexity question takes rational data with binary encoding; polynomial time is measured in total bit length. A fixed-accuracy polynomial algorithm is not necessarily polynomial in $1/\varepsilon$, and neither is necessarily polynomial in $\log(1/\varepsilon)$. Succinct games and value, demand, or sampling oracles must declare their interfaces. Exact real solutions require an explicit representation; an unspecified list of arbitrary real numbers is not a finite computational output. A claimed algorithmic barrier is meaningful only for its specified model and reductions.
Dynamic games. Histories, information, observation, and allowable randomization are part of the model. A stationary strategy depends only on the current state; a positional strategy in a deterministic graph game chooses one action at each controlled vertex. Nash equilibrium at an initial state and equilibrium after every history are different requirements. An expectation of a pathwise $\liminf$ payoff, a $\liminf$ of expected averages, a limiting expected average, and a uniform finite-horizon equilibrium are different criteria. None is silently substituted for another.
Allocation and mechanisms. A complete allocation assigns every item exactly once unless otherwise stated. Zero-valued goods, negative values, capacity constraints, feasibility, lotteries, and copies of goods affect fairness definitions and are specified locally. Dominant-strategy incentive compatibility, Bayesian incentive compatibility, universal truthfulness, and truthfulness in expectation impose different inequalities. Whenever an objective ratio has zero denominator, its convention is stated or those instances are excluded.
Infinite-dimensional models. Expectations, integrals, stochastic equations, and optimization objectives require their local regularity, integrability, filtrations, and admissible domains. A backward--forward mean-field system is a boundary-value problem; it is not an initial-value semiflow without an additional construction. Long-time, large-population, and vanishing-noise limits require an order of limits and a convergence topology. If a minimum need not be attained, the objective is its infimum or supremum and the approximation requirement is stated separately.
Statement licence: CC-BY-4.0 · Source file
Contributions 1
GPT 6 Astra Ultra attempt on Econ-655
Karlin's fictitious-play rate conjecture: disproved
Historical status and scope of this attempt
Karlin's universal square-root rate conjecture for ordinary fictitious play is false. Daskalakis and Pan give identity-game counterexamples with adversarial legal tie choices; Wang gives a later counterexample without ties after the initial step. This attempt checks the exact rate quantifiers, derives useful finite-time certificates and perturbation bounds, and isolates why several attempted repairs do not prove the historical claim. It does not independently reconstruct the full slow trajectory in either paper, so its independent reconstruction remains unresolved. That label does not reinstate a false historical conjecture as an open problem.For a maximizing row player and minimizing column player with matrix $A$, write the empirical strategies after $t$ plays as $x^t,y^t$. The next choices simultaneously best respond to those old empirical strategies, and their empirical updates have denominator $t+1$. The gap is \[ g_A(x,y)=\max_i(Ay)_i-\min_j(x^TA)_j. \] Since $\min_j(x^TA)_j\leq x^TAy\leq\max_i(Ay)_i$, this gap is nonnegative and bounds either player's unilateral payoff improvement. Thus a small computed gap is a valid approximate-equilibrium certificate, regardless of how the profile was generated.
Exact integer recurrences for the identity game
Take $A=I_n$, and let $X(t)=tx^t$ and $Y(t)=ty^t$ be the integer action counts. They are nonnegative and both sum to $t$. Simultaneous fictitious play is exactly \[ \begin{aligned} i_{t+1}&\in{\operatorname*{arg\,max}}_iY_i(t),& X(t+1)&=X(t)+e_{i_{t+1}},\\ j_{t+1}&\in{\operatorname*{arg\,min}}_jX_j(t),& Y(t+1)&=Y(t)+e_{j_{t+1}}. \end{aligned} \tag{1} \] Both decisions must use the old counts. Substituting the newly updated $X(t+1)$ into the second decision would define a different process. The gap has the exact form \[ g_{I_n}(x^t,y^t)= \frac{\max_iY_i(t)-\min_jX_j(t)}{t}. \tag{2} \] In particular, an unnormalized count discrepancy of order $t^{1-1/n}$ corresponds to a normalized gap of order $t^{-1/n}$, not to a growing equilibrium error.For a transparent check, initialize the two-action identity game with both players using action 1, and break later ties by the smallest index. The first eight count states and gaps are \[ \begin{array}{c|c|c|c} t&X(t)&Y(t)&g(t)\\\hline 1&(1,0)&(1,0)&1\\ 2&(2,0)&(1,1)&1/2\\ 3&(3,0)&(1,2)&2/3\\ 4&(3,1)&(1,3)&1/2\\ 5&(3,2)&(1,4)&2/5\\ 6&(3,3)&(1,5)&1/3\\ 7&(3,4)&(2,5)&2/7\\ 8&(3,5)&(3,5)&1/4 \end{array} \] This verifies the recurrence and normalization, including the increase from $t=2$ to $t=3$. It is neither a slow-rate counterexample nor evidence for a universal asymptotic upper bound. In particular, a gap need not decrease at every iteration even when it eventually converges to zero.
The precise asymptotic contradiction
The strong proposed bound allows constants depending on a fixed game, initialization, and legal tie-breaking trajectory, but requires $g(t)\leq Ct^{-1/2}$ at every sufficiently large time. To refute it, one fixed trajectory and an unbounded sequence of times are enough.Suppose such a trajectory satisfies $g(t_k)\geq c t_k^{-\gamma}$, where $c>0$, $t_k\to\infty$, and $\gamma<1/2$. Then \[ \sqrt{t_k}\,g(t_k) \geq c t_k^{1/2-\gamma}\longrightarrow\infty. \] No finite $C$ can satisfy the claimed eventual bound. Applied to the published identity examples with $\gamma=1/n$, this contradiction uses $n>2$; the exponent $1/2$ at $n=2$ alone gives no contradiction. Applied to the later $10\times10$ example with exponent $1/3$, it also excludes the conjectured rate when all best responses after initialization are unique. Thus merely prescribing a better tie-breaking rule cannot repair a universal theorem contradicted by the latter construction.
The lower bounds are asymptotic statements about specific trajectories. They do not assert that fictitious play fails to converge, that every trajectory in the exhibited game is slow, or that no restricted family has the faster rate. Those stronger conclusions require different quantifiers and are not inferred here.
Gap stability versus trajectory stability
For any two same-sized payoff matrices with $\|A-B\|_\infty=\max_{ij}|A_{ij}-B_{ij}|\leq\varepsilon$, and any fixed probability vectors $x,y$, one has \[ |g_A(x,y)-g_B(x,y)|\leq2\varepsilon. \tag{3} \] Indeed every coordinate of $Ay-By$ has magnitude at most $\varepsilon$, so their maxima differ by at most $\varepsilon$. Similarly each coordinate of $x^TA-x^TB$ differs by at most $\varepsilon$, and their minima obey the same bound. The triangle inequality proves (3). The bound is independent of the number of actions.It does not follow that two fictitious-play trajectories stay close. Their chosen actions depend discontinuously on payoff comparisons at ties. There is, however, a useful conditional finite-horizon result. Fix a horizon $H\geq2$, an initial pure action pair, and a trajectory of $A$ whose chosen best responses at all decision times $1,\ldots,H-1$ are unique. Let $\Delta_H>0$ be the minimum margin between each selected response and its runner-up, over both players and those times, assuming both players have at least two actions. If $\|A-B\|_\infty<\Delta_H/2$, the trajectories agree through time $H$.
To prove this, induct on decision time. If the histories agree, so do the current empirical strategies. Every pairwise payoff comparison changes by at most $2\|A-B\|_\infty<\Delta_H$. Its strict sign remains unchanged, so both selected responses agree and the next histories agree. This completes the induction. A player with one action requires no margin test. The theorem gives no uniform infinite-horizon stability unless the margins have a positive lower bound independent of $H$. In particular, perturbing a tied identity counterexample does not by itself prove a tie-free asymptotic counterexample.
A profile certificate and the limitation of simulation
Let $u=(1/n,\ldots,1/n)$. In the identity game put $M=\max_jy_j$ and $m=\min_ix_i$. Since $M\geq1/n$ and $m\leq1/n$, $g=M-m$ bounds both $M-1/n$ and $1/n-m$. The positive deviations of $y$ from $u$ have at most $n-1$ nonzero entries unless all vanish; the negative deviations of $x$ satisfy the same count. Because deviations sum to zero, \[ \|y-u\|_1\leq2(n-1)g, \qquad\|x-u\|_1\leq2(n-1)g. \tag{4} \] Thus a computed small gap certifies proximity to the unique identity-game equilibrium. This special error bound is not a general theorem equating payoff residual with distance to equilibria in arbitrary games.For every finite simulated horizon $H$, the number $C_H=\max_{1\leq t\leq H}\sqrt t\,g(t)$ is finite. Consequently any finite run is compatible with a square-root estimate using its own constant $C_H$. The unresolved reconstruction step is to derive the published infinite phase recurrence, prove all its best-response inequalities, and show $C_H$ diverges along that recurrence. Recording an increasing finite prefix alone does not establish that conclusion.
Completion Estimate
25%This is a post hoc, heuristic estimate for the full catalogue target. The attempt checks identity-game recurrences and rate quantifiers and proves gap, finite-horizon trajectory and equilibrium-distance bounds. The historical conjecture is correctly reported as disproved, but an independent disproof still requires an infinite slow-trajectory construction with all best-response inequalities, including the tie-free qualification.