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.

References

Constantinos Daskalakis and Qinxuan Pan, A Counter-Example to Karlin's Strong Conjecture for Fictitious Play, FOCS 2014; arXiv:1412.4840. https://arxiv.org/abs/1412.4840. Yuanhao Wang, Tie-breaking Agnostic Lower Bound for Fictitious Play, arXiv:2507.09902 (2025), Theorem 1 and the augmented-game construction. https://arxiv.org/pdf/2507.09902. These sources supply the historical counterexamples. The count audit, finite-horizon stability proof, and profile bounds above state the additional checks completed in this attempt.