{"id":"e4def89e-75bc-4737-8e2a-d107bb63ac78","arxiv_id":"2507.11703","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A distributed extrapolation algorithm achieves geometric convergence O(exp{-k/(gamma^2 n^2)}) in restricted strongly monotone games and the first sublinear rate O(1/k^{1/2-epsilon}) for merely monotone games.","lead":"This paper proposes a distributed algorithm for finding Nash equilibria in convex games, where players only exchange information with nearby neighbors. The authors prove faster convergence rates than previous distributed methods, including the first rate guarantee for games with only a monotone structure.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Monotone-rate proof uses a telescoping identity that the stated λ_t violates; the required λ_t is the reciprocal.","rationale":"The most load-bearing concern is an internal inconsistency in the time-varying parameter choice, not the global-domain monotonicity assumption. Proposition 1's telescoping requires θ_t α_t λ_t = θ_{t−1} α_{t−1}, and the stated θ_t, α_t, λ_t fail this by a factor ((t+1)/t)^{2(a+b)}. Since the merely-monotone rate theorem is built on this identity, the O(1/k^{1/2−ε}) claim is currently unproven for the algorithm as written. The fix is simple (invert λ_t), and Theorem 2's constant-λ argument is untouched, so the paper's overall program remains plausible. The reader's CONDITIONAL verdict is therefore appropriate; my concern does not move the verdict. The reader correctly flagged parameter mismatches in Corollary 1 and the undefined g5, but the specific λ_t inversion is the step that actually breaks the proof. The global monotonicity assumption is explicit and self-acknowledged, so it is a limitation of scope rather than a flaw in the derivation.","tokens_in":20112,"tokens_out":34662,"duration_ms":337836,"concrete_test":"Evaluate the identity at t=1 for the stated parameters: θ_1 = (1/2)^b, α_1 = A/2^a, λ_1 = (1/2)^{a+b}; compare θ_1 α_1 λ_1 = A/2^{2(a+b)} with θ_0 α_0 = A. They differ by a factor 2^{2(a+b)}, confirming the violation. Then rerun the proof of Proposition 1 and Theorem 1 with λ_t = ((t+1)/t)^{a+b}; verify that Eq. (16) telescopes and that the inequalities leading to Eq. (27) hold. If the corrected λ yields the stated O(1/k^{1/2−ε}) gap bound, the concern is a typographical parameter inversion; if not, the monotone-rate claim lacks proof. Also check the simulation code to see whether the simulations used λ_t > 1 or the printed λ_t < 1.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of the merely-monotone rates (Theorem 1 and Corollary 1) rests on the telescoping identity θ_t α_t λ_t = θ_{t−1} α_{t−1} in Proposition 1. With the stated choices θ_t = (t+1)^{−b}, α_t = A(t+1)^{−a}, and λ_t = (t/(t+1))^{a+b}, the identity is false: θ_t α_t λ_t = A t^{a+b}/(t+1)^{2(a+b)} while θ_{t−1} α_{t−1} = A/t^{a+b}. The identity forces λ_t = ((t+1)/t)^{a+b} > 1, the reciprocal of the value stated in Theorem 1 and Corollary 1. Equation (16) of Proposition 1 and the subsequent telescoping in Lemma 3 and Theorem 1 depend directly on this identity, so the claimed O(1/k^{1/2−ε}) gap-rate theorem is unproven for the algorithm as specified. This is a parameter inversion and appears correctable, but it is load-bearing because the merely-monotone result is the paper's central novelty. Theorem 2 is unaffected since it uses constant λ = 1/c < 1. The reader's flagged assumption (monotonicity over R^n rather than Ω) is explicit, acknowledged, and narrows applicability, but it is not an internal inconsistency.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a distributed algorithm for Nash equilibrium seeking in convex games with merely monotone and restricted strongly monotone pseudo-gradients. The algorithm is an operator-extrapolation method with local communications over a fixed undirected graph. The central claims are a geometric rate O(exp{-k/(gamma^2 n^2)}) for restricted strongly monotone games and a sublinear rate O(1/k^{1/2-epsilon}) for the gap function in merely monotone games, both presented as improvements over prior distributed methods. The analysis is built on a telescoping-sum inequality in Proposition 1, with separate treatments for the two monotonicity cases.","tokens_in":20403,"tokens_out":10130,"duration_ms":96457,"significance":"If the results are correct, the monotone-rate guarantee would be the first distributed convergence-rate result for merely monotone games, and the geometric rate would improve the known dependence on the condition number and network size. The paper is also careful to state its assumptions and to provide full proofs, including the technical proposition omitted from the conference version. However, the correctness of the monotone-rate result currently rests on a parameter inversion in the telescoping identity, and the geometric-rate proof contains an undefined constant and a false displayed equality. These issues are fixable, but until they are resolved the main claims are not established as stated.","major_comments":[{"comment":"The stated parameter choice in Theorem 1, namely lambda_t = (t/(t+1))^{a+b}, does not satisfy the telescoping identity used in Proposition 1. The proof of Proposition 1 uses theta_{t+1} alpha_{t+1} lambda_{t+1} = theta_t alpha_t, and with theta_t = (t+1)^{-b}, alpha_t = A(t+1)^{-a}, lambda_t = (t/(t+1))^{a+b} one obtains theta_{t+1} alpha_{t+1} lambda_{t+1} = A(t+1)^{a+b}/(t+2)^{2(a+b)}, while theta_t alpha_t = A(t+1)^{-(a+b)}. The correct relation requires lambda_t = ((t+1)/t)^{a+b}, the reciprocal of the stated value. Since Eq. (16) and the subsequent telescoping argument in Proposition 1, Lemma 3, and Theorem 1 all depend on this identity, the claimed O(1/k^{1/2-epsilon}) gap-rate result is not proven for the algorithm as specified. This is a load-bearing error, though it appears correctable.","section":"Proposition 1 and Theorem 1 (Eq. (16), parameter choices)"},{"comment":"The parameter choices in Corollary 1 are internally inconsistent with the claimed rate. With alpha_k = A/(k+1)^{1/2+eps/2} and theta_t = 1/(t+1)^eps, the exponents are a = 1/2 + eps/2 and b = eps, so 1-a-b = 1/2 - 3eps/2, not 1/2 - eps as stated. To obtain the claimed exponent 1/2 - eps, one needs b = eps/2, i.e., theta_t = 1/(t+1)^{eps/2}. The stated theta_t gives a slower rate for any eps in (0,1/2), so the rate in the corollary does not follow from the stated parameters.","section":"Corollary 1 (parameter choice and rate)"},{"comment":"The displayed equality after '=' in the chain around Eq. (17) is incorrect: it writes the sum of squares as sum (||x_t - hat(x)_{t-1}|| - ||x_{t+1} - x_t||)^2, omitting the coefficients sqrt(theta_t L^2 alpha_t^2 lambda_t^2/(2 eta_t)) and sqrt(theta_t eta_t/2) that appear in the preceding expression. As printed, the equality is false. The subsequent lower bound only needs the sum to be nonnegative, so the proof can be repaired by inserting the missing coefficients, but the displayed line must be corrected.","section":"Proof of Proposition 1, Eq. (17) (completion of squares)"},{"comment":"The proof of Theorem 2 refers to the condition 'alpha <= min{g4, g5}' but the constant g5 is never defined. From the surrounding text, the needed bound appears to be alpha <= sqrt(7)/(8L), which is used to conclude L^2 alpha^2/(2(1-eta)) <= 1/16. The proof is incomplete without a definition of g5 (or an explicit statement of this bound).","section":"Proof of Theorem 2 (undefined constant g5)"},{"comment":"The result for the 'restricted strongly monotone' case assumes inequality (4) over the whole space R^n, not only over the joint action set Omega. This is explicitly acknowledged after Lemma 4, but it is a substantive limitation: the algorithm's estimates can leave Omega, so the proof genuinely needs the full-space condition. The paper should state this limitation in the abstract and in the comparison with prior distributed methods, since those methods may only require strong monotonicity on Omega; as presented, the claimed improvement over GRANE/DDP may not apply to games that are not monotone outside Omega.","section":"Assumption (4) and Lemma 4 (full-space monotonicity)"}],"minor_comments":[{"comment":"The definition of eta_t in the proof is ambiguous: 'eta_t = 1/2 (t+1)^{2a-2eps}' should read eta_t = 1/(2(t+1)^{2a-2eps}) to be consistent with the text.","section":"Section 4.1, proof of Theorem 1"},{"comment":"Appendix A states 'given that lambda_t = theta_{t-1} alpha_{t-1} / (theta_t alpha_t)', which contradicts the definition lambda_t = (t/(t+1))^{a+b} used in Theorem 1; the former is the reciprocal of the latter. This inconsistency is part of the parameter-inversion issue noted above and should be resolved.","section":"Appendix A"},{"comment":"The condition on A in Corollary 1, written as 'A <= 1/(2L) 1/sqrt(2)', is typeset ambiguously; the intended bound appears to be A <= 1/(2L sqrt(2)). Please clarify the notation.","section":"Corollary 1"},{"comment":"The paper defines L in (2) as a Lipschitz constant for the pseudo-gradient on the relevant domain, but later uses the same L for the Lipschitz constant of the augmented mapping in Lemma 1. This is consistent, but it would help to state explicitly that the same constant serves both purposes.","section":"General notation"}],"recommendation":"major_revision","confidential_remarks":"The paper addresses a meaningful problem and the algorithmic idea is interesting, but the current version contains several proof errors in the central claims, including a parameter inversion that breaks the telescoping identity for the monotone-rate result and an inconsistency in Corollary 1. These are correctable, and I do not see evidence of circularity or fitted constants, but the authors must fix the stated lambda_t, the theta_t in Corollary 1, the undefined g5, and the incorrect displayed equality in Proposition 1 before the results can be accepted. The full-space monotonicity assumption in (4) should also be prominently qualified in the final version."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The headline is that the advertised merely-monotone rate is not actually proven as the paper stands. I checked the stress-test concern: with θ_t = (t+1)^{-b}, α_t = A(t+1)^{-a}, and λ_t = (t/(t+1))^{a+b}, the identity θ_{t+1}α_{t+1}λ_{t+1} = θ_t α_t in Proposition 1 fails. The required λ_t is the reciprocal, ((t+1)/t)^{a+b}. Since Theorem 1 and Corollary 1 build directly on that identity, the O(1/k^{1/2−ε}) gap-function guarantee is unproven for the algorithm as specified. This is the paper's main novelty, so it is a load-bearing flaw, not a cosmetic typo. The restricted strongly monotone part is unaffected, because it uses constant λ and θ_t = c^t, and that part seems plausible.\n\nWhat is genuinely useful: ADM is a clean distributed adaptation of the centralized operator extrapolation in [5], with one operator evaluation and one projection per player per iteration. The claimed geometric rate O(exp{−k/(γ² n²)}) improves on the prior distributed rates O(exp{−k/(γ⁴ n³)}) and O(exp{−k/(γ⁶ n⁶)}), and the simulations are consistent with that ordering. The paper is also honest about the restricted-strong-monotonicity-over-R^n assumption: it is explicitly acknowledged after Lemma 4 and explained by the estimates leaving Ω. That narrowing is a real limitation, but it is not an internal inconsistency.\n\nOther soft spots are smaller. The proof of Proposition 1 contains a garbled completion-of-squares step, and the proof of Theorem 2 uses an undefined constant g5. These are likely fixable, but they make the dense proofs harder to verify. The numerical section is illustrative; no code or data is shipped. The comparison baselines are the authors' own prior algorithms, but those are separately published, so that is not a problem.\n\nBottom line: this deserves peer review, not desk rejection. The algorithmic idea is sensible, the literature is engaged, and the rate improvement is worth having if the proof can be repaired. But as submitted, the merely-monotone claim should not be certified. I would send it to referees with the expectation of major revision, and I would not cite the monotone-rate result in its current form.","headline":"The claimed merely-monotone rate is unproven as written — the stated λ_t violates the telescoping identity in Proposition 1 — but the restricted strongly monotone part and the algorithmic idea are solid enough to deserve peer review after a repair.","tokens_in":20933,"tokens_out":4969,"would_cite":false,"duration_ms":53529,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91A10","49J40","90C25","68W15"],"pacs":[],"model":"deepseek-v4-flash","headline":"A distributed gradient-extrapolation method reaches Nash equilibria at rate $O(\\exp\\{-k/(\\gamma^2 n^2)\\})$ and provides the first rate guarantee for merely monotone games.","keywords":["Nash equilibrium seeking","distributed optimization","monotone games","operator extrapolation","variational inequality","consensus","geometric convergence rate","gap function"],"falsifier":"Construct a two-player game with $\\Omega=[0,1]^2$ whose pseudo-gradient is strongly monotone on $\\Omega$ but not on all of $\\mathbb{R}^2$, initialize ADM with estimates outside $\\Omega$, and check whether the geometric rate of Corollary 2 still holds; a counterexample where the iterates stall or diverge would show that the whole-space assumption in Lemma 4 is essential.","tokens_in":19919,"feed_emoji":"🎯","tokens_out":11926,"duration_ms":127128,"temperature":0.7,"pith_summary":"This paper proposes a distributed algorithm, the Accelerated Direct Method (ADM), for computing Nash equilibria in convex games where players can only exchange information with neighbors over a connected communication graph. The authors claim that in games with a restricted strongly monotone pseudo-gradient, the squared distance to the equilibrium decays geometrically, at rate $O(\\exp\\{-k/(\\gamma^2 n^2)\\})$, improving on the previously known distributed rates. In merely monotone games, they prove the gap function at a weighted average of iterates decays as $O(1/k^{1/2-\\varepsilon})$, which they state is the first convergence-rate guarantee for distributed procedures in this class. The practical point is that a simple gradient extrapolation step, one projection per player per iteration, and one round of neighbor communication are enough to obtain these rates.","feed_headline":"Distributed algorithm beats prior Nash-seeking rates in monotone games","feed_subtitle":"Geometric rate O(exp{-k/(γ²n²)}) improves on prior distributed methods and gives a first rate for merely monotone games.","key_machinery":"The machinery is an extrapolated pseudo-gradient step combined with a consensus step: each player mixes neighbor estimates via the mixing matrix $W$, forming $\\hat{x}^k$, and then projects onto its own action set with the gradient extrapolation $\\nabla_i J_i(\\hat{x}_{(i)}^k) + \\lambda_k[\\nabla_i J_i(x_{(i)}^k) - \\nabla_i J_i(\\hat{x}_{(i)}^{k-1})]$. The proof decomposes every estimation matrix into its consensus part $x_{\\|}$ and disagreement part $x_{\\perp}$, and uses a weighted-energy inequality (Proposition 1) in which the mixing matrix's contraction constant $\\sigma$ controls the disagreement while a parameter-dependent potential controls the distance of the consensus to the equilibrium. In the strongly monotone case, choosing the weights $\\theta_t = c^t$ with $c>1$ yields a Lyapunov inequality that telescopes to the geometric rate; in the monotone case, time-varying weights and the gap function $g(y) = \\max_{x\\in\\Omega}\\langle F(x), y-x\\rangle$ give the sublinear rate on averaged iterates.","core_discovery":"The central claim is that the centralized operator extrapolation idea can be carried into a distributed setting without sacrificing its acceleration. Concretely, ADM's update $x_i^{k+1} = P_{\\Omega_i}\\{\\hat{x}_i^k - \\alpha_k[\\nabla_i J_i(\\hat{x}_{(i)}^k) + \\lambda_k(\\nabla_i J_i(x_{(i)}^k) - \\nabla_i J_i(\\hat{x}_{(i)}^{k-1}))]\\}$, with $\\hat{x}^k = W x^k$ the consensus mixing step, yields the geometric rate $\\|x_k - x^*\\|^2 = O(\\exp\\{-k/(\\gamma^2 n^2)\\})$ under restricted strong monotonicity, and the gap-function rate $g(\\bar{x}_k) = O(1/k^{1/2-\\varepsilon})$ under mere monotonicity. The authors compare the geometric rate favorably with GRANE's $O(\\exp\\{-k/(\\gamma^6 n^6)\\})$ and the direct distributed procedure's $O(\\exp\\{-k/(\\gamma^4 n^3)\\})$, and they note that their monotone result is the first distributed rate for that class. They also flag that, unlike the centralized case, both monotonicity assumptions are made over the whole space $\\mathbb{R}^n$ because players' estimates of joint actions need not lie in $\\Omega$.","pith_inferences":["If the whole-space monotonicity assumption is the bottleneck, adding a projection or clipping step that keeps estimates in a region where monotonicity is known could relax it, at the cost of some bias; the authors do not analyze this variant.","Because the exponential rate depends on $n^2$ and on $\\sigma$ through the mixing matrix, choosing a better-connected graph or a mixing matrix with smaller second-largest singular value should improve the constant; the paper does not explore this trade-off.","The $O(1/k^{1/2-\\varepsilon})$ gap-function rate leaves open whether matching lower bounds exist for distributed monotone games; if such lower bounds match, the method would be order-optimal.","The extrapolation step suggests a direct route to stochastic or asynchronous variants, since each player only needs its own gradient and neighbors' estimates; this is not studied in the paper."],"forward_implications":["In restricted strongly monotone games, ADM's squared error decays as $O(\\exp\\{-k/(\\gamma^2 n^2)\\})$, which improves on GRANE's $O(\\exp\\{-k/(\\gamma^6 n^6)\\})$ and the direct distributed procedure's $O(\\exp\\{-k/(\\gamma^4 n^3)\\})$ in both iteration count and dimension dependence.","In merely monotone games, the gap function at the averaged iterates decays as $O(1/k^{1/2-\\varepsilon})$ for any $\\varepsilon \\in (0,1/2)$, giving the first distributed convergence-rate guarantee for this class.","In merely monotone games, any limit point of the averaged iterates is a Nash equilibrium; in restricted strongly monotone games, the whole estimation matrix converges to the consensus matrix whose rows are the unique Nash equilibrium.","The acceleration does not come from extra oracle calls: each player performs one pseudo-gradient evaluation, one projection, and one round of neighbor communication per iteration.","The rates degrade as the condition number $\\gamma = L/\\mu$ grows, which the numerical experiments confirm."],"supporting_citations":[{"why":"Supplies the centralized operator extrapolation method whose update structure Algorithm 1 adapts to distributed settings.","marker":"[5]"},{"why":"Provides the centralized geometric-rate baseline $O(\\exp\\{-k/\\gamma^2\\})$ and the gap-function property used in Remark 2.","marker":"[10]"},{"why":"Gives the GRANE algorithm and its $O(\\exp\\{-k/(\\gamma^6 n^6)\\})$ rate, the main distributed comparison that ADM improves.","marker":"[22]"},{"why":"The fully-distributed proximal-point algorithm whose linear rate, together with [19], is the DDP baseline ADM improves.","marker":"[3]"},{"why":"The direct distributed procedure whose $O(\\exp\\{-k/(\\gamma^4 n^3)\\})$ rate is the second distributed comparison in Remark 4.","marker":"[19]"},{"why":"Establishes the $O(1/k)$ complexity of mirror-prox for monotone variational inequalities, the benchmark for the merely monotone result.","marker":"[9]"},{"why":"Provides the consensus contraction inequality (3) that controls disagreement in Proposition 1.","marker":"[12]"},{"why":"Establishes the equivalence between Nash equilibria and variational inequality solutions that underlies the whole approach.","marker":"[13]"}],"fun_headline_variants":["Distributed Nash seeking improves geometric rate in monotone games","First distributed rate for merely monotone Nash games","Distributed extrapolation yields faster Nash rates in monotone games","Geometric rate improved for distributed Nash seeking in monotone games"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proofs assume the players' payoff map's monotonicity holds everywhere in $\\mathbb{R}^n$, not only on the joint action set, because players' estimates of others' actions can leave that set; if monotonicity holds only on the action set, the stated rates are not established.","fun_headline_variants_meta":{"raw":{"variants":["Distributed Nash seeking improves geometric rate in monotone games","First distributed rate for merely monotone Nash games","Distributed extrapolation yields faster Nash rates in monotone games","Geometric rate improved for distributed Nash seeking in monotone games"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00046,"raw_usage":{"total_tokens":2296,"prompt_tokens":931,"completion_tokens":1365,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":547,"completion_tokens_details":{"reasoning_tokens":1298}},"tokens_in":547,"tokens_out":1365,"duration_ms":13198,"temperature":1.0,"reasoning_tokens":1298,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T17:05:59.453156+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a two-player game with $\\Omega=[0,1]^2$ whose pseudo-gradient is strongly monotone on $\\Omega$ but not on all of $\\mathbb{R}^2$, initialize ADM with estimates outside $\\Omega$, and check whether the geometric rate of Corollary 2 still holds; a counterexample where the iterates stall or diverge would show that the whole-space assumption in Lemma 4 is essential.","supporting_citations":[{"cited_title":"Kotsalis, G","cited_arxiv_id":null,"evidence_quote":"Supplies the centralized operator extrapolation method whose update structure Algorithm 1 adapts to distributed settings."},{"cited_title":"Nesterov and L","cited_arxiv_id":null,"evidence_quote":"Provides the centralized geometric-rate baseline $O(\\exp\\{-k/\\gamma^2\\})$ and the gap-function property used in Remark 2."},{"cited_title":"Tatarenko, W","cited_arxiv_id":null,"evidence_quote":"Gives the GRANE algorithm and its $O(\\exp\\{-k/(\\gamma^6 n^6)\\})$ rate, the main distributed comparison that ADM improves."},{"cited_title":"Bianchi, G","cited_arxiv_id":null,"evidence_quote":"The fully-distributed proximal-point algorithm whose linear rate, together with [19], is the DDP baseline ADM improves."},{"cited_title":"Tatarenko and A","cited_arxiv_id":null,"evidence_quote":"The direct distributed procedure whose $O(\\exp\\{-k/(\\gamma^4 n^3)\\})$ rate is the second distributed comparison in Remark 4."},{"cited_title":"Nemirovski","cited_arxiv_id":null,"evidence_quote":"Establishes the $O(1/k)$ complexity of mirror-prox for monotone variational inequalities, the benchmark for the merely monotone result."},{"cited_title":"Olshevsky and J","cited_arxiv_id":null,"evidence_quote":"Provides the consensus contraction inequality (3) that controls disagreement in Proposition 1."},{"cited_title":"Pang and F","cited_arxiv_id":null,"evidence_quote":"Establishes the equivalence between Nash equilibria and variational inequality solutions that underlies the whole approach."}],"review_version":1}