{"id":"0c23d909-cdc5-4993-8e6f-8f4c34a653e2","arxiv_id":"2608.07336","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A merely monotone linear-quadratic generalized Nash equilibrium problem reduces to one convex quadratic program, and two accelerated QP schemes reach quadratically decaying approximate equilibria.","lead":"Multi-player games with quadratic costs and shared linear constraints, under only a monotonicity condition, can be turned into a single convex quadratic program whose solution is the equilibrium. This makes a class of hard equilibrium computations solvable with standard optimization software and gives faster convergence guarantees than older projection methods.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Core QP equivalence appears sound, but Proposition 4.5 is unproven as stated: the printed APG updates (20a) and (20d) are not the FISTA updates of [4], so the claimed O(1/k^2) last-iterate guarantee is not established for the algorithm actually written.","rationale":"The reader's conditional verdict is justified. I read Lemma 3.1 carefully: the equality of objectives in (12), bounded-below-by-zero, and the Frank-Wolfe attainment argument are valid; the necessity and sufficiency of zero optimal value for a v-GNE follows from the polyhedral normal cone representation, so I do not see an unstated constraint qualification issue. I also found no flaw in Proposition 4.3's use of Guler's accelerated proximal point, assuming exact subproblem solves. The weakest spot is the printed APG algorithm: it is inconsistent with the cited theorem, so the fastest claimed rate is not proven for the stated method. This is a concrete, correctable algorithmic error rather than a defect in the QP-reformulation idea. The same error is noted in the reader's rationale, but the reader's stated weakest assumption, monotonicity, is not my concern: monotonicity is the paper's scope condition and the argument is internally consistent under it. I therefore partially agree with the reader's emphasis and leave the conditional verdict unchanged.","tokens_in":16823,"tokens_out":30088,"duration_ms":282383,"concrete_test":"Run the APG-QP routine in the published GitHub repository on one of the random N=2, m=1 instances of Section 7.1, and also implement the method literally as written in (20a)-(20d). Record lambda_k^T (b - A x_k) for k = 1..10^4 and check whether both satisfy the bound <= C/(k+1)^2 with the constant predicted by [4, Thm. 4.4]. Separately verify whether (20d) satisfies the recurrence (19a) for constant gamma_k = gamma; if the printed update fails the recurrence, or the printed method's gap does not decay as O(1/k^2), Proposition 4.5 must be reworded to refer to the corrected FISTA updates.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma 3.1 and Propositions 4.1/4.3 check out under the stated assumptions: the identity (12) is valid, Frank-Wolfe supplies attainment, and Lemma 3.3 correctly converts objective values into appGNE certificates. The load-bearing gap is in Section 4.3. The smooth gradient of g = x^T F_s x + f^T x + b^T lambda + e^T nu is (2 F_s x + f, b, e), so (20a) is dimensionally inconsistent and misses the factor 2. More importantly, (20d) is not the solution of (19a) for constant gamma: solving theta_{k+1}^2 = (1 - theta_{k+1}) theta_k^2 gives theta_{k+1} = (sqrt(theta_k^4 + 4 theta_k^2) - theta_k^2)/2, not the printed expression. Since the O(1/k^2) bound in Proposition 4.5 is quoted from Beck-Teboulle [4, Thm. 4.4], the sequence used in the proof must be the FISTA sequence; with (20a)-(20d) as written, the algorithm is a different (and possibly non-convergent) procedure. This is fixable by replacing (20a) and (20d) with the correct FISTA formulas, and the numerical code may already do so, but the paper as printed does not prove its central accelerated-gradient claim.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies linear-quadratic generalized Nash equilibrium problems with shared affine constraints and a merely monotone pseudogradient. Its central result, Lemma 3.1, shows that variational generalized Nash equilibria of the game coincide with the zero-value solutions of the convex QP (10) built from the joint KKT conditions, provided that QP is feasible. From this reformulation the authors derive a Tikhonov-regularized QP whose solution is an O(rho)-approximated GNE (Prop. 4.1), an accelerated proximal-point scheme and an accelerated projected-gradient scheme with claimed O(1/k^2) last-iterate guarantees (Props. 4.3 and 4.5), and a lower-dimensional dual-only QP when the pseudogradient is invertible (Lemma 5.1). Numerical experiments compare the proposed solvers with extragradient baselines on random instances and on a game-theoretic MPC example.","tokens_in":1507,"tokens_out":5940,"duration_ms":210089,"significance":"The QP equivalence for non-potential monotone games is a clean and, to my knowledge, novel structural result; if it holds, it turns v-GNE computation for this class into convex QP solving with off-the-shelf software. The paper ships reproducible code, and the regularized bound and reduced QP are useful additions. The headline O(1/k^2) last-iterate claim for merely monotone games, however, is not established for the algorithm actually printed in Section 4.3 because the gradient formula is incorrect; this is a local but load-bearing defect. The reader's stress-test concern therefore lands in part: Eq. (20a) is genuinely wrong, while Eq. (20d) is a typesetting ambiguity rather than a substantive error. The central Lemma 3.1 and Props. 4.1 and 4.3 appear sound.","major_comments":[{"comment":"The smooth part of the objective in (18) is g(x, lambda, nu) = x^T F_s x + f^T x + b^T lambda + e^T nu, whose gradient is (2 F_s x + f, b, e). Equation (20a) prints [f + (F_s(bar{x}_k))^T, b^T, e^T]^T, which misses the factor 2 and is not dimensionally consistent. Since Proposition 4.5 is justified by invoking [4, Thm. 4.4] for the algorithm 'above', that theorem is applied to a different iteration than the one printed. This invalidates Proposition 4.5 as stated. The fix is local: replace (20a) with the exact gradient evaluated at y_k = (bar{x}_k, bar{lambda}_k, bar{nu}_k) and state that the step (20b)-(20c) is the proximal map of the indicator of the feasible set; the O(1/k^2) bound of [4] then applies to the corrected algorithm.","section":"§4.3, Eq. (20a)"},{"comment":"The formula for theta_{k+1} is typeset ambiguously; as rendered it can be read as theta_k (sqrt(theta_k^2 + 4 - theta_k))/2, which is not the positive root of (19a). If the intended expression is theta_k (sqrt(theta_k^2 + 4) - theta_k)/2, then it is correct and is the reciprocal-parameter form of the standard FISTA sequence, but it must be rewritten unambiguously so the reader can verify that the O(1/k^2) rate applies.","section":"§4.3, Eq. (20d)"}],"minor_comments":[{"comment":"The displayed simplification G^T E^T M^{-T} (E G E^T) M^{-1} E G = G^T E^T M^{-T} M M^{-1} E G = G^T E^T M^{-1} E G uses M^{-T} M = I, which is not valid for the nonsymmetric matrix M = E F^{-1} E^T allowed by Lemma 5.1. The desired cancellation can be obtained by regrouping as G^T E^T M^{-T} (E G E^T M^{-1}) E G = G^T E^T M^{-T} E G; please correct the algebra.","section":"Appendix A.1"},{"comment":"Please state the hypotheses of [11, Thm. 2.2] being used (proper closed convex objective, attainment of the minimum, and the exactness of the prox subproblems) and verify them for the function Psi in (18).","section":"§4.2, Prop. 4.3"},{"comment":"The proof invokes necessity of the joint KKT conditions (8) without stating a constraint qualification. For polyhedral X the required CQ holds, but it should be stated explicitly so the equivalence is self-contained.","section":"§3, Lemma 3.1"},{"comment":"The notation in (20a) is inconsistent with (20b): the gradient is written in terms of bar{x}_k while the extrapolated variable y_k is a triple (bar{x}_k, bar{lambda}_k, bar{nu}_k); please make the dependency on y_k explicit.","section":"§4.3, Eq. (20)"}],"recommendation":"major_revision","confidential_remarks":"The main issue is confined to Section 4.3 and is readily fixable; the numerical code may already implement the correct projected-gradient update, and the authors should confirm consistency between the printed algorithm and the code. The rest of the central derivation, including Lemma 3.1, Prop. 4.1, and Prop. 4.3, appears sound. With a careful revision that corrects Eq. (20a), disambiguates Eq. (20d), and states the supporting theorem hypotheses, I would be willing to accept the paper. I would not recommend reject, because the central equivalence is a genuine contribution and the defects are local rather than conceptual."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Hi [Colleague],\n\nThe short version: the core QP reformulation is sound and worth knowing, but the accelerated projected-gradient part is wrong as printed. The stress-test note has it right. Proposition 4.5 is not proved for the algorithm actually written.\n\nWhat's genuinely new: Lemma 3.1 turns v-GNE computation for merely-monotone LQ-GNEPs into a convex QP with zero optimal value iff a v-GNE exists. The proof via the identity (12) is clean and self-contained. Proposition 4.1's linear-in-rho suboptimality bound is straightforward and correct. The dual-only QP in Lemma 5.1 is a nice reduction when F is invertible, and the numerical section is honest, with code available. If the APG formulas are fixed, the O(1/k^2) last-iterate guarantee is a real improvement over the O(1/sqrt(k)) ergodic bound for extragradient.\n\nSoft spots, in order of size. First, the novelty claim is over-stated. The complementarity-minimization reformulation of a monotone LCP is classical, and QP (10) is essentially that reformulation written for the joint KKT system. The paper should cite that line of work and position itself as applying it to GNEPs, not as inventing it. The O(1/k^2) last-iterate results and the reduced dual QP still appear new, but the boundary needs to be drawn honestly. Second, Section 4.3 is wrong as printed: (20a) drops the factor 2 in the gradient of x^T F_s x, and (20d) is not the FISTA theta-update. As a result, Proposition 4.5 is unproven for the algorithm displayed. This is fixable—replace those two lines with the correct FISTA updates—but it must be fixed, not just acknowledged. Third, Proposition 4.3 cites Guler's theorem without restating or verifying its hypotheses; re-checking that the problem satisfies them should take one paragraph.\n\nWho this is for: anyone working on GNEP solution methods or game-theoretic MPC. The reformulation enables off-the-shelf QP solvers and the numerics suggest real speedups. I'd send it to a serious referee, with the expectation of a revision that corrects the APG section and tightens the novelty claims.","headline":"The QP reformulation is real and useful—most of the paper is sound—but the accelerated projected-gradient section is wrong as printed and needs correction before the O(1/k^2) claim can stand.","tokens_in":17708,"tokens_out":3137,"would_cite":true,"duration_ms":28535,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C20","90C33","91A10","49J40"],"pacs":[],"model":"deepseek-v4-flash","headline":"For monotone linear-quadratic games, finding a variational Nash equilibrium reduces to solving a single convex quadratic program.","keywords":["generalized Nash equilibrium","variational equilibrium","linear-quadratic game","quadratic programming reformulation","monotone pseudogradient","accelerated proximal point","accelerated projected gradient","game-theoretic model predictive control"],"falsifier":"Run the accelerated projected-gradient method (20) on a small merely-monotone LQ-GNEP whose QP subproblems are solved to machine precision, and record λ_k^T(b - A x_k) at each iterate; if the gap does not decay as O(1/$k^{2}$) over a thousand iterations, the rate claim in Proposition 4.5 is refuted. A second check: solve QP (10) for a game with Fs singular and compare its optimal value against a v-GNE found by an independent method; any positive optimal value paired with an existing v-GNE would contradict Lemma 3.1.","tokens_in":16610,"feed_emoji":"🎯","tokens_out":6787,"duration_ms":51988,"temperature":0.7,"pith_summary":"This paper proves that, for an N-player game in which each player minimizes a convex quadratic cost subject to shared affine constraints, computing a variational generalized Nash equilibrium (v-GNE) is equivalent to solving one convex quadratic program built from the players' joint Karush–Kuhn–Tucker conditions. The equivalence holds under only mere monotonicity of the game's pseudogradient, not the strong monotonicity or potential-game structure that earlier reformulations required. Once the game is rewritten as a QP, off-the-shelf convex QP solvers, Tikhonov regularization, accelerated proximal-point iterations, and accelerated projected-gradient methods all become applicable, and the paper derives an O(1/$k^{2}$) last-iterate approximation guarantee for the latter two. A reader should care because this turns a class of equilibrium problems previously solved only by variational-inequality methods into a standard convex optimization task, with concrete gains in game-theoretic model predictive control.","feed_headline":"Monotone Nash games collapse into a single quadratic program","feed_subtitle":"Variational equilibria of linear-quadratic games now come with O(1/k^2) accelerated solvers and off-the-shelf QP code.","key_machinery":"The load-bearing object is the quadratic program (10) in primal-dual variables, whose Hessian is the symmetric part Fs = (F + F^T)/2 of the pseudogradient matrix F and whose objective equals the complementarity slackness λ^T(b - Ax). Monotonicity of the pseudogradient is exactly the statement Fs ⪰ 0, which makes the QP convex; the Frank–Wolfe theorem then guarantees the optimal value is attained. Lemma 3.3 supplies the bridge from optimization to game theory: any feasible point of (10) whose objective value is at most ε is an ε-approximated v-GNE. The accelerated methods then run on this QP, with each subproblem a strongly convex QP that existing active-set solvers can handle.","core_discovery":"The central discovery is Lemma 3.1: under the monotonicity assumption, the feasibility set of the QP (10) is exactly the set of triples (x, λ, ν) satisfying the joint KKT conditions except for complementarity slackness, and the QP's objective coincides with the complementarity gap λ^T(b - Ax) on that set. Consequently the QP is convex, its optimal value is finite and nonnegative whenever feasible, and a point x* is a v-GNE if and only if the optimal value of (10) is zero at some minimizer (x*, λ*, ν*). From this equivalence the paper obtains an ε-suboptimality bound for the regularized QP, proves that the accelerated proximal-point and accelerated projected-gradient methods produce O(1/$k^{2}$)-approximated v-GNEs at the k-th iterate under mere monotonicity, and derives a reduced dual-only QP of dimension m when the pseudogradient matrix is invertible. Numerical experiments on random instances and a two-agent game-theoretic MPC problem show the reformulation reduces solution time substantially compared with extragradient baselines.","pith_inferences":["The equivalence suggests that steady progress in convex QP solvers automatically transfers to equilibrium computation; any improvement in warm-starting or active-set technology for convex QPs should directly speed up v-GNE solving.","The objective value of (10) is a natural, cheaply computable certificate of suboptimality, so real-time game-theoretic MPC could stop as soon as the complementarity gap falls below a safe threshold.","The dual-only reduction for invertible F hints at a decentralized scheme where players communicate only their dual multipliers; whether such a scheme preserves the O(1/k^2) rate is an open question the paper does not address.","If the pseudogradient is only monotone on the feasible set rather than globally, the same construction may still yield a convex QP on that set, but the equivalence and rate proofs would need reworking."],"forward_implications":["Every monotone LQ-GNEP with shared affine constraints becomes solvable by any convex QP solver, including warm-started active-set and interior-point methods, without special-purpose equilibrium code.","Tikhonov regularization of the QP yields an ε-approximated v-GNE with ε = O(ρ), and as ρ → 0 the regularized solution converges to the minimum-norm v-GNE.","The accelerated proximal-point and accelerated projected-gradient schemes guarantee the k-th iterate is an O(1/k^2)-approximated v-GNE, improving on the O(1/√k) ergodic guarantee of extragradient methods and needing no compactness of the feasible set.","When the pseudogradient matrix is invertible, the problem reduces to a convex QP in the inequality multipliers alone, of dimension m, with x and ν recovered by explicit formulas.","The same QP framework applies to game-theoretic model predictive control, where the per-step game can be solved faster than by extragradient baselines."],"supporting_citations":[{"why":"Supplies the variational-inequality characterization of v-GNEs and existence results used to interpret the QP reformulation.","marker":"[8]"},{"why":"Provides the Frank–Wolfe theorem used to show the convex QP attains its minimum when feasible.","marker":"[3]"},{"why":"Defines generalized Nash equilibria, v-GNEs, and ε-approximated equilibria, the solution concepts throughout the paper.","marker":"[7]"},{"why":"Gives the joint KKT conditions for convex programs that form the starting point of the reformulation.","marker":"[21]"},{"why":"Provides the accelerated proximal-point method whose O(1/k^2) rate is transferred to the QP.","marker":"[11]"},{"why":"Provides the accelerated projected-gradient (FISTA-type) rate used for Proposition 4.5.","marker":"[4]"},{"why":"The extragradient method used as the main baseline in the numerical comparison.","marker":"[14]"},{"why":"Gives the ergodic O(1/k) bound for the extragradient baseline, setting the comparison level.","marker":"[18]"}],"fun_headline_variants":["Monotone Nash games collapse into one convex QP","QP reformulation speeds up monotone Nash solving","Accelerated QP method for generalized Nash equilibria","One QP solves monotone linear-quadratic Nash games","O(1/k^2) convergence for Nash equilibrium via QP"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument collapses if the game's pseudogradient is not monotone, because the symmetric part Fs would not be positive semidefinite and QP (10) would no longer be the convex problem whose zero optimal value signals a v-GNE.","fun_headline_variants_meta":{"raw":{"variants":["Monotone Nash games collapse into one convex QP","QP reformulation speeds up monotone Nash solving","Accelerated QP method for generalized Nash equilibria","One QP solves monotone linear-quadratic Nash games","O(1/k^2) convergence for Nash equilibrium via QP"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000285,"raw_usage":{"total_tokens":1688,"prompt_tokens":964,"completion_tokens":724,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":580,"completion_tokens_details":{"reasoning_tokens":641}},"tokens_in":580,"tokens_out":724,"duration_ms":6124,"temperature":1.0,"reasoning_tokens":641,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T06:03:21.385044+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the accelerated projected-gradient method (20) on a small merely-monotone LQ-GNEP whose QP subproblems are solved to machine precision, and record λ_k^T(b - A x_k) at each iterate; if the gap does not decay as O(1/$k^{2}$) over a thousand iterations, the rate claim in Proposition 4.5 is refuted. A second check: solve QP (10) for a game with Fs singular and compare its optimal value against a v-GNE found by an independent method; any positive optimal value paired with an existing v-GNE would contradict Lemma 3.1.","supporting_citations":[{"cited_title":"Bazaraa, H.D","cited_arxiv_id":null,"evidence_quote":"Provides the Frank–Wolfe theorem used to show the convex QP attains its minimum when feasible."},{"cited_title":"Facchinei and C","cited_arxiv_id":null,"evidence_quote":"Defines generalized Nash equilibria, v-GNEs, and ε-approximated equilibria, the solution concepts throughout the paper."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the accelerated proximal-point method whose O(1/k^2) rate is transferred to the QP."},{"cited_title":"Korpelevich","cited_arxiv_id":null,"evidence_quote":"The extragradient method used as the main baseline in the numerical comparison."},{"cited_title":"Nemirovski","cited_arxiv_id":null,"evidence_quote":"Gives the ergodic O(1/k) bound for the extragradient baseline, setting the comparison level."}],"review_version":1}