{"id":"d4fe3f4f-2981-42a5-87fe-e95297847209","arxiv_id":"1908.02458","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"A projected subgradient algorithm for leader-follower network aggregative games with stochastic communication and activeness is claimed to converge to the unique equilibrium, but the proof has critical flaws.","lead":"One leader and many followers play a cost-minimizing game, and followers only sometimes transmit to or update with their neighbors. The paper proposes a simple update rule and claims it always settles at the game's unique equilibrium, but the proof contains several serious gaps.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proof of Theorem 1 reverses two step-size inequalities: (23) uses the maximum step size in a negative strong-convexity term where the minimum is required, and (26) bounds a sum of non-increasing step sizes by the interval's smallest step size, so the negativity of T_3 and T_4 in (27) is not…","rationale":"The reader's verdict is REJECT with high confidence, and my analysis supports that rejection. The reader's weakest_assumption points to Assumption 5 and its use in (23); I agree that Assumption 5 is fragile, but the more specific and decisive problem is that the proof misapplies the assumption, producing reversed inequalities regardless of whether Assumption 5 itself holds. The error in (26) is independent of the truth of Assumption 5: even with κ finite, a sum of non-increasing step sizes over a leader interval cannot be replaced by the smallest step size times the interval length when an upper bound is needed. This directly breaks the positivity of T_3 and T_4 in (27) and thus the supermartingale argument for Theorem 1. The additional flaw in Proposition 1 (from ∑α_k E||∇x_k||^2 < ∞ and ∑α_k = ∞ to E||∇x_k||^2 → 0) is a separate unsupported inference, reinforcing the rejection. I therefore see no reason to change the reader's verdict, and I would keep it at REJECT because the main convergence theorem is not established. My agreement is partial because the reader centered the concern on the assumption itself rather than on the concrete reversed inequalities in (23) and (26), though the overall conclusion coincides.","tokens_in":13937,"tokens_out":19347,"duration_ms":200308,"concrete_test":"Take a one-leader/two-follower instance with step sizes α_1^k = 1/(k+1), α_2^k = 2/(k+1), α_0^k = 1/(k+1), so Assumption 5 holds with κ=2. For a leader interval K'_j = {1,...,10}, compute the actual sum S_true = ∑_{k=1}^{10} α^k with α^k = max(α_1^k,α_2^k,α_0^k) = 2/(k+1), which is about 4.6, and compare it with the proof's replacement α^{10}·10 = (2/11)·10 ≈ 1.82. Since S_true exceeds the replacement by a factor greater than 2, the inequality (26) is reversed. Re-derive (27) using the correct sum; the coefficient of ||∇y^{k_L_j}||^2 becomes C0 - (S_true/α^{k_L_j}) ¯L instead of C0 - κ(k_L_j-k_L_{j-1})¯L, and one can choose C0 > κ¯K¯L yet still have a positive coefficient, so the stated sufficient condition does not guarantee negativity of T_3.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central convergence proof of Theorem 1 is not valid as written because Assumption 5 is applied with reversed inequalities in two load-bearing places. First, in (23), the agent step size α_n^k is replaced by the maximum step size α^k = max(α_1^k,...,α_N^k,α_0^k) in the negative strong-convexity term: the proof writes -α_n^k e Ψ ≤ -α^k C_n e ||∇x_n||^2 + α^k κ L ||∇x_n||(...). Since α_n^k ≤ α^k, the correct upper bound requires -α_n^k C_n ≤ -α^k C_n / κ, not -α^k C_n; as written the inequality has the wrong sign on the dominant term. Second, in (26), the sum over the leader interval ∑_{k'∈K'_j} α^{k'} ||∇y^{k_L_j}||^2 is bounded by α^{k_L_j}(k_L_j-k_L_{j-1}) ||∇y^{k_L_j}||^2. Because the step sizes are non-increasing (Assumption 4), α^{k'} ≥ α^{k_L_j} for every k' in the interval, so the replacement under-estimates the true positive term. These two errors are what produce the displayed coefficients (C0 - κ(k_L_j-k_L_{j-1})¯L) and (δC_n - κ¯L) in (27); without them the supermartingale inequality (20)+(27) does not follow, and the almost sure convergence claim is unsupported. In addition, Proposition 1 uses the invalid implication that ∑α_k E||∇x_k||^2 < ∞ and ∑α_k = ∞ force E||∇x_k||^2 → 0, which is false (e.g., α_k=1/k and E||∇x_k||^2=1 on a sparse subsequence). The mean-square claim is therefore also unsupported.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper considers a leader-follower network aggregative game in which each follower's cost depends on the leader's strategy and the aggregated strategies of its neighbors, while the leader's cost depends on the aggregate of all followers' strategies. Communication among followers and the activeness of each follower are stochastic and may be dependent; the leader wakes up and updates only at an infinite set of iterations with bounded gaps. The authors propose a distributed projected subgradient algorithm and claim that it converges almost surely to the unique generalized Nash equilibrium under strong convexity, Lipschitz subgradients, and an assumption bounding the ratio of the largest to the smallest step size. They also claim mean-square convergence and include simulations for a small-cell power allocation example.","tokens_in":14397,"tokens_out":6465,"duration_ms":71727,"significance":"The model is well motivated and, if the convergence results were correct, the paper would be a useful contribution: it extends network aggregative games to a leader-follower setting with stochastic communication and activeness, and it offers a distributed subgradient scheme with a clean algorithmic statement. The simulation example is appropriate for the application domain. However, the central convergence proof contains two sign errors in the treatment of the step sizes, and the mean-square claim rests on an invalid subsequence argument. As written, the main theorem is not established, so the paper does not yet provide the claimed justification for the algorithm.","major_comments":[{"comment":"The replacement of the follower step size by the maximum step size is invalid. Since α_n^k ≤ α^k, the inequality -α_n^k C_n ||∇x_n^k||^2 ≤ -α^k C_n ||∇x_n^k||^2 has the wrong sign; the left-hand side is actually larger. Assumption 5 gives α_n^k ≥ α^k/κ, so the correct negative coefficient is at most -(α^k/κ) C_n, not -α^k C_n. Consequently the positivity of T_4 in Eq. (27) does not follow from the stated supermartingale inequality.","section":"Section IV, Theorem 1 proof, Eq. (23)"},{"comment":"The bound for the leader term reverses the monotonicity of the step sizes. For each k' in K'_j, ||∇y^{k_L_j}||^2 is constant, but since the step sizes are non-increasing, α^{k'} ≥ α^{k_L_j}; hence ∑_{k'∈K'_j} α^{k'} ||∇y^{k_L_j}||^2 is at least α^{k_L_j}(k_L_j-k_L_{j-1})||∇y^{k_L_j}||^2, not at most. This makes the displayed coefficient (C0 - κ(k_L_j-k_L_{j-1}) \\bar L) in T_3 unjustified, and the supermartingale inequality obtained by combining (20) and (27) is not established.","section":"Section IV, Theorem 1 proof, Eq. (26)"},{"comment":"The proof claims that ∑ α^k E||∇x^k||^2 < ∞ together with ∑ α^k = ∞ forces E||∇x^k||^2 → 0. This implication is false in general; for example, one can take α_k = 1/k and E||∇x^k||^2 = 1 on a sufficiently sparse subsequence. No L1 or uniform-integrability argument is supplied from the almost-sure convergence, so the mean-square convergence claim is unsupported.","section":"Section IV, Proposition 1"},{"comment":"The matrices V^{k'} are not symmetric, and the Perron-Frobenius theorem controls the spectral radius from row sums, not the quadratic form v^T V v. Since v^T V v = v^T ((V+V^T)/2) v, the bound \\bar L ||v||^2 would require an eigenvalue estimate on the symmetric part of V, not on V itself. The current justification for v^{k'⊤} V^{k'} v^{k'} ≤ \\bar L ||v^{k'}||^2 is therefore incomplete and is also used in the uniqueness argument.","section":"Section IV, Eq. (26) and Proposition 2"}],"minor_comments":[{"comment":"“almost surly” should be “almost surely”.","section":"Theorem 1 statement"},{"comment":"The proof refers to “Assumption 6” when the intended reference is Assumption 1.","section":"Section IV, proof around Eq. (21)"},{"comment":"The sentence “Also, based on Lemma 3 we have ∑ T_j^1 < ∞” appears to refer to T_j^2; Lemma 3 bounds the communication-error terms, not the already-bounded square-step-size sum T_j^1.","section":"Section IV, after Eq. (27)"},{"comment":"“e.i.” should be “i.e.”.","section":"Appendix B"}],"recommendation":"reject","confidential_remarks":"The two sign errors in the proof of Theorem 1 are not cosmetic: they invalidate the main convergence theorem as written. The mean-square claim is also not justified. If the authors can repair the step-size treatment, strengthen the Perron-Frobenius argument, and provide a genuine L1 argument for Proposition 1, a substantially revised version could be reconsidered."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nThe model here is genuinely new—a leader-follower network aggregative game with stochastic communication and activeness, where the leader wakes intermittently. That part I like. But I read the proof carefully, and the reader's worst concerns are correct: Theorem 1's convergence argument is not valid as written.\n\nThe paper does several things well. The problem setup is natural and relevant; gossip protocols are recovered as a special case; the simulations are clear; and the literature review is honest. The novelty claims are fair.\n\nThe proof, however, reverses two inequalities. In (23), α_n^k is replaced by the maximum α^k inside a negative strong-convexity term. Since α_n^k ≤ α^k, the inequality −α_n^k C_n ≤ −α^k C_n is wrong; a valid bound would use −(α^k/κ)C_n, the min step size. In (26), the sum over the leader interval is bounded by using α^{k_L_j}, the smallest step size in the interval, yet the sequence is non-increasing, so every term is larger. That under-estimates a positive term when an upper bound is required. These two errors are what make the coefficients in (27) look positive. Without them, the supermartingale lemma does not apply, and the almost-sure convergence claim is unsupported.\n\nProposition 1 is also unsupported. From ∑ α_k E‖∇x_k‖² < ∞ and ∑ α_k = ∞, one cannot conclude E‖∇x_k‖² → 0; sparse subsequence counterexamples are standard. And almost-sure convergence alone does not imply mean-square convergence.\n\nThese are load-bearing, not cosmetic. The assumptions are also strong (Assumption 5 in particular), but the broken proof is the main issue.\n\nFor whom is this paper? For researchers in distributed Nash/GNE seeking, the problem formulation is worth knowing, but the convergence guarantees should not be cited. A corrected proof—possibly with stronger step-size assumptions—could make this a publishable piece. As submitted, it is not there.\n\nMy recommendation: if you're handling it, send it to peer review rather than desk-rejecting, because the model is novel and an expert might see whether the proof can be repaired. But the referee should be asked to focus on the proof, and I'd expect a reject decision as is.\n\nBest,\n[Your name]","headline":"A novel leader-follower NAG model with an unsound convergence proof—two reversed inequalities and an invalid mean-square step.","tokens_in":14861,"tokens_out":5838,"would_cite":false,"duration_ms":57676,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91A10","91A43","91A65","68W15"],"pacs":[],"model":"deepseek-v4-flash","headline":"A distributed projected subgradient algorithm converges almost surely and in mean square to the unique generalized Nash equilibrium of a leader-follower network aggregative game, despite stochastic communication, stochastic activeness…","keywords":["leader-follower game","network aggregative game","generalized Nash equilibrium","projected subgradient method","stochastic communication","stochastic activeness","almost sure convergence","mean square convergence"],"falsifier":"Run Algorithm 1 on a small network (two followers and one leader) with quadratic strongly convex costs satisfying the theorem's thresholds, gossip communication, and a leader that wakes every $\\bar{K}$ iterations, and check whether the squared distance to the computed GNE goes to zero; a persistent nonzero error or convergence to a different point would falsify the claim.","tokens_in":13747,"feed_emoji":"📡","tokens_out":9480,"duration_ms":94002,"temperature":0.7,"pith_summary":"This paper studies a non-cooperative game with one leader and many followers. Each follower's cost depends on its own strategy, a weighted aggregate of its neighbors' strategies, and the leader's strategy; the leader's cost depends on its strategy and a weighted aggregate of all followers' strategies. The authors propose a fully distributed projected subgradient algorithm in which each follower updates only when randomly active and uses only information delivered over randomly established links, while the leader wakes up, updates, and broadcasts at time instants separated by at most $\\bar{K}$ iterations. The central claim is that, under strong convexity and Lipschitz assumptions and a uniform bound on the ratio of step sizes, Algorithm 1 converges to the unique generalized Nash equilibrium in both almost sure and mean square senses. A sympathetic reading would summarize the contribution as: stochastic communication and sleeping agents degrade the convergence rate but not the convergence itself, provided each agent's cost curvature is large enough relative to the coupling.","feed_headline":"Simple update rule reaches unique equilibrium in leader-follower games","feed_subtitle":"Proof covers random agent communication and activeness, plus a leader that wakes occasionally.","key_machinery":"The central object is Algorithm 1: the projected subgradient recursions $x_n^{k+1} = \\Pi_{X_n}(x_n^k - e_n^k \\alpha_n^k d_n(x_n^k, \\tilde{\\sigma}_n^k, y^k))$ for followers and $y^{k+1} = \\Pi_Y(y^k - \\alpha_0^k d_0(y^k, \\sigma_0^k))$ for the leader at wake-up instants. The random binary variables $e_n^k$ (activeness) and $l_{n,m}^k$ (message delivery) realize the stochastic communication model. The argument's load-bearing step is the almost-supermartingale inequality (27), which decomposes the expected squared error accumulated over one leader sleep period into two summable perturbation terms and two non-positive quadratic terms; the non-positivity is certified by combining the lower bounds $\\gamma$ and $\\delta$ from Assumption 2, the step-size ratio bound $\\kappa$ from Assumption 5, and the spectral-radius bound for the nonnegative coupling matrix $V^{k'}$.","core_discovery":"Theorem 1 states that if the strong-convexity constants from Assumption 1 satisfy $C_n > \\frac{\\kappa}{\\delta}\\bar{L}$ for every follower and $C_0 > \\kappa\\bar{K}\\bar{L}$ for the leader, with $\\bar{L} = \\max(2L, L_0)$, then Algorithm 1 converges almost surely to the unique GNE point. Proposition 1 adds mean-square convergence, and Proposition 2 establishes that the equilibrium is unique under the same conditions. In the paper's own terms, the randomness in who communicates and who updates is handled as a perturbation that is summable with respect to the step sizes, so the expected squared distance to equilibrium is driven to zero by the two negative terms $T_3^j$ and $T_4^j$ in inequality (27).","pith_inferences":["A natural extension the authors do not pursue is relaxing Assumption 5, the uniform step-size ratio; if some agents' step sizes decay much faster than others', the cross-term bound in (23) can fail, and the conjecture is that convergence may be lost.","The proof only uses lower bounds $\\gamma$ and $\\delta$ on communication and activeness probabilities, so the same guarantee should hold for any scheduling mechanism—energy-aware sleeping, deterministic duty cycles, or randomized gossip—that respects those bounds.","In the small-cell power-control application, the threshold condition translates into a quantitative rule: a macrocell base station that updates less often needs a stronger penalty curvature or a smaller maximum sleep gap; the paper's simulation uses one operating point but does not map out this trade-off."],"forward_implications":["A network of selfish cost-minimizing agents can reach the unique equilibrium with a simple gradient-following rule, without solving best-response problems at each step.","Gossip-style communication, in which at most one neighboring pair exchanges information per iteration, is a special case of the model and inherits the convergence guarantee.","The leader can sleep for arbitrarily long but bounded stretches; followers continue updating with the last broadcast value and the system still converges.","The mean-square convergence result means that independent runs of the algorithm will concentrate around the equilibrium, not merely converge on a set of probability one.","The explicit thresholds $C_n > \\kappa\\bar{L}/\\delta$ and $C_0 > \\kappa\\bar{K}\\bar{L}$ give quantitative guidance for when unreliable communication is tolerable."],"supporting_citations":[{"why":"Supplies the existence and uniqueness theorem for the equilibrium, used in Proposition 2 to conclude the GNE is unique.","marker":"[24]"},{"why":"Supplies the almost-supermartingale convergence lemma that converts inequality (27) into almost sure convergence of Algorithm 1.","marker":"[25]"},{"why":"Gives the fixed-point characterization of the projection update used to initialize the squared-error recursion in the proof of Theorem 1.","marker":"[26]"},{"why":"Provides the spectral-radius bound used to bound the cross-coupling matrix by $\\bar{L} = \\max(2L, L_0)$.","marker":"[27]"}],"fun_headline_variants":["Random communication yields unique equilibrium in leader-follower games","Leader-follower game converges despite random communication and activeness","Unique generalized Nash equilibrium reached even with stochastic interactions","Subgradient algorithm converges to unique equilibrium despite random agent updates","Stochastic communication and activeness lead to unique equilibrium in games"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof requires that at every iteration the ratio of the largest to the smallest step size across all followers and the leader is bounded by one fixed constant; if some agents' step sizes shrink at very different rates, the negative terms that drive convergence can no longer be shown non-positive.","fun_headline_variants_meta":{"raw":{"variants":["Random communication yields unique equilibrium in leader-follower games","Leader-follower game converges despite random communication and activeness","Unique generalized Nash equilibrium reached even with stochastic interactions","Subgradient algorithm converges to unique equilibrium despite random agent updates","Stochastic communication and activeness lead to unique equilibrium in games"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001595,"raw_usage":{"total_tokens":6313,"prompt_tokens":857,"completion_tokens":5456,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":473,"completion_tokens_details":{"reasoning_tokens":5376}},"tokens_in":473,"tokens_out":5456,"duration_ms":33695,"temperature":1.0,"reasoning_tokens":5376,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:45:05.058061+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 1 on a small network (two followers and one leader) with quadratic strongly convex costs satisfying the theorem's thresholds, gossip communication, and a leader that wakes every $\\bar{K}$ iterations, and check whether the squared distance to the computed GNE goes to zero; a persistent nonzero error or convergence to a different point would falsify the claim.","supporting_citations":[{"cited_title":"Existence and uniqueness of equilibrium points for concave n-person games,","cited_arxiv_id":null,"evidence_quote":"Supplies the existence and uniqueness theorem for the equilibrium, used in Proposition 2 to conclude the GNE is unique."},{"cited_title":"A convergence theorem for non negative almost supermartingales and some applications,","cited_arxiv_id":null,"evidence_quote":"Supplies the almost-supermartingale convergence lemma that converts inequality (27) into almost sure convergence of Algorithm 1."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the fixed-point characterization of the projection update used to initialize the squared-error recursion in the proof of Theorem 1."},{"cited_title":"A note on the proof of the perron- frobenius theorem,","cited_arxiv_id":null,"evidence_quote":"Provides the spectral-radius bound used to bound the cross-coupling matrix by $\\bar{L} = \\max(2L, L_0)$."}],"review_version":1}