{"id":"d55c7607-1d58-4771-a197-596b33de2fc8","arxiv_id":"2507.09902","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A tie-breaking-agnostic 10-by-10 counterexample makes fictitious play converge at rate Ω(t^{-1/3}), disproving the weak form of Karlin's 1959 conjecture.","lead":"There exists a 10-by-10 zero-sum game where fictitious play, a classic learning rule from 1951, improves toward equilibrium no faster than t^{-1/3}, no matter how ties are broken. This refutes the weak form of Karlin's 1959 conjecture, which predicted a t^{-1/2} rate.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 2's second-block growth bound is false: with the printed B the per-step increment can be as low as 21/900, not 1/12, and the paper's own condition (13) is violated since −max{B}=7/300<1/27. The lower-bound proof collapses.","rationale":"I read the paper in good faith. The algebraic setup is substantial: the RPS periodicity, the admissible matrices Q0 and Q1, equation (12), and the boundary identities appear internally consistent, and the numerical experiment agrees with the claimed rate. However, Lemma 2 is the only bridge from the algebraic construction to the trajectory claim, and its proof contains a numerical inequality that is demonstrably false with the printed B. The reader's pinpointed weakness is correct: the asserted 1/12 per-step growth is not a lower bound for the actual increments, and the paper's own sufficient condition (13) is violated because −max{B}=7/300<1/27. This is not a stylistic gap or a missing detail; the specific bound used to control RHS is numerically violated. Since there is no formal verification and no alternative argument for the phase structure, the central claim is not established as submitted. The construction may or may not be repairable by changing B or the timing constants, but the submitted proof of the lower bound fails.","tokens_in":10302,"tokens_out":14114,"duration_ms":155184,"concrete_test":"Run an exact rational simulation of the RPS segment for k=1 and k=2 with the printed matrices: for each τ∈[0,T_{k+1}−T_k), compute LHS(τ)=max{V1+A_rps δ} and RHS(τ)=max{V2−B δ}, where δ=x^{rps}_{t0+τ}−x^{rps}_{t0} and t0=1^T Q0 vec{k}. If any τ has LHS(τ)≤RHS(τ), Lemma 2 is false and the induction in Lemma 3 fails at that step. If no violation is found, rerun the proof's three-case estimate with the true per-step lower bound min_{i,j}(−B_{ij})=21/900 (or, if justified, the action-dependent values 54/900 and 75/900), and check whether the inequalities still close for all k≥1. This determines whether the phase structure of the construction actually holds.","verdict_should_be":"REJECT","load_bearing_attack":"The load-bearing step is Lemma 2 (Section 4.3), which drives Lemma 3's induction and hence Theorem 1. Its proof asserts that the right-hand side of (14), RHS(τ)=max{V2−B(x^{rps}_{t0+τ}−x^{rps}_{t0})}, grows by at least 1/12 at every step. For the printed B=−(1/900)[[71,54,75],[54,21,25],[75,25,50]], every entry of −B is positive, but the smallest is 21/900. In particular, when action 2 is played the increment is column 2 of −B, namely [54,21,25]/900, so if the current maximizing row is row 2 the maximum grows by only 21/900, and if it is row 1 by 54/900=3/50; neither is 1/12=75/900. Thus the asserted uniform lower bound is false, and 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 τ=T2−T1−29 gives the proof's RHS upper bound as 35.66 while the true RHS is about 36.33, so the bound is numerically violated, not merely loose. Independently, Section 4.2 states max{V1}−max{V3}=1/27∈(0,−max{B}); but with the printed B, max{B}=−21/900 and −max{B}=7/300≈0.0233<1/27≈0.0370, so sufficient condition (13) is false. Since no alternative proof of the phase structure is supplied, Theorem 1 is unproved as submitted; the numerical experiment and the verified algebraic identities do not repair this gap.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":10703,"tokens_out":2943,"duration_ms":31425,"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":[{"comment":"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.","section":"Section 4.3, Lemma 2"},{"comment":"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.","section":"Section 4.2"},{"comment":"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.","section":"Section 4.3, Lemma 2 proof, case structure"}],"minor_comments":[{"comment":"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.","section":"Section 4.4"},{"comment":"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.","section":"Section 4.3, Lemma 2 proof"},{"comment":"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).","section":"Notation"},{"comment":"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.","section":"Appendix A"}],"recommendation":"reject","confidential_remarks":"The paper addresses a significant open problem and the overall strategy is inventive, but the submitted construction contains a concrete numerical error that invalidates the main theorem. The error is not a typo in an auxiliary claim: the printed B fails the paper's own sufficient condition, and Lemma 2's growth bound is false by about a factor of four in the worst case. Repairing this would require finding a new B (and possibly Delta and Q matrices) that actually satisfies (12) and (13), which is substantial new work rather than a local correction. I therefore recommend rejection, while noting that a corrected version with a valid instance would be a strong paper."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take on 2507.09902. The double-loop RPS construction is the right idea, and the algebraic framework is genuinely nice: Q0 and Q1 are admissible, the block identities (10) solve cleanly, and the numerical experiment shows the claimed Θ(t^{-1/3}) rate. If this worked, it would settle the weak Karlin conjecture, and the tie-breaking-agnostic 10x10 augmentation is a thoughtful touch.\n\nBut the proof as written doesn't go through. Lemma 2 is the load-bearing step, and its central estimate is wrong. The paper asserts that the RHS of (14) grows by at least 1/12 per step because '-max{A}=1/12'. With the printed B, -B has smallest entry 21/900 ≈ 0.0233, so a step can add as little as 21/900 to the second block's max. That's not 1/12. The three-case bound built on this doesn't hold; the stress-test's concrete counterexample for k=1 (τ = T2-T1-29) shows the claimed upper bound 35.66 versus true RHS about 36.33. This isn't a loose constant—the inequality fails numerically.\n\nIndependently, the paper states that max{V1}-max{V3}=1/27 lies in (0,-max{B}). But with the printed B, -max{B}=7/300≈0.0233, which is less than 1/27≈0.0370. So the sufficient condition (13) is false. The text says 'It can then be checked', but the check fails.\n\nSo the main theorem is unproved. The construction may be salvageable—the violation is quantitative, not a structural flaw in the phase idea—but the current manuscript doesn't supply a valid proof. The numerical experiment is consistent but doesn't repair the gap.\n\nWho benefits from reading this? Anyone working on FP rates or Karlin's conjecture will find the construction instructive, and the error is worth knowing about. But the central claim should not be accepted as-is. I'd send it to peer review, because the result is significant and the construction is plausible enough that a careful referee might help the author fix the proof. But my verdict is reject-and-resubmit, not accept.","headline":"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.","tokens_in":11300,"tokens_out":3901,"would_cite":false,"duration_ms":38032,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91A05","91A26"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["fictitious play","Karlin's conjecture","zero-sum games","convergence rate lower bound","tie-breaking agnostic","rock-paper-scissors game","Nash equilibrium","symmetric games"],"falsifier":"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.","tokens_in":10026,"feed_emoji":"🎲","tokens_out":7844,"duration_ms":77329,"temperature":0.7,"pith_summary":"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.","feed_headline":"10-by-10 zero-sum game slows fictitious play to t^{-1/3}","feed_subtitle":"More than 60 years after Karlin's conjecture, a tie-free game shows the classic learning rule can be much slower than 1/sqrt(t).","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"states the $O(t^{-1/2})$ conjecture that this paper refutes in its weaker form.","marker":"Karlin [1959]"},{"why":"gives the strong-form counterexample under adversarial tie-breaking that this paper eliminates the reliance on.","marker":"Daskalakis and Pan [2014]"},{"why":"introduces fictitious play, the algorithm under study.","marker":"Brown [1951]"},{"why":"supplies the classical convergence analysis whose $O(t^{-1/(m+n-2)})$ rate is the starting point for the lower-bound question.","marker":"Robinson, 1951, Shapiro, 1958"},{"why":"shows diagonal payoff matrices converge at $O(t^{-1/2})$ under lexicographic tie-breaking, which motivates the weak form and provides the contrast class.","marker":"Abernethy et al. [2021]"},{"why":"gives the continuous-time fictitious play convergence result that highlights the discrete-continuous rate gap.","marker":"Harris [1998]"}],"fun_headline_variants":["Fictitious play hits t^{-1/3} wall in 10x10 game","Tie-free 10x10 game defeats Karlin's 1959 conjecture","After 60 years, Karlin's speed conjecture falls to 10x10 game","10x10 zero-sum game: FP no faster than t^{-1/3}"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Fictitious play hits t^{-1/3} wall in 10x10 game","Tie-free 10x10 game defeats Karlin's 1959 conjecture","After 60 years, Karlin's speed conjecture falls to 10x10 game","10x10 zero-sum game: FP no faster than t^{-1/3}"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000695,"raw_usage":{"total_tokens":3122,"prompt_tokens":904,"completion_tokens":2218,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":520,"completion_tokens_details":{"reasoning_tokens":2128}},"tokens_in":520,"tokens_out":2218,"duration_ms":17633,"temperature":1.0,"reasoning_tokens":2128,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T17:51:04.268841+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Mathematical Methods and Theory in Games, Programming, and Economics: Matrix Games, Programming, and Economics","cited_arxiv_id":null,"evidence_quote":"states the $O(t^{-1/2})$ conjecture that this paper refutes in its weaker form."},{"cited_title":"A counter-example to karlin's strong conjecture for fictitious play","cited_arxiv_id":null,"evidence_quote":"gives the strong-form counterexample under adversarial tie-breaking that this paper eliminates the reliance on."},{"cited_title":"Iterative solution of games by fictitious play","cited_arxiv_id":null,"evidence_quote":"introduces fictitious play, the algorithm under study."},{"cited_title":"An iterative method of solving a game","cited_arxiv_id":null,"evidence_quote":"supplies the classical convergence analysis whose $O(t^{-1/(m+n-2)})$ rate is the starting point for the lower-bound question."},{"cited_title":"Fast convergence of fictitious play for diagonal payoff matrices","cited_arxiv_id":null,"evidence_quote":"shows diagonal payoff matrices converge at $O(t^{-1/2})$ under lexicographic tie-breaking, which motivates the weak form and provides the contrast class."},{"cited_title":"On the rate of convergence of continuous-time fictitious play","cited_arxiv_id":null,"evidence_quote":"gives the continuous-time fictitious play convergence result that highlights the discrete-continuous rate gap."}],"review_version":1}