{"id":"229a0b1e-ba77-421f-9919-ae6c538e37a6","arxiv_id":"2507.11366","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Alternating gradient descent energy invariants can be turned into linear equations that recover the Nash equilibrium in O(k) iterations, provided the equation system is non-degenerate.","lead":"This paper derives linear equations from alternating gradient descent that, when solvable, pin down the Nash equilibrium of a zero-sum game after only a linear number of update steps. The approach is novel but relies on a non-degeneracy condition that is demonstrated empirically rather than proven.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 5–6 claim a finite characterization only 'modulo degeneracy,' but the paper never proves the constructed linear system is generically full rank; without that, the central claim rests on an unstated, untested rank condition.","rationale":"I read the paper in good faith: the invariant-energy algebra in Theorems 1–12 checks out, the experiments are reproducible in structure, and the parallelization idea is a reasonable response to the ill-conditioning observed in Section 5. The reader's weakest_assumption correctly identifies the unproven full-rank condition as the load-bearing premise. My stress-test sharpens it: the full-rank condition is not merely a technical caveat, because for singular A the NE set is non-unique and the constructed equations necessarily have a non-trivial nullspace, so the paper's 'modulo degeneracy' phrasing quietly excludes a whole class of games without saying so. For invertible A, a direct Jacobian calculation indicates the parallelized row map is generically full rank, which means the gap is likely repairable by a short lemma rather than a fundamental flaw. Because the concern is real but addressable, and because the paper's own experiments plus the derivable genericity argument point toward a positive resolution, I do not move the verdict away from CONDITIONAL. The reader's moderate-confidence conditional verdict remains appropriate: the central theorem should be revised to include a stated, proven non-degeneracy condition or an explicit characterization of the degenerate cases.","tokens_in":40183,"tokens_out":18667,"duration_ms":217640,"concrete_test":"Independently derive the coefficient rows of Theorem 5 (zero-sum) and Theorem 6 (coordination) as functions of the parallelized initial conditions in Section 6.1. Compute the Jacobian of the row map with respect to (x0, y0); for zero-sum it should be the block matrix M = [[-eta2 A A^T, 2A], [-2A^T, 0]] (with an analogous block matrix for coordination). Verify that for invertible A, det M is a nonzero constant multiple of det(A)^2 for all positive learning rates eta1, eta2. If this holds, the paper's missing lemma is the generic full-rank statement; if it fails, exhibit concrete (A, eta1, eta2) with det M = 0 and confirm numerically that the parallelized system is singular for all random seeds, which would falsify the unrestricted 'arbitrary learning rates' claim.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim that 2k, 2k+1, or k iterations of Alternating GD suffice to characterize the NE depends entirely on the linear system in Theorems 5, 6, 8, 10, 11, and 12 having full rank. The paper flags this as 'modulo degeneracy' (Sections 4.1 and 5) but never states which games are degenerate, proves the system is generically nonsingular, or bounds the probability of singularity under the random initializations used in Section 6. If the matrix is singular, the equations define a superset of the NE set, so the method does not actually characterize the NE. For games with non-unique NE, i.e., singular payoff matrix A, full rank is impossible because every NE satisfies the same homogeneous relations; hence the claimed characterization silently excludes all games with a non-trivial NE set, a limitation the paper does not state. A direct computation of the map from parallelized initial conditions to the coefficient rows shows its linear part has kernel null(A^T) x null(A), suggesting the system is generically full rank iff A is invertible, but this argument is absent from the paper. Without it, the theorems only say 'if the equations happen to be independent, the solution is the NE,' which is not a proof of finite-iteration characterization for any concrete game.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies alternating gradient descent (AGD) in two-agent unbounded zero-sum and coordination games with linear costs. It shows that the discrete-time AGD dynamics admit an invariant energy (a perturbed distance to the Nash equilibrium). Taking differences of this energy at consecutive iterations yields equations that are linear in the unknown equilibrium strategy and/or cost vectors, provided the game is zero-sum or coordination. The paper proposes three models requiring observation of different information (both strategies; one strategy plus the opponent's norm; one strategy plus the opponent's gradient norm), and claims that, modulo a non-degeneracy condition, 2k, 2k+1, or k iterations suffice to generate a linear system whose solution is the Nash equilibrium. Numerical experiments show that solving this system directly is numerically unstable, but a parallelized version using fresh random initial conditions for each equation yields accurate solutions very quickly for random invertible payoff matrices.","tokens_in":40446,"tokens_out":11500,"duration_ms":127372,"significance":"If the rank question were resolved, the core idea would be valuable: it gives a finite-time, equation-based alternative to asymptotic time-average or last-iterate convergence for finding Nash equilibria, and the parallelization and learning-rate independence are appealing. The algebraic proofs of the invariant energy and of the linear forms appear correct and are presented self-containedly, with the zero-sum invariant re-proved in the appendix. The experiments provide reproducible evidence of high accuracy for random invertible matrices. However, the central theoretical claim currently rests on an uncharacterized 'modulo degeneracy' condition, and the method implicitly excludes games with non-unique equilibria. These gaps substantially temper the novelty as stated.","major_comments":[{"comment":"The theorems prove only that every Nash equilibrium satisfies the displayed linear equations; they never prove that the assembled 2k×2k (or k×k) system has full rank. The phrase 'modulo degeneracy' (Section 4.1, Section 5) is never made precise: no condition on A, the learning rates, or the initial conditions is identified that guarantees non-singularity. Table 2 shows that for a single trajectory the determinant is already about 10^-7 at dimension 3, so degeneracy is not a rare pathology, and Section 6's parallelization is supported only by experiments. Without a genericity or probability bound, the central claim of a finite-iteration characterization is not established for any specific game.","section":"Theorems 5–12; Sections 4.1, 5, 6"},{"comment":"For any two Nash equilibria (x*, y*) and (x*+Δx, y*+Δy), the difference of the two equalities in Theorem 5 shows the row vector at time t is orthogonal to (Δx, Δy). Consequently, whenever the NE set has positive dimension (which occurs exactly when A is singular and the NE conditions are consistent), the 2k×2k system matrix necessarily has a nontrivial nullspace, so the method cannot 'characterize the set of NE' for such games. This limitation is not stated in the abstract or in the model description; the paper should either restrict all claims to unique-NE games or explain how degeneracy is resolved.","section":"Section 4.2, Theorem 5; NE conditions"},{"comment":"The claim that parallelization 'fundamentally changes the structure of linear systems' and yields well-conditioned matrices is not accompanied by any theoretical justification. Since each row is an affine function of the initial condition, one can compute the linear part of the map from initial conditions to rows; its kernel is null(A^T) × null(A), which would establish generic full rank for invertible A and also confirm the obstruction for singular A. This argument is absent, and without it the parallelized method is an empirical heuristic rather than a theorem.","section":"Section 6"}],"minor_comments":[{"comment":"The claims 'a first in online optimization' and 'both firsts in algorithmic game theory' are difficult to verify and are not supported by a thorough literature comparison; they should be qualified or removed.","section":"Abstract; Section 1.1"},{"comment":"Table 5 reports relative errors near 1.0 for dimensions 100–500 even with the least-squares method, which is at odds with the narrative that least squares 'stabilizes' the system; this discrepancy is not discussed in the text.","section":"Section 5.3.1, Table 5"},{"comment":"The term 'modulo degeneracy' is used informally; the paper should give a formal definition, for example 'the linear system constructed from the displayed equations has full row rank,' and state what happens to the solution set when this fails.","section":"Section 4.1"},{"comment":"The abstract and introduction should be consistent with the fact that the models of Sections 4.3 and 4.4 characterize only x* (and b1) and require a symmetric model to obtain y*; as written, some passages suggest the full equilibrium is recovered.","section":"Sections 4.3 and 4.4"},{"comment":"The proof of Theorem 10 is only sketched in the main text, with no appendix; the paper should either provide the full proof or state that it follows from Theorem 9 with the same cancellation as in Theorem 8.","section":"Theorems 8 and 10"},{"comment":"There are several typographical issues, e.g., 'V on Neumann' in the Introduction and inconsistent subscript formatting in the appendices; a careful proofread is recommended.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The paper is likely to be of interest to the algorithmic game theory community if the rank gap is closed. The novelty claims are overstated; the energy invariants are already known (cited [4,3]), and the genuinely new part is the equation-based characterization. The authors should be encouraged to add a genericity theorem and to clearly delimit the class of games (unique NE, invertible A) for which the method is proven."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the short version: the finite-iteration characterization is a real result, but it only holds for games with a unique Nash equilibrium, and the paper doesn't tell you that. The 'modulo degeneracy' caveat is doing more work than the authors acknowledge.\n\nWhat's genuinely new: turning the known energy invariants for alternating GD into linear equations in the NE, and the three observational models that reduce what each agent needs to see. The parallelization idea—using one update per initial condition to avoid correlated equations—is clever, and the experiments show it works well on random instances. The algebra is carefully done and the invariants are re-proved in the text, not just cited.\n\nThe soft spot is structural. The linear system built from energy differences has full rank only if the payoff matrix A is invertible. If A is singular, the NE set is a nontrivial affine subspace, and every valid NE satisfies the same homogeneous relations, so the coefficients collapse. That means the method silently excludes every zero-sum or coordination game with non-unique NE—a standard case—and the paper doesn't state this. The 'modulo degeneracy' phrasing pushes it into a footnote, but it's actually the boundary of the theorem. The authors should either prove generic full rank under the random initialization they use, or explicitly restrict the claims to games with a unique NE. The experiments only sample invertible A (random matrices), so they don't expose this.\n\nMinor issues: the 'firsts' in the abstract are a bit loose, and the baseline is only time-average convergence; a comparison with optimistic GD or extragradient would be fairer. But those are secondary.\n\nBottom line: the core math is solid, the idea is new, and the limitation is fixable. I'd send it to a serious referee. The right revision would name the invertibility condition, prove or at least carefully state the degeneracy, and soften the 'first' claims.","headline":"The finite-iteration characterization is real but only works for games with a unique Nash equilibrium; the unproven 'modulo degeneracy' caveat is actually the main limitation and needs to be stated up front.","tokens_in":40928,"tokens_out":2118,"would_cite":true,"duration_ms":27053,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91A05","91A10","91A26","90C47"],"pacs":[],"model":"deepseek-v4-flash","headline":"Modulo degeneracy, a linear number of alternating gradient descent iterations — 2k, 2k+1, or k, depending on what is observed — yields linear equations whose solution is the Nash equilibrium of a zero-sum or coordination game.","keywords":["zero-sum games","Nash equilibrium","alternating gradient descent","Hamiltonian dynamics","invariant energy function","online optimization","parallelizable algorithms","arbitrary learning rates"],"falsifier":"For the one-dimensional zero-sum game with payoff $a$, costs $b_1, b_2$, and learning rates $\\eta_1, \\eta_2$, derive the two Section 4.2 equations from three consecutive alternated updates, view them as a $2\\times 2$ linear system in $(x^*, y^*)$, and compute the determinant symbolically as a function of $a$, $b_1$, $b_2$, $\\eta_1$, $\\eta_2$, and the starting point. If any non-degenerate game (unique equilibrium, $a \\neq 0$) has a starting point where the determinant vanishes, the finite-iteration characterization fails outside the degeneracies the paper acknowledges; if the determinant is nonzero on a dense set of parameters, that calculation shows exactly how large the 'modulo degeneracy' caveat is.","tokens_in":39971,"feed_emoji":"🎯","tokens_out":18445,"duration_ms":194959,"temperature":0.7,"pith_summary":"This paper attempts to establish that alternating gradient descent in zero-sum and coordination games does more than converge slowly: every update step yields one linear equation in the unknown Nash equilibrium, so after a number of steps linear in the dimension ($2k$, $2k+1$, or $k$, depending on what is observed) the accumulated equations form a linear system whose solution is the equilibrium. The statement carries an explicit caveat, \"modulo degeneracy\": the system must be non-singular for the equilibrium to be its unique solution, and the paper assumes rather than proves this rank condition. If the claim is right, it replaces asymptotic time-average or last-iterate guarantees with a direct solve after a finite number of gradient queries, works with arbitrary learning rates, and parallelizes across independent runs. The authors report that the parallelized version reaches about $10^{-10}$ relative error in under a second in dimensions up to 20 (and stays accurate at dimension 500), where time-average alternating gradient descent reaches only about $10^{-6}$ after five minutes in dimension 7.","feed_headline":"A linear number of gradient steps characterizes Nash equilibria","feed_subtitle":"Solving those equations gives the equilibrium outright; time-averaging needs thousands of rounds to get close.","key_machinery":"The load-bearing object is the discrete-time invariant energy function, called the perturbed energy — for zero-sum games $h^-_t = \\|x_t - x^*\\|^2/\\eta_1 + \\|y_t - y^*\\|^2/\\eta_2 + \\langle x_t, Ay_t - b_1\\rangle + \\langle y_t, b_2\\rangle$, with an analogous $h^+_t$ for coordination games in which the agent-2 squared-distance and inner-product terms enter with opposite signs. Theorems 1 and 2 prove $h^-_t = h^-_0$ and $h^+_t = h^+_0$ for every $t$ under alternating gradient descent, using only the unbounded-setting first-order conditions $Ay^* = b_1$ and $Bx^* = b_2$. The mechanism that carries the argument is the difference $h^-_t - h^-_{t+1} = 0$: expanding it cancels the quadratic terms and leaves one linear equation in the unknown equilibrium per iteration, each row of the eventual linear system. The physical motivation — alternating gradient descent as a symplectic Störmer-Verlet discretization of Hamiltonian dynamics whose energy is squared distance to the NE — explains why such an invariant exists, but the linearity of the expanded differences is what does the mathematical work.","core_discovery":"On the paper's own terms, the central discovery is that the time-invariant \"perturbed energy\" conserved exactly by alternating gradient descent in a zero-sum game (with a sibling energy in coordination games) is not only a convergence tool: expanding its constancy across two consecutive iterations gives an equation that is linear in the unknown equilibrium $(x^*, y^*)$ and the linear cost terms, with every coefficient observable from the agents' strategies and gradients, without knowing the payoff matrix. Three models trade information for iteration count: observing both agents' strategies recovers $(x^*, y^*)$ from $2k$ equations; observing only the opponent's strategy norm recovers $(x^*, b_1)$ from $2k+1$ equations; observing only the opponent's gradient norm recovers $x^*$ from $k$ equations. The authors are careful to state that they do not claim the dynamics themselves solve for the equilibrium in finite time; they claim that the dynamics supply the linear system $A'(x^*, y^*) = b'$, and that solving that system, when it is non-singular, characterizes the NE exactly. They further claim this is the first finite-iteration characterization in online optimization in games, and the first such method that is parallelizable and supports arbitrary learning rates.","pith_inferences":["My inference: the consecutive-energy-difference trick should transfer to any discrete-time dynamic that conserves or nearly conserves a quadratic invariant in the unknown equilibrium, such as extragradient or optimistic variants, converting each step into a row of a linear system; the paper does not explore this generalization.","My inference: the practical reach of the method depends on how often the 'modulo degeneracy' caveat binds, and the experiments do not prove it is rare — a concentration or genericity result showing random independent initializations are full-rank with high probability would convert the observed conditioning into a guarantee.","My inference: since only one or two updates per trajectory are needed, the method could serve as a probing device that decouples informativeness from convergence, deliberately using large learning rates to collect equations from trajectories that would diverge if run longer — a mode of use the convergence literature would not predict."],"forward_implications":["An equilibrium can be computed from $2k$ (or, in the reduced models, $2k+1$ or $k$) gradient queries made by an online algorithm, with no need to wait for time-averaging or last-iterate convergence.","The procedure works with arbitrary learning rates, so the stability condition $\\sqrt{\\eta_1 \\eta_2} < 2/\\|A\\|$ required for convergence of the underlying dynamics is not a restriction on the characterization.","The computation parallelizes: each equation may come from an independent initial condition, and the experiments indicate the assembled system is then well-conditioned across dimensions.","The reported comparison shows roughly $10^{-10}$ relative error in under a second for the new method versus roughly $10^{-6}$ after five minutes for time-average alternating gradient descent in dimension 7.","Via a variable substitution that preserves zero-sum and coordination structure, the characterization transfers to games on probability simplices when the equilibrium is fully mixed, and to polymatrix zero-sum games through standard reductions."],"supporting_citations":[{"why":"Established that continuous-time alternating gradient descent in zero-sum games is a Hamiltonian system, the physical motivation for searching for exact finite-iteration characterizations.","marker":"[6]"},{"why":"First proved the time-invariant perturbed energy for zero-sum alternating gradient descent that Theorems 1 and 3 turn into linear equations in the unknown NE.","marker":"[4]"},{"why":"First proved the invariant energy for coordination games and the O(1/T) time-average convergence of alternating gradient descent used as the baseline.","marker":"[3]"},{"why":"Supplies the Störmer-Verlet symplectic integration viewpoint that identifies alternating gradient descent as a near-energy-conserving discretization of the Hamiltonian system.","marker":"[21]"},{"why":"Grounds the last-iterate, contraction-based baseline the paper contrasts with: Hamiltonian gradient descent converges linearly but still requires infinitely many iterations.","marker":"[1]"}],"fun_headline_variants":["Conserved energy yields linear equations for Nash equilibria","Zero-sum equilibria from a physics-inspired linear system","Parallelizable NE method with linear gradient queries","Finite-step characterization of Nash equilibria in games"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"For the method to work, the linear equations collected across alternating-gradient iterations must be independent enough that the unknown equilibrium is their unique solution; the paper assumes this full-rank condition, flagging it as \"modulo degeneracy\" in Sections 4.1 and 5, and does not prove that random parallel initialization makes it hold.","fun_headline_variants_meta":{"raw":{"variants":["Conserved energy yields linear equations for Nash equilibria","Zero-sum equilibria from a physics-inspired linear system","Parallelizable NE method with linear gradient queries","Finite-step characterization of Nash equilibria in games"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000259,"raw_usage":{"total_tokens":1585,"prompt_tokens":941,"completion_tokens":644,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":557,"completion_tokens_details":{"reasoning_tokens":583}},"tokens_in":557,"tokens_out":644,"duration_ms":8395,"temperature":1.0,"reasoning_tokens":583,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T17:09:17.208893+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For the one-dimensional zero-sum game with payoff $a$, costs $b_1, b_2$, and learning rates $\\eta_1, \\eta_2$, derive the two Section 4.2 equations from three consecutive alternated updates, view them as a $2\\times 2$ linear system in $(x^*, y^*)$, and compute the determinant symbolically as a function of $a$, $b_1$, $b_2$, $\\eta_1$, $\\eta_2$, and the starting point. If any non-degenerate game (unique equilibrium, $a \\neq 0$) has a starting point where the determinant vanishes, the finite-iteration characterization fails outside the degeneracies the paper acknowledges; if the determinant is nonzero on a dense set of parameters, that calculation shows exactly how large the 'modulo degeneracy' caveat is.","supporting_citations":[{"cited_title":"Bailey and Georgios Piliouras","cited_arxiv_id":null,"evidence_quote":"Established that continuous-time alternating gradient descent in zero-sum games is a Hamiltonian system, the physical motivation for searching for exact finite-iteration characterizations."},{"cited_title":"Bailey, Gauthier Gidel, and Georgios Piliouras","cited_arxiv_id":null,"evidence_quote":"First proved the time-invariant perturbed energy for zero-sum alternating gradient descent that Theorems 1 and 3 turn into linear equations in the unknown NE."},{"cited_title":"$O\\left(1/T\\right)$ Time-Average Convergence in a Generalization of Multiagent Zero-Sum Games","cited_arxiv_id":"2110.02482","evidence_quote":"First proved the invariant energy for coordination games and the O(1/T) time-average convergence of alternating gradient descent used as the baseline."},{"cited_title":"Long-time Energy Conservation , page 162–180","cited_arxiv_id":null,"evidence_quote":"Supplies the Störmer-Verlet symplectic integration viewpoint that identifies alternating gradient descent as a near-energy-conserving discretization of the Hamiltonian system."},{"cited_title":"Last-iterate convergence rates for min-max optimization: Convergence of hamiltonian gradient descent and consensus optimization","cited_arxiv_id":null,"evidence_quote":"Grounds the last-iterate, contraction-based baseline the paper contrasts with: Hamiltonian gradient descent converges linearly but still requires infinitely many iterations."}],"review_version":1}