Pith. sign in

REVIEW 3 major objections 4 minor 13 references

Tie-breaking Agnostic Lower Bound for Fictitious Play

T0 review · 3 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A 10-by-10 zero-sum game makes fictitious play converge no faster than $\Omega(t^{-1/3})$, refuting Karlin's conjecture in its weak form.

desk verdict Clever construction and the right high-level idea, but Lemma 2's growth bound is false and condition (13) is violated, so the weak-Karlin claim is unproved as written. read the letter →

arxiv 2507.09902 v1 pith:EZ5LOMBI submitted 2025-07-14 cs.GT

Yuanhao Wang This is my paper
classification cs.GT MSC 91A0591A26
keywords fictitiousplayKarlin'sconjecturezero-sumgamesconvergenceratelowerboundtie-breakingagnosticrock-paper-scissorsgameNashequilibriumsymmetric
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper answers a long-open question in game theory: does fictitious play, the natural 'best response to history' learning rule, always approach a Nash equilibrium at the $O(t^{-1/2})$ rate Karlin conjectured in 1959, even when ties are not allowed to help? The answer is no. The paper constructs a 10-by-10 zero-sum matrix game, built from three coupled copies of rock-paper-scissors, in which fictitious play's duality gap is $\Omega(t^{-1/3})$ at infinitely many times, regardless of how ties are broken. After the first step there are no ties at all, so the slowdown is intrinsic to the game rather than an artifact of adversarial tie-breaking. If correct, this closes the weaker form of Karlin's conjecture and shows that discrete fictitious play can be polynomially slower than its continuous-time counterpart.

What carries the argument

Three coupled rock-paper-scissors (RPS) blocks plus a symmetric interaction matrix $B$; the paper solves a matrix equation (Eq. 12) derived from requiring the utility vector at phase boundaries to follow exact quadratic trajectories $V_i \vec{k}$. The admissible matrices $Q_0,Q_1$ come from RPS's exact periodic behavior (Fact 2), and $B$ is chosen so that, during a block, the maximum of the inactive second block grows faster than the active block's maximum decreases, enforcing the phase switch at exactly $T_{k+1}$. Because the game is symmetric, the duality gap is $2\max\{U_t\}$, so tracking one coordinate's maximum suffices to read off the convergence rate.

What would settle it

Simulate FP directly on the printed $M_{\rm aug}$ from Appendix A for $t$ up to at least $T_4$ and check that the maximizing block cycles exactly as predicted and that the duality gap at $t=T_{3k+1}$ scales as $\Theta(t^{-1/3})$; any switch of the maximum to a different block before the predicted boundary refutes the phase structure.

Watch

Extended reading notes

Core claim

The paper's central object is a symmetric zero-sum game $M$ whose payoff matrix has three rock-paper-scissors blocks on the diagonal, coupled through a $3\times3$ interaction matrix $B$ chosen so that fictitious play follows a double loop. At the start of the $k$-th outer loop, all three blocks' utility vectors are quadratic polynomials in $k$; during the phase, one block is played for $\Theta(k^2)$ steps exactly as unperturbed rock-paper-scissors would be, while the other blocks' maxima drift. The interaction is tuned so the next block catches up at exactly the right moment, cycling block 1 to block 2 to block 3 and back to block 1. At times $T_{3k+1}=\Theta(k^3)$ the maximum utility is $\Theta(k^2)=\Theta(t^{2/3})$, hence the duality gap is $\Theta(t^{-1/3})$. An added dummy action makes the game $10\times10$ and guarantees that after the first step no tie ever occurs, giving a tie-breaking-agnostic counterexample.

Load-bearing premise

The argument depends on a numerical growth bound: during each phase the largest utility in the second block must increase by at least $1/12$ per step, and the gap between first- and third-block maxima must stay smaller than the negative of the largest entry of $B$; if either fails, the phase timer that produces the $\Omega(t^{-1/3})$ trajectory is not guaranteed.

Editorial extensions

