{"id":"f6f4825c-9c28-4915-aca3-d00704e2b0c7","arxiv_id":"2509.08161","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":4,"one_line_summary":"A first-order Lagrangian penalty method is claimed to reach an ε-stationary multi-follower Stackelberg equilibrium in O(k²ε^{-6-α}) gradient evaluations.","lead":"This paper proposes an algorithm for Stackelberg games where one leader faces multiple followers, using only first-order gradients. It claims the first proof of convergence to an approximate equilibrium, but the proof has a gap that affects the stated rate.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 5.5's contraction step conflates the surrogate \\tilde L with the true Lagrangian L: gradient descent on \\tilde L does not converge to y^*_\\lambda, so the E1 bound and the O(k^2 ε^{-6-α}) rate are not established.","rationale":"The reader is right that the convergence proof is not sound, but the most load-bearing gap is different from the one highlighted. The E2/M_{z,t} objection depends on whether the black-box solver gives O(1/M) or O(1/\\sqrt{M}) gradient norm; the text's formal condition is consistent with O(1/M), so that line is not decisive. Independently, Lemma 5.5's contraction inequality is false as stated: the inner GD minimizes \\tilde L, not L, and no term accounts for the drift between their minimizers. This drift is at least of order \\|z-y^*\\| and enters E1 with a \\lambda_t^2 factor, so without it the summability argument for E1 collapses. I would keep the REJECT verdict; the concrete check above decides whether the rate survives after repair.","tokens_in":19258,"tokens_out":30984,"duration_ms":316372,"concrete_test":"Re-derive the first display in the proof of Lemma 5.5 using the actual surrogate \\tilde L: call \\bar y_{t+1} = \\arg\\min_y \\tilde L_{\\lambda_t}(x_t,\\cdot,z_{t+1}) and prove \\|\\bar y_{t+1}-y^*_{\\lambda_t}(x_t)\\| \\le (2\\sqrt{k}\\ell_{g,1}/\\mu_g)\\|z_{t+1}-y^*(x_t)\\| (or a similar bound). Insert this source term into the recursion of Lemma 5.5 and re-check whether \\sum_t \\lambda_t^2\\|y_{t+1}-y^*_\\lambda\\|^2 remains O(1) with M_{y,t}=O(\\log t), M_{z,t}=O(k^2 t^{2+\\alpha/2}), \\lambda_t=t^\\rho, \\alpha/2-\\epsilon'=\\rho-1. If the sum diverges, Theorem 5.1 fails; if bounded, the proof needs the added drift term and the stated rate likely survives.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Algorithm 1 (line 3) obtains y_{t+1} by minimizing the surrogate \\tilde L_{\\lambda_t}(x_t,\\cdot,z_{t+1}) = f(x_t,\\cdot) + \\lambda_t \\sum_i [g_i(x_t,\\cdot,z_{-i,t+1})-g_i(x_t,z_{t+1})]. The proof of Lemma 5.5 instead invokes strong convexity/smoothness of the true Lagrangian L_{\\lambda_t} to assert \\|y_{t+1}-y^*_{\\lambda_t}(x_t)\\| \\le (1-2\\mu_l/(\\mu_l+\\ell_l))^{M_{y,t}/2}\\|y_t-y^*_{\\lambda_t}(x_t)\\|. But GD on \\tilde L contracts to \\arg\\min_y \\tilde L, not to y^*_\\lambda. The mismatch \\|\\arg\\min_y \\tilde L - y^*_\\lambda\\| is never bounded; it is at least of order \\|z_{t+1}-y^*(x_t)\\| (by strong convexity and smoothness) and enters E1 in Corollary 5.4 multiplied by \\lambda_t^2. Without this drift term, the claimed summability of E1, hence the O(k^2 ε^{-6-α}) gradient-complexity bound, does not follow from the paper's equations.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies Stackelberg games with one leader and k followers in continuous action spaces. It proposes a bilevel reformulation and a Lagrangian-penalty single-level surrogate, then an algorithm (Algorithm 1) that alternates between (i) obtaining an approximate follower equilibrium z_{t+1} with an outer monotone-game solver, (ii) minimizing the surrogate Lagrangian by gradient descent, and (iii) updating the leader by an approximate gradient. The main claim, Theorem 5.1, is a convergence rate of O(k^2 ε^{-6-α}) gradient evaluations to an ε-stationary Stackelberg equilibrium for any α>0, under strong monotonicity and smoothness of the followers' subgame. The proof attempts to decompose the gradient error into three terms E1, E2, E3, control them via inner-loop iteration counts M_{y,t} and M_{z,t}, and then sum over T=O(ε^{-2}) outer iterations.","tokens_in":19654,"tokens_out":11430,"duration_ms":127508,"significance":"If the main theorem were correct, the contribution would be notable: it would provide the first fully first-order method for multi-follower Stackelberg games with a convergence guarantee, avoiding Hessian inversion and implicit differentiation, and the use of the Cai-Zheng monotone-game solver as a black box is a legitimate design choice. The paper also contains no fitted parameters and makes a genuine effort to provide full proofs in the appendix. However, the central convergence analysis has two load-bearing gaps: the bound on E2 is arithmetically inconsistent with the stated choice of M_{z,t}, and Lemma 5.5 contracts the wrong objective (the true Lagrangian instead of the surrogate actually minimized in the algorithm). These gaps invalidate Theorem 5.1 as stated. The result may be salvageable with a substantially different analysis and a weaker rate, but the claimed O(k^2 ε^{-6-α}) guarantee is not established.","major_comments":[{"comment":"The sufficient condition for E2 is derived incorrectly. Corollary 5.4 gives E2 = 2k^2 λ_t^2 ||z_{t+1}-y*(x_t)||^2. With λ_t = t^ρ and the manuscript's own inner-solver bound ||z-z*|| ≤ C_z/(μ_g √M_{z,t}), E2 ≤ const · k^2 t^{2ρ} C_z^2 / M_{z,t}. Requiring E2 ≤ t^{-(1+ε')} therefore needs M_{z,t} ≥ const · k^2 C_z^2 t^{2ρ+1+ε'}. Since the text states C_z = O(k), this is M_{z,t} ≥ O(k^4 t^{2ρ+1+ε'}). The paper instead states M_{z,t} ≥ C_z k t^{ρ+ε'+1}/μ_g and then sets M_{z,t}=O(k^2 t^{2+α/2}). With the paper's relation ρ = 1 + α/2 - ε', the correct exponent is 2ρ+1+ε' = 3 + α - ε', not 2+α/2, and the k-dependence is k^4, not k^2. Thus E2 is not summable under the stated inner-loop counts, and the total complexity O(k^2 ε^{-6-α}) does not follow. The text also alternates between ||Vz|| ≤ C_z/M and ||z-z*|| ≤ C_z/(μ√M); either convention preserves the mismatch.","section":"§5.2, 'Bounding E2' and Proof of Theorem 5.1"},{"comment":"Lemma 5.5 conflates the surrogate \\(\\tilde L\\) with the true Lagrangian \\(L\\). Algorithm 1 line 3 minimizes \\(\\tilde L_{\\lambda_t}(x_t,\\cdot,z_{t+1}) = f(x_t,\\cdot) + \\lambda_t \\sum_i [g_i(x_t,\\cdot,z_{-i,t+1}) - g_i(x_t,z_{t+1})]\\), where \\(z_{t+1}\\) is only an approximate follower equilibrium. The proof of Lemma 5.5, however, invokes strong convexity and smoothness of the true Lagrangian \\(L\\) and asserts a contraction of \\(y_{t+1}\\) to \\(y^*_{\\lambda_t}(x_t)\\). Gradient descent on \\(\\tilde L\\) contracts to \\(\\arg\\min_y \\tilde L\\), not to \\(y^*_{\\lambda_t}\\). The distance between these two minimizers depends on \\(\\|z_{t+1}-y^*(x_t)\\|\\), and this drift term is never bounded in Lemma 5.5. Since the drift enters E1 in Corollary 5.4 multiplied by \\(\\lambda_t^2\\), the claimed summability of E1, and hence the overall rate, is not established. This is a substantive gap, not a notational issue","section":"§5.2, Lemma 5.5 and Algorithm 1, line 3"},{"comment":"The statement '... ≤ C_y = O(t^{1-ρ})' is internally inconsistent for ρ>1: the left-hand side is positive, while O(t^{1-ρ}) tends to 0. In the proof, B_t is O(t^{-ρ}), so its partial sum from u=1 to t is O(1) (bounded by ζ(ρ)), not O(t^{1-ρ}). As written, Lemma 5.5 does not provide the uniform constant needed to choose M_{y,t}=O(log t). This is likely repairable, but it is another load-bearing error in the proof of the E1 bound.","section":"Lemma 5.5"}],"minor_comments":[{"comment":"The follower suboptimality condition writes 'g_i(x,y) ≤ min_{y'∈Y_i} g(x,y'_i,y_{-i})+ε'; the argument of g on the left should be (x,y_i,y_{-i}), not (x,y).","section":"Definition 2.4"},{"comment":"Line 3 mentions an accuracy parameter ε_{y,t} that is never defined or used in the analysis; the proof only tracks M_{y,t}. Either define ε_{y,t} and relate it to M_{y,t}, or remove it.","section":"Algorithm 1"},{"comment":"The inner-solver rate is quoted inconsistently: one sentence gives ||Vz(x,z_{M_z,t})|| ≤ C_z/M_{z,t}, and the next uses ||z-z*|| ≤ C_z/(μ_g√M_{z,t}). Please state the exact Cai-Zheng last-iterate rate in gradient norm and derive the distance bound consistently.","section":"§5.2, 'Bounding E2'"},{"comment":"The notation alternates between y, y_t, y_{t+1}, z_t, z_{t+1}, and the subscripting in the surrogate \\(\\tilde L\\) is easy to confuse with the true Lagrangian \\(L\\). A table of notation or a displayed definition immediately before Lemma 5.5 would help.","section":"Throughout"}],"recommendation":"reject","confidential_remarks":"The Lagrangian-reformulation idea is interesting and the paper addresses a relevant open computational problem. However, the two main proof gaps are not local typos: one invalidates the claimed inner-loop count for E2 and the other contracts the wrong objective. Even if the authors repair the E2 arithmetic, the convergence rate would degrade from O(k^2 ε^{-6-α}) to something like O(k^4 ε^{-(8+δ)}), and the \\(\\tilde L\\)-vs-\\(L\\) gap requires a new argument. I would be open to a substantially revised version with a corrected theorem, but the current manuscript does not establish its central claim."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague — the short version: this paper is right about the gap it targets, and the high-level approach is plausible, but the proof of the main theorem doesn't hold together. I agree with the reader's rejection.\n\nWhat's actually new: extending Kwon et al.'s first-order bilevel method from a single lower-level problem to a k-follower game. The Lagrangian reformulation is a natural step, and the algorithm itself is clean. The related work is honest, and the claim that existing multi-follower methods need Hessians is accurate. The paper is not setting up a strawman.\n\nNow the soft spots, and they are serious. First, the inner-loop count for the game solver is off. Corollary 5.4's E2 term is 2k^2 λ_t^2 ||z_{t+1} - y*||^2. With the Cai-Zheng bound — the paper is inconsistent about whether the rate is O(1/√M) or O(1/M) — the M_{z,t} stated in the proof sketch is too small to make E2 ≤ t^{-(1+ε')}. That alone kills the claimed O(k^2 ε^{-6-α}) rate.\n\nSecond, the stress-test note is right about Lemma 5.5. Algorithm 1 minimizes the surrogate \\tilde L — the Lagrangian with z_{t+1} in place of the equilibrium y^*(x) — but the contraction argument is for the true Lagrangian L. There is no bound on the distance between the minimizer of \\tilde L and y^*_λ. That drift enters E1 scaled by λ_t^2 and is left unaccounted. The lemma's recursive inequality therefore isn't about the iterates the algorithm actually computes.\n\nCredit where it's due: the reformulation is derived, not assumed, and the use of Cai-Zheng as a black box is externally grounded. The paper is not circular, and the authors aren't fudging. It's an honest attempt with a real missing piece in the analysis.\n\nWho's it for? Anyone working on first-order bilevel or Stackelberg methods. It would be a useful discussion paper for a reading group, but not a reliable result to cite. A corrected proof might salvage the rate; the gaps look fixable in principle, but they are not minor.\n\nRecommendation: send it to a serious referee. The problem matters, and the approach deserves careful scrutiny with a chance for revision. But my own verdict is that in its current form, the main theorem is unsupported.","headline":"The extension to multiple followers is a sensible idea, but the proof of the main rate has two load-bearing gaps; as written the central claim is not established.","tokens_in":20139,"tokens_out":7159,"would_cite":false,"duration_ms":69318,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91A65","90C30","90C33"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proposes the first fully first-order algorithm—using only gradient evaluations, never Hessians or matrix inverses—that provably finds an ε-stationary Stackelberg equilibrium when several followers play a strongly monotone game.","keywords":["Stackelberg games","multi-follower games","bilevel optimization","fully first-order method","Lagrangian reformulation","strongly monotone games","ε-stationary equilibrium","convergence rate"],"falsifier":"Fix a leader strategy x, choose a large λ, compute y*_λ(x) by high-precision gradient descent on L_λ, and compare ∇L*_λ(x) with the true leader gradient ∇F(x) obtained by solving the followers' game exactly. If the difference does not shrink like O(1/λ) as Lemma 4.2 predicts, the Lagrangian proxy fails. Alternatively, run Algorithm 1 on a known strongly monotone two-follower game and check whether empirical gradient-evaluation counts track ε^{-6}; a much faster or divergent growth would indicate the theorem's bound is loose or wrong.","tokens_in":19160,"feed_emoji":"♟️","tokens_out":12578,"duration_ms":126564,"temperature":0.7,"pith_summary":"Stackelberg games model a leader committing to a strategy before several followers play a game in response. Computing such equilibria normally requires second derivatives and matrix inversions of the followers' equilibrium map, or exact best responses. This paper claims the first algorithm for multiple followers that needs only first-order gradient evaluations and still comes with a convergence guarantee: it reaches an ε-stationary equilibrium in O(k^2 ε^{-6-α}) gradient evaluations for any α>0. The method converts the two-level problem into a single constrained optimization problem through a Lagrangian penalty, then alternates between gradient-descent approximation of the followers' equilibrium and gradient-descent updates of the leader's strategy, while growing the penalty parameters. If the claim holds, multi-follower Stackelberg problems become solvable where Hessian-based implicit differentiation is impractical.","feed_headline":"Gradient-only method provably solves multi-follower Stackelberg games","feed_subtitle":"No Hessians or matrix inverses: plain gradients find ε-stationary equilibria in multi-follower Stackelberg games.","key_machinery":"The load-bearing object is the Lagrangian L_λ(x,y)=f(x,y)+Σ_i λ_i(g_i(x,y_i,y*_{-i}(x))-g_i(x,y*(x))). It replaces the constraint that y be a Nash equilibrium of the followers' game with a weighted penalty. Because the followers' game is strongly monotone, L_λ is strongly convex in y for λ large enough, so gradient descent on y converges linearly. Its minimizer y*_λ(x) lies within O(1/λ) of the true follower equilibrium y*(x), and the gap between ∇L*_λ(x) and the true leader gradient ∇F(x) is O(k^2/λ). The algorithm grows λ over time so this finite-penalty error becomes summable, while inner-loop iteration counts control the other two error terms from approximating the followers' equilibrium","core_discovery":"The paper's central claim: a fully first-order method can find an ε-stationary Stackelberg equilibrium with one leader and k followers, if the followers' subgame is strongly monotone and smooth. The proof reformulates the bilevel problem as a single-level constrained program via the Lagrangian L_λ(x,y)=f(x,y)+Σ_i λ_i(g_i(x,y_i,y*_{-i}(x))-g_i(x,y*(x))), showing that as λ grows, the Lagrangian minimizer approaches y*(x) and its gradient approaches ∇F(x). Algorithm 1 alternates gradient-descent approximation of the followers' equilibrium, gradient-descent approximation of the Lagrangian minimizer, and leader updates using the Lagrangian gradient, with λ_t=t^ρ. The error splits into three terms","pith_inferences":["The O(ε^{-6-α}) rate looks conservative: the E1 term only needs O(log t) inner steps while the E2 term needs O(t^{2+α/2}), and the α-vs-ε' trade-off is an artifact of the proof's schedule. A tighter coupling may push the rate below ε^{-5}.","The method assumes exact gradient oracles for f and g_i. A stochastic variant with noisy or sampled gradients is the natural next step; the paper anticipates complexity blow-up, but variance-reduction techniques might control the inflation.","Because the followers' game must be strongly monotone, the method does not apply to games with multiple isolated equilibria or to weakly monotone subgames; a regularized or perturbed variant could broaden the class, paying a bias-complexity trade-off.","A practical test: on a smooth market-pricing or security game with k=2–5 followers, record gradient-evaluation counts versus ε; the observed power law can reveal whether the ε^{-6} factor is a real bottleneck or a proof artifact."],"forward_implications":["Hessian-free scalability: leader and follower strategy spaces can be high-dimensional because no Hessian or matrix inverse is ever formed; per-iteration work is a few gradient evaluations.","Approximate followers suffice: the leader can update even when followers' best responses are only approximated by gradient descent, so the method works when the lower-level game cannot be solved exactly.","First guarantee of its kind: for k>1 followers, this is the first convergence rate (O(k^2 ε^{-6-α})) with only first-order oracles, at quadratic cost in the number of followers.","Parameter-growth blueprint: the proof shows how to schedule penalty growth (λ_t=t^ρ, ρ>1) and inner-loop iterations so the cumulative gradient error stays finite and the outer loop needs only T=O(ε^{-2}) steps."],"supporting_citations":[{"why":"The single-follower fully first-order bilevel method whose Lagrangian/penalty reformulation this paper generalizes to k followers; its rate is the baseline to beat.","marker":"Kwon et al. [2023]"},{"why":"Black-box last-iterate convergence for smooth monotone games; supplies the inner-game solver and the O(1/T) rate used in the E2 error bound.","marker":"Cai and Zheng [2023]"},{"why":"Tight last-iterate rates for no-regret learning in multi-player games; cited by Algorithm 1 when approximating the followers' equilibrium.","marker":"Golowich et al. [2020]"},{"why":"Existing multi-follower Stackelberg solver using differential backward induction with second-order information; the contrast that motivates the first-order contribution.","marker":"Li et al. [2022]"},{"why":"Existing multi-follower Stackelberg method based on KKT differentiation and Hessian-based gradient descent; the approach this paper avoids.","marker":"Wang et al. [2022]"},{"why":"Standard variational-analysis results used to bound the Jacobian and its inverse, giving the invertibility and sensitivity estimates behind the implicit-function analysis.","marker":"Facchinei and Pang [2003]"},{"why":"First-order quadratic-penalty method for bilevel programs; the penalty-reformulation technique this paper adapts to the multi-follower setting.","marker":"Lu and Mei [2024]"}],"fun_headline_variants":["First-order-only method reaches Stackelberg equilibrium","No Hessian: gradient provable for multi-follower games","Gradient descent finds epsilon-stationary Stackelberg","Fully first-order algorithm for multi-follower Stackelberg","Guaranteed convergence without second-order info"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"The argument rests on the followers' subgame being strongly monotone for every leader strategy, which guarantees a unique, smoothly varying follower equilibrium; if that fails, the Lagrangian may not be strongly convex and the convergence proof no longer applies.","fun_headline_variants_meta":{"raw":{"variants":["First-order-only method reaches Stackelberg equilibrium","No Hessian: gradient provable for multi-follower games","Gradient descent finds epsilon-stationary Stackelberg","Fully first-order algorithm for multi-follower Stackelberg","Guaranteed convergence without second-order info"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000138,"raw_usage":{"total_tokens":941,"prompt_tokens":642,"completion_tokens":299,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":386,"completion_tokens_details":{"reasoning_tokens":221}},"tokens_in":386,"tokens_out":299,"duration_ms":4200,"temperature":1.0,"reasoning_tokens":221,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-04T21:09:36.041642+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Fix a leader strategy x, choose a large λ, compute y*_λ(x) by high-precision gradient descent on L_λ, and compare ∇L*_λ(x) with the true leader gradient ∇F(x) obtained by solving the followers' game exactly. If the difference does not shrink like O(1/λ) as Lemma 4.2 predicts, the Lagrangian proxy fails. Alternatively, run Algorithm 1 on a known strongly monotone two-follower game and check whether empirical gradient-evaluation counts track ε^{-6}; a much faster or divergent growth would indicate the theorem's bound is loose or wrong.","supporting_citations":[{"cited_title":"A fully first-order method for stochastic bilevel optimization","cited_arxiv_id":null,"evidence_quote":"The single-follower fully first-order bilevel method whose Lagrangian/penalty reformulation this paper generalizes to k followers; its rate is the baseline to beat."},{"cited_title":"Doubly optimal no-regret learning in monotone games","cited_arxiv_id":null,"evidence_quote":"Black-box last-iterate convergence for smooth monotone games; supplies the inner-game solver and the O(1/T) rate used in the E2 error bound."},{"cited_title":"Tight last-iterate convergence rates for no-regret learning in multi-player games","cited_arxiv_id":null,"evidence_quote":"Tight last-iterate rates for no-regret learning in multi-player games; cited by Algorithm 1 when approximating the followers' equilibrium."},{"cited_title":"Reiter, and Milind Tambe","cited_arxiv_id":null,"evidence_quote":"Existing multi-follower Stackelberg method based on KKT differentiation and Hessian-based gradient descent; the approach this paper avoids."},{"cited_title":"Finite--Dimensional Variational Inequalities and Complementarity Problems, volume 1 of Springer Series in Operations Research and Financial Engineering","cited_arxiv_id":null,"evidence_quote":"Standard variational-analysis results used to bound the Jacobian and its inverse, giving the invertibility and sensitivity estimates behind the implicit-function analysis."}],"review_version":1}