If this is right

  • Karlin's conjecture in its weaker form is false: fictitious play can be as slow as $\Omega(t^{-1/3})$ even when no ties occur after the first step.
  • The lower bound holds for every tie-breaking rule, so no tie-resolution heuristic can guarantee $O(t^{-1/2})$ for general zero-sum games.
  • Discrete and continuous fictitious play are genuinely different: continuous-time FP has an $O(1/t)$ rate, while discrete FP can be polynomially slower.
  • Any future positive rate result for fictitious play must either restrict the payoff structure (as diagonal matrices do) or live between $t^{-1/3}$ and $t^{-1/2}$.
  • The constructed $10\times10$ game is a concrete finite witness that a natural learning dynamic can be slow without any appeal to adversarial tie-breaking.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The double-loop mechanism is modular: coupling more RPS copies could plausibly push the lower bound closer to $t^{-1/2}$, though the paper only establishes the $t^{-1/3}$ exponent.
  • The exact quadratic periodicity of RPS is the engine of the construction; similar exact periodic trajectories in other small games could be used to build hard instances for other learning dynamics.
  • The fully negative interaction matrix realizes a generic 'cancelling progress' principle that could transfer to no-regret algorithms beyond fictitious play, such as online mirror descent or Frank-Wolfe variants.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper constructs a 9x9 symmetric zero-sum game, augmented to a 10x10 game with a dummy action, and claims that fictitious play (FP) on this game converges at rate Omega(t^{-1/3}), with no ties after the first step. This is presented as a disproof of the weaker form of Karlin's conjecture. The construction embeds three rock-paper-scissors blocks coupled by an interaction matrix B, and the proof relies on a phased structure in which FP plays one block at a time (Lemma 3, Theorem 1). Lemma 2 is the key technical step that keeps the first block's utility maximum above the other blocks throughout a phase.

Significance. If correct, the result would be a significant resolution of a long-standing open question, extending the Daskalakis--Pan counterexample to the tie-breaking-agnostic setting. The paper's explicit 10x10 matrix and the transfer argument in Lemma 1 are attractive features, and the algebraic identities in Section 4.2 are verifiable by direct substitution. However, the central lower-bound proof is invalid as written because Lemma 2 relies on a false numerical bound, and the stated sufficient condition (13) is not satisfied by the printed constants. The main theorem is therefore unproved.

major comments (3)
  1. [Section 4.3, Lemma 2] The proof of Lemma 2 asserts that the right-hand side of (14), RHS(tau) = max{V2 vec{k} - B(x^{rps}_{t0+tau} - x^{rps}_{t0})}, grows by at least 1/12 per step. This is false for the printed matrix B = -(1/900)[[71,54,75],[54,21,25],[75,25,50]]. The entries of -B are positive but the smallest is 21/900, not 1/12 = 75/900. When action 2 is played, the increment added to the second block is column 2 of -B, namely [54,21,25]/900, so if the current maximizing row is row 2 the maximum increases by only 21/900. Consequently the three-case estimate that keeps RHS below LHS throughout [0, T_{k+1}-T_k) is not established. A direct check for k=1 at tau = T_2-T_1-29 gives the proof's upper bound on RHS as about 35.66 while the true value is about 36.33, so the claimed bound is numerically violated. Since Lemma 2 drives the induction in Lemma 3 and hence Theorem 1, the lower-bound proof collapses.
  2. [Section 4.2] The sufficient condition (13) requires 0 < max{V1 vec{k}} - max{V3 vec{k}} < -max{B}. The paper states that max{V1 vec{k}} - max{V3 vec{k}} = 1/27 in (0, -max{B}), but with the printed B we have max{B} = -21/900, so -max{B} = 7/300 ≈ 0.0233, which is strictly less than 1/27 ≈ 0.0370. Thus the stated condition (13) is false for the given instance. This condition is the mechanism that ensures the second block catches up with the first block only at the phase endpoint; without it, the outer-loop timing in Figure 2 and Lemma 2's conclusion are not guaranteed. The claim that a brute-force search found a solution satisfying (12) and (13) is therefore contradicted by the displayed matrices.
  3. [Section 4.3, Lemma 2 proof, case structure] Even setting aside the exact value of the increment, the proof's case analysis uses the bound LHS >= max{V1 vec{k}} - (4k+17) for tau < T_{k+1} - 12(4k+17) - 1 and a 1/(24k) slope bound in the middle interval. These estimates are coupled to the incorrect 1/12 growth rate of RHS. Since the actual minimal growth of RHS is 21/900, the inequalities labeled RHS in the three displayed chains are not valid, and no alternative argument is supplied to show that max{Ut[1:3]} exceeds max{Ut[4:9]} for all tau in the phase. The phase structure is thus unsupported.
minor comments (4)
  1. [Section 4.4] The sentence 'the fact that a gap exists between the first and second largest entry except for the second step' should refer to the first step of the augmented game, where the dummy action is played and a tie necessarily occurs; the wording is confusing.
  2. [Section 4.3, Lemma 2 proof] In the proof of (15), the text says 'the second equality holds' but the step is an inequality; this is a typographical issue that does not affect the argument.
  3. [Notation] The notation - -> k for [k^2; k; 1]^T is unconventional and visually resembles a negation; consider a clearer symbol such as v(k) or p(k).
  4. [Appendix A] The augmented matrix M_aug is presented with delta = 1/2700, but the earlier definition allows any delta in (0,1/1800); the dependence of the matrix entries on delta should be stated explicitly in the appendix to avoid an apparent inconsistency with the main text's U0 definition.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the lower bound is derived from an explicit construction and algebraic verification, not from a fitted target.

full rationale

The paper's derivation chain is self-contained and non-circular. It constructs a 9x9 symmetric game M by choosing RPS-admissible matrices Q0 and Q1 and solving the matrix equation (12) for B and Delta; this is a constructive existence proof, not a fit of the target rate. The claimed lower bound Gap = Theta(t^{-1/3}) at t = T_{3k+1} follows from the explicit phase equations (10)-(12), Lemma 3's induction, and the computation max{U_t} = Theta(k^2) = Theta(t^{2/3}) in Theorem 1; nothing in this chain is defined in terms of the gap it purports to predict. The surrounding references (Karlin, Daskalakis-Pan, Abernethy et al.) are external results used only for context and contrast, not load-bearing self-citations. The only concerns raised by the reader—that constants were reverse-engineered, and that the numerical condition (13) and Lemma 2's second-block growth bound may fail for the printed B—are verification/correctness issues, not circular reasoning; a false lemma makes the proof unsound, but it does not make the argument circular. I therefore find no pattern of self-definition, fitted-input-called-prediction, or self-citation load-bearing reduction.

Assumptions & free parameters 3 free parameters · 4 assumptions · 1 invented entities

The construction rests on explicitly given rational matrices (B, Δ, Q0, Q1, V1, V2, V3) and on the RPS periodicity lemmas, which are proved or verified. The main unproved and incorrect ingredient is the claimed phase-timing condition (13), which fails for the printed constants.

free parameters (3)
  • B (3x3 symmetric interaction matrix) = -(1/900) [[71,54,75],[54,21,25],[75,25,50]]
    Chosen by brute-force search (Section 4.2) to satisfy the key equation (12) and produce the double-loop phase structure. The paper's claimed sufficient condition (13) is actually violated: -max{B} = 7/300 < 1/27.
  • Delta (3-vector offset for block 1) = [2, 298/27, 0]^T (text garbled as [2,290,27,0]^T)
    Chosen with B so that (12) holds; enters V1 = 1 Delta^T + A_rps Q0. Verified by substitution against the printed V1.
  • Q0, Q1 (admissible quadratic matrices) = Q0 = [[12,8,-12],[12,0,0],[12,4,0]], Q1 = [[48,208,225],[48,200,213],[48,200,208]]
    Derived from RPS periodicity (Fact 2) via interpolation (Fact 3); verified for k=1 and k=2. Q = Q1 - Q0 determines each phase length.
assumptions (4)
  • standard math Fact 2: RPS periodicity formulas (5)-(7) for lexicographic tie-breaking
    Proved in Appendix B.1 by induction; verified. Minor typo: appendix writes t=9k²+12k+6 instead of 9k²+12k+4.
  • domain assumption Fact 3: Q0 and Q1 are admissible for RPS
    Asserted via interpolation of Fact 2 vertices; verified by direct substitution for k=1, k=2. The proof sketch is thin but the claim checks out.
  • standard math Fact 1: max{U_t} is non-decreasing in FP
    Proved immediately after (4); relies on A = -A^T (diagonal zero).
  • ad hoc to paper The phase-structure sufficiency of conditions (10) and (13)
    Equation (12) is necessary but not sufficient (the paper admits this); the additional timing condition (13) is stated but is not satisfied by the printed constants, since 1/27 > 7/300.
invented entities (1)
  • Dummy action in M_aug
    purpose: absorbs the only tie at the first step so that the lower bound is tie-breaking-agnostic
    A standard construction device in the game matrix; it is part of the explicit 10-by-10 matrix, not an external postulate.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Tie-breaking Agnostic Lower Bound for Fictitious Play." pith.science (2026). https://pith.science/paper/EZ5LOMBI

@misc{pith2026250709902,
  author       = {Pith},
  title        = {Pith review of: Tie-breaking Agnostic Lower Bound for Fictitious Play},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EZ5LOMBI}},
  note         = {Machine review of arXiv:2507.09902}
}
abstract

Fictitious play (FP) is a natural learning dynamic in two-player zero-sum games. Samuel Karlin conjectured in 1959 that FP converges at a rate of $O(t^{-1/2})$ to Nash equilibrium, where $t$ is the number of steps played. However, Daskalakis and Pan disproved the stronger form of this conjecture in 2014, where \emph{adversarial} tie-breaking is allowed. This paper disproves Karlin's conjecture in its weaker form. In particular, there exists a 10-by-10 zero-sum matrix game, in which FP converges at a rate of $\Omega(t^{-1/3})$, and no ties occur except for the first step.

Figures

Figures reproduced from arXiv: 2507.09902 by the authors.

Figure 1
Figure 1. Phased Structure. It is assumed that k mod 3 = 1 here for illustration. It is straightforward to see that if the phased structure in [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Evolution of the maximum within each block. [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Duality gap of xt/t vs t for FP in Maug then UTk+1 =   V1 −→k V2 −→k V3 −→k   +   Arps B −B −B Arps B B −B Arps     Q −→k 0 0   =   V3 −−−→ k + 1 V1 −−−→ k + 1 V2 −−−→ k + 1   . Because of the cyclic symmetry of M, the same proof of Lemma 3 implies that UTk+2 =   V2 −−−→ k + 2 V3 −−−→ k + 2 V1 −−−→ k + 2   , UTk+3 =   V1 −−−→ k + 3 V2 −−−→ k + 3 V3 −−−→ k + 3   . For the case of k = 0… view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

13 extracted references · 12 canonical work pages

  1. [1]

    Fast convergence of fictitious play for diagonal payoff matrices

    Jacob Abernethy, Kevin A Lai, and Andre Wibisono. Fast convergence of fictitious play for diagonal payoff matrices. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1387--1404. SIAM, 2021

    work page 2021

  2. [2]

    Fictitious play in 2 n games

    Ulrich Berger. Fictitious play in 2 n games. Journal of Economic Theory, 120 0 (2): 0 139--154, 2005

    work page 2005

  3. [3]

    Iterative solution of games by fictitious play

    George W Brown. Iterative solution of games by fictitious play. Act. Anal. Prod Allocation, 13 0 (1): 0 374, 1951

    work page 1951

  4. [4]

    A counter-example to karlin's strong conjecture for fictitious play

    Constantinos Daskalakis and Qinxuan Pan. A counter-example to karlin's strong conjecture for fictitious play. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 11--20. IEEE, 2014

    work page 2014

  5. [5]

    Fictitious play, shapley polygons, and the replicator equation

    Andrea Gaunersdorfer and Josef Hofbauer. Fictitious play, shapley polygons, and the replicator equation. Games and Economic Behavior, 11 0 (2): 0 279--303, 1995

    work page 1995

  6. [6]

    Frank-wolfe algorithms for saddle point problems

    Gauthier Gidel, Tony Jebara, and Simon Lacoste-Julien. Frank-wolfe algorithms for saddle point problems. In Artificial Intelligence and Statistics, pages 362--371. PMLR, 2017

    work page 2017

  7. [7]

    On the rate of convergence of continuous-time fictitious play

    Christopher Harris. On the rate of convergence of continuous-time fictitious play. Games and Economic Behavior, 22 0 (2): 0 238--259, 1998

    work page 1998

  8. [8]

    Deep reinforcement learning from self-play in imperfect-information games

    Johannes Heinrich and David Silver. Deep reinforcement learning from self-play in imperfect-information games. arXiv preprint arXiv:1603.01121, 2016

    arXiv 2016

Show all 13 references
  1. [9]

    Fictitious self-play in extensive-form games

    Johannes Heinrich, Marc Lanctot, and David Silver. Fictitious self-play in extensive-form games. In International conference on machine learning, pages 805--813. PMLR, 2015

    2015

  2. [10]

    Mathematical Methods and Theory in Games, Programming, and Economics: Matrix Games, Programming, and Economics

    Samuel Karlin. Mathematical Methods and Theory in Games, Programming, and Economics: Matrix Games, Programming, and Economics. Pergamon, 1959

    1959

  3. [11]

    An iterative method of solving a game

    Julia Robinson. An iterative method of solving a game. Annals of mathematics, pages 296--301, 1951

    1951

  4. [12]

    Note on a computation method in the theory of games

    Harold N Shapiro. Note on a computation method in the theory of games. Communications on Pure and Applied Mathematics, 11 0 (4): 0 587--593, 1958

    1958

  5. [13]

    J v. Neumann. Zur theorie der gesellschaftsspiele. Mathematische annalen, 100 0 (1): 0 295--320, 1928

    1928

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.