{"id":"d9e5baea-1e2e-4c8a-8a5e-89fad9b89f3b","arxiv_id":"2501.12256","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A bounded-update-rate extremum seeking controller drives players in quadratic noncooperative games to a small neighborhood of the Nash equilibrium, with local exponential convergence shown via Lie-bracket averaging.","lead":"Players in a game who know only their own payoff can still be driven close to a Nash equilibrium, according to this control-theory paper. It combines two existing ideas, extremum seeking and bounded-update-rate control, and proves local convergence for quadratic games.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The proof of Theorem 5.1 applies the Lie-bracket averaging bound for all t>=0, but the cited averaging theorem only supports a finite-horizon O(1/tildeomega) estimate; the infinite-horizon bound in Eq. (5.18) is not established.","rationale":"I read the paper in good faith and checked the main algebraic steps. The sign of the Lie-bracket calculation is consistent: [b1,b2] = -alpha k (partial J_i/partial theta_i) e_i, and the subsequent gradient-ascent form (4.13) is correct. The Gershgorin argument in Section 5 is valid under strict diagonal dominance, and Assumption 2.2 is an explicit scope limitation rather than an internal inconsistency. The most load-bearing weakness is the uniform-in-time use of the Lie-bracket approximation theorem. The reader noted in the rationale that the uniform-in-time bound is 'lightly justified,' but selected Assumption 2.2 as the formal weakest assumption. I think the averaging step is more central: if (5.18) only holds on compact intervals, then the conclusion of Theorem 5.1 overreaches. This is fixable with a Lyapunov-based averaging argument, so I recommend conditional acceptance rather than rejection. With the missing infinite-horizon justification supplied, the central claim would be substantially supported.","tokens_in":13012,"tokens_out":10799,"duration_ms":113277,"concrete_test":"Analytically verify whether the original Gurvits-Li Theorem 2.1, as reproduced in Appendix Theorem 7.1, actually provides a uniform-in-time approximation bound on [0,infinity). If it does not, re-derive (5.18) by a two-time-scale Lyapunov argument: use exponential stability of the linear averaged system (4.13) to construct a Lyapunov function for the exact system and bound the Lie-bracket remainder by C/tildeomega with C independent of t. If such a uniform bound cannot be produced, Theorem 5.1 must be weakened to a finite-horizon statement, and the 'for all t>=0' claim in (5.1) is unsupported.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The paper's central result, Theorem 5.1, is a uniform-in-time bound: ||theta(t)-theta*|| <= M exp(-mt)||theta(0)-theta*|| + O(1/tildeomega) for all t>=0. The only place where the actual system is connected to the exponentially stable average is Eq. (5.18), which asserts ||theta(t)-thetabar(t)|| <= O(1/tildeomega), for all t>=0, citing [5, Thm. 2.1] (Appendix Thm. 7.1). The Appendix theorem, as stated, says only 'for sufficiently small epsilon, the trajectory ... is bounded by the solution ... in the sense that ||x-z|| <= O(epsilon)' with no time-uniformity qualification. Standard averaging theorems of this type provide O(epsilon) agreement on compact time intervals [0,T]; without an additional argument (e.g., combining exponential stability of (4.13) with a converse Lyapunov function and a perturbation bound on the remainder), the approximation error need not remain O(1/tildeomega) for unbounded t. Since (5.20) relies on this inequality for all t>=0, the theorem's conclusion is not established by the proof as written. This is a proof gap rather than a demonstrated counterexample, but it is load-bearing because both the exponential transient and the residual-set characterization in (5.1) depend on this inequality holding for every t>=0.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies N-player quadratic noncooperative games with unknown payoff functions and proposes a distributed Nash equilibrium seeking law θ̇_i(t)=√α_i ω_i cos(ω_i t−k_i J_i(θ(t))), in which each player uses only its own payoff evaluation. Under assumptions of a strictly diagonally dominant interaction matrix and commensurable distinct rational probing frequencies, the authors rewrite the closed loop in input-affine form and compute its Lie-bracket average system (4.13). Using Gershgorin discs and a quadratic Lyapunov function, they show that the averaged error system is exponentially stable, and Theorem 5.1 concludes that the actual actions converge to an O(1/ω̃) neighborhood of the unique Nash equilibrium with an exponentially decaying transient. A four-firm oligopoly simulation illustrates the result.","tokens_in":13312,"tokens_out":13338,"duration_ms":129573,"significance":"If the proof is completed, this is a useful contribution: it extends Lie-bracket extremum seeking to noncooperative games with provably bounded update rates, removes the need for payoff-model knowledge, and gives an explicit parameter-free characterization of the residual set. The algebraic core is transparent: the trigonometric identity reduction to input-affine form, the cancellation of cross-player terms under Assumption 3.1, and the Gershgorin/Lyapunov argument for the average system are all checkable by hand. The paper also correctly highlights that the residual size is O(1/ω̃), independent of the probing-signal amplitudes. The central concern is that the proof of the main theorem uses an infinite-horizon averaging estimate that the cited theorem does not provide.","major_comments":[{"comment":"The proof of Theorem 5.1 asserts in Eq. (5.18) that ||θ(t)−θ̄(t)|| ≤ O(1/ω̃) for all t ≥ 0, citing [5, Thm. 2.1] (restated as Appendix Theorem 7.1). As stated, Theorem 7.1 gives only an O(ε) bound without specifying a time horizon; standard versions of this theorem provide the bound on compact intervals [0,T], and the Appendix does not contain the additional assumptions or argument needed for a uniform-in-time bound. Since Eq. (5.20) and therefore the main claim (5.1) use (5.18) at arbitrarily large t, this is a load-bearing proof gap. Please either cite a theorem that directly gives the infinite-horizon bound or add the standard averaging/ultimate-boundedness argument, for example by combining exponential stability of (4.13) with a converse Lyapunov function and a perturbation estimate for the periodically perturbed flow.","section":"Theorem 5.1, Eq. (5.18), Appendix Theorem 7.1"},{"comment":"The stated selection rule for the Lie-bracket coefficients is incorrect. For the inputs u(t)=sin(nt) and cos(nt), the integral in (4.2) with k=l (sin-sin or cos-cos) vanishes over a full period, whereas the mixed case k≠l gives ±1/(2n_j) when n_i=n_j. Equation (4.3) states the opposite. The final average system (4.13) has the correct sign if the mixed-case coefficient with the ordering used in (4.1)-(4.2) is adopted, but the written derivation is not coherent. Please correct (4.3) and clarify the index convention in (4.1)-(4.2).","section":"Section 4, Eq. (4.3)"}],"minor_comments":[{"comment":"The third payoff in the simulation is labelled J2(t) but is defined with H3, h3, and c3; it should be labelled J3(t).","section":"Section 6, Eqs. (6.1)-(6.4)"},{"comment":"The line numbered (6.14) is an empty dangling equation before the definition of H4 and should be removed.","section":"Section 6, after Eq. (6.13)"},{"comment":"Please fix typographical errors: 'Mardsden' in [9] should be 'Marsden', 'nooncoperative' in Section 6 should be 'noncooperative', and 'right-hand size' near Eq. (5.13) should be 'right-hand side'.","section":"References and text"}],"recommendation":"major_revision","confidential_remarks":"The uniform-in-time averaging gap in the proof of Theorem 5.1 is the decisive issue; I would not accept the paper before it is fixed or replaced by a correct infinite-horizon argument. The incorrect selection rule in Eq. (4.3) also needs correction, though it appears to be a fixable notational/substantive slip. The paper is a reasonable fit for the journal and the contribution is solid if the proof is completed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nQuick take: this paper does something new—it ports the Scheinker–Krstić bounded-update-rate extremum seeking idea into multi-player Nash seeking, using Lie-bracket averaging to show local practical convergence for quadratic games. The result is credible in spirit and the writing is clear. The central proof, however, has a gap that needs to be fixed before I'd call the theorem fully proved.\n\nWhat's genuinely good: the setup is clean. Each player runs θ̇_i = √α_i ω_i cos(ω_i t − k_i J_i(θ)), which keeps update rates bounded by √α_iω_i times a cosine—so the bounded-rate feature is real and not an afterthought. The Lie-bracket computation is done carefully, and with distinct rational frequencies the cross-terms vanish, giving the averaged system θ̇̄ = (1/2)AK(Hθ̄ + h). Under strict diagonal dominance the Gershgorin argument puts the eigenvalues in the left half plane, and Lyapunov gives exponential stability of the average. The O(1/ω̃) residual is not fitted; it comes from averaging theory. Simulation on a four-firm oligopoly reproduces the expected behavior. No fabricated numerics, no hidden parameters.\n\nThe soft spot the referee will hit immediately is Eq. (5.18). The paper asserts ∥θ(t)−θ̄(t)∥ ≤ O(1/ω̃) for all t ≥ 0, citing Gurvits–Li Theorem 2.1 (Appendix Theorem 7.1). But that theorem, as stated, only gives O(ε) approximation—it does not state uniform-in-time validity. Standard averaging theorems give O(ε) on compact intervals unless you add exponential stability of the average plus a converse Lyapunov argument to push the bound to infinite horizon. The authors skip that step. Since Theorem 5.1's both exponential transient and ultimate residual rely on (5.18) holding for every t, this is load-bearing, not cosmetic. I don't think it's wrong—the claim is probably true with a suitable stability estimate—but the proof as written does not establish it.\n\nThe other limitation is scope: Assumption 2.2 (strict diagonal dominance of H) is strong. It is stated transparently, so it's not a hidden flaw, but it means the result covers a fairly narrow class of quadratic games. The paper presents it as inherited from the prior NES literature, which is fair but worth flagging in review.\n\nWho's this for? People working on extremum seeking, model-free optimization, or distributed Nash seeking. It deserves a serious referee. If I were handling it, I'd send it out and ask the authors to either prove the uniform-in-time averaging bound or restate the theorem with a finite-horizon practical convergence statement, which would still be an honest and useful result.\n\nRecommended for review.","headline":"New bounded-update-rate Nash seeking scheme with a clean Lie-bracket derivation, but the uniform-in-time averaging bound in Theorem 5.1 is not justified by the cited theorem.","tokens_in":13847,"tokens_out":2789,"would_cite":true,"duration_ms":28636,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91A10","91A80","93D05","93C40"],"pacs":[],"model":"deepseek-v4-flash","headline":"A distributed, bounded-rate update law drives players of a quadratic noncooperative game to a small neighborhood of the Nash equilibrium even though no player knows any payoff function.","keywords":["Nash equilibrium seeking","noncooperative games","extremum seeking","bounded update rates","Lie-bracket approximation","quadratic payoff games","distributed control","pseudo-gradient"],"falsifier":"Numerically simulate the four-firm oligopoly of Section 6 for several values of the common frequency parameter $\\tilde{\\omega}$ (say 30, 300, and 3000) and measure the ultimate radius $\\limsup_{t\\to\\infty}\\|\\theta(t)-\\theta^*\\|$; Theorem 5.1 predicts it shrinks like $O(1/\\tilde{\\omega})$, so a roughly tenfold reduction when $\\tilde{\\omega}$ is increased tenfold confirms the scaling, while a flat or divergent deviation falsifies it. A second test is to keep $H$ invertible but non-diagonally dominant while preserving a unique Nash equilibrium and observe whether convergence to the predicted neighborhood fails.","tokens_in":12821,"feed_emoji":"🎮","tokens_out":11814,"duration_ms":104068,"temperature":0.7,"pith_summary":"This paper establishes that in an $N$-player quadratic noncooperative game, players who know nothing about the payoff functions—not even the analytic form of their own payoff—can drive their actions to a small neighborhood of the unique Nash equilibrium using a distributed update law with a provably bounded update rate. The law is $\\dot{\\theta}_i = \\sqrt{\\alpha_i}\\,\\omega_i \\cos(\\omega_i t - k_i J_i(\\theta))$, so the measured payoff enters only inside the cosine and the rate of every player's action is capped by $\\sqrt{\\alpha_i}\\omega_i$. Because the payoff appears in the phase of the dither, standard averaging does not apply; the analysis instead uses a Lie-bracket approximation whose averaged dynamics is exactly the pseudo-gradient flow, which converges exponentially when the interaction matrix is strictly diagonally dominant. The paper quantifies the residual set around the equilibrium as $O(1/\\tilde{\\omega})$, independent of the probing amplitudes, and demonstrates the behavior on a four-firm oligopoly simulation.","feed_headline":"Model-free players reach Nash equilibrium at bounded update rates","feed_subtitle":"Sampling only its own payoff, each player converges exponentially close to equilibrium; the miss shrinks with probing frequency.","key_machinery":"The load-bearing object is the Lie bracket (commutator) of the two vector fields that appear once the update law is written in input-affine form, $\\dot{\\theta}_i = \\sqrt{\\alpha_i}\\cos(k_iJ_i(\\theta))\\sqrt{\\omega_i}\\cos(\\omega_i t) + \\sqrt{\\alpha_i}\\sin(k_iJ_i(\\theta))\\sqrt{\\omega_i}\\sin(\\omega_i t)$. For player $i$, the bracket of these fields evaluates to $-\\alpha_i k_i \\frac{\\partial J_i}{\\partial \\theta_i} e_i$, so the averaged (Lie-bracket) system is exactly the pseudo-gradient ascent $\\dot{\\bar{\\theta}} = \\tfrac12 A K \\nabla J(\\bar{\\theta}) = \\tfrac12 A K (H\\bar{\\theta} + h)$. Gershgorin's circle theorem then places the eigenvalues of $\\tfrac12 A K H$ in the left half-plane whenever $H$ is strictly diagonally dominant, turning the averaged error dynamics into an exponentially stable linear system and producing the bound in Theorem 5.1. The bounded update rate is carried by the cosine/sine argument itself: since $|\\dot{\\theta}_i| \\le \\sqrt{\\alpha_i}\\omega_i$, the probing amplitudes no longer inflate the update rate.","core_discovery":"The paper's central claim is Theorem 5.1: for a quadratic game with unknown payoffs satisfying Assumptions 2.1, 2.2, and 3.1, and for sufficiently small initial error and sufficiently large common frequency parameter $\\tilde{\\omega}$, the distributed update law makes the action vector satisfy $\\|\\theta(t)-\\theta^*\\| \\le M e^{-mt}\\|\\theta(0)-\\theta^*\\| + O(1/\\tilde{\\omega})$ for all $t\\ge 0$, with computable constants $M,m>0$. The exponential term comes from the Lie-bracket-averaged error system $\\dot{\\tilde{\\theta}} = \\tfrac12 A K H \\tilde{\\theta}$, whose system matrix is Hurwitz by Gershgorin's theorem under strict diagonal dominance of $H$; the $O(1/\\tilde{\\omega})$ term comes from the Lie-bracket approximation theorem for nonholonomic systems. In effect, each player measures only its own scalar payoff, never sees the other players' actions or payoffs, and yet the collective action vector converges to a residual neighborhood of the unique Nash equilibrium whose radius shrinks as the probing frequency grows.","pith_inferences":["(Editorial extension) The same Lie-bracket construction should carry over to smooth non-quadratic payoffs by linearizing around the equilibrium: whenever the Hessian of the pseudo-gradient at $\\theta^*$ is strictly diagonally dominant, the quadratic game of this paper acts as the local surrogate and the same exponential-plus-residual bound should hold.","(Editorial extension) The amplitude-independence of the residual suggests a practical tuning recipe the paper does not spell out: use small probing amplitudes to respect actuator limits and large frequencies to shrink the residual, instead of trading off amplitude against accuracy as in classical extremum seeking.","(Editorial extension) The unicycle connection mentioned in the conclusion implies a testable extension to mobile robot teams: the same bounded-rate bracketing could generate distributed source-seeking or formation-seeking laws with constant forward speed, which is not analyzed here.","(Editorial extension) If some players are stubborn or deceptive and do not run the seeking law, the pseudo-gradient structure suggests convergence should survive as long as the effective interaction matrix seen by the seeking players remains strictly diagonally dominant; this conjecture is not established in the paper."],"forward_implications":["Any player with access only to its own scalar payoff can participate in a noncooperative game and reach near-Nash behavior online, without model identification, communication, or knowledge of other players' actions and payoffs.","The residual neighborhood of the Nash equilibrium can be made arbitrarily small by increasing the common frequency parameter $\\tilde{\\omega}$, and unlike classical extremum seeking this residual is independent of the probing amplitudes, so accuracy and boundedness of update rates are decoupled.","The exponential rate $m$ and overshoot constant $M$ in Theorem 5.1 are computable from the Lyapunov solution, giving quantitative guidance for tuning the gains $\\alpha_i,k_i$ and the frequencies.","Because the analysis is local, it provides a baseline for semi-global or nonlocal bounded-rate Nash seeking: the guaranteed basin is a neighborhood of the equilibrium whose size is governed by the game's curvature and the control gains, and leaving that neighborhood is not covered by the claim."],"supporting_citations":[{"why":"Supplies the Lie-bracket approximation theorem for extremum seeking systems and the multi-agent ES setup with unbounded update rates that this paper adapts to bounded rates.","marker":"[2]"},{"why":"Establishes the model-free Nash equilibrium seeking approach with sinusoidal extremum seeking that this paper extends, and provides the strict diagonal dominance assumption and the oligopoly simulation parameters.","marker":"[4]"},{"why":"Provides the averaging theorem for nonholonomic systems used in the appendix, which yields the O(1/\\tilde{\\omega}) approximation error between the actual and averaged trajectories.","marker":"[5]"},{"why":"Supplies Gershgorin's circle theorem, used to prove that the averaged error matrix has eigenvalues in the left half-plane under diagonal dominance.","marker":"[6]"},{"why":"Provides the Lyapunov equation, the Rayleigh-Ritz inequality, and the comparison lemma used to derive the exponential decay in Theorem 5.1.","marker":"[7]"},{"why":"Introduces extremum seeking with bounded update rates, the law whose cosine structure is carried into the Nash equilibrium seeking design.","marker":"[20]"}],"fun_headline_variants":["Bounded-rate probing converges to Nash equilibrium","Model-free players hit Nash via Lie-bracket search","Payoff-sampling players converge to Nash with bounded updates","Distributed extremum seeking reaches Nash without models"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the interaction matrix $H$ is strictly diagonally dominant—each player's own quadratic coefficient outweighs the sum of the cross-influences of all other players on that player's marginal payoff—so Gershgorin's theorem forces the averaged error system into the left half-plane; the result also needs a sufficiently small initial action error and a sufficiently high probing frequency, and if the diagonal dominance fails, the exponential bound collapses.","fun_headline_variants_meta":{"raw":{"variants":["Bounded-rate probing converges to Nash equilibrium","Model-free players hit Nash via Lie-bracket search","Payoff-sampling players converge to Nash with bounded updates","Distributed extremum seeking reaches Nash without models"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000577,"raw_usage":{"total_tokens":2683,"prompt_tokens":869,"completion_tokens":1814,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":485,"completion_tokens_details":{"reasoning_tokens":1753}},"tokens_in":485,"tokens_out":1814,"duration_ms":14494,"temperature":1.0,"reasoning_tokens":1753,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T17:21:33.142734+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Numerically simulate the four-firm oligopoly of Section 6 for several values of the common frequency parameter $\\tilde{\\omega}$ (say 30, 300, and 3000) and measure the ultimate radius $\\limsup_{t\\to\\infty}\\|\\theta(t)-\\theta^*\\|$; Theorem 5.1 predicts it shrinks like $O(1/\\tilde{\\omega})$, so a roughly tenfold reduction when $\\tilde{\\omega}$ is increased tenfold confirms the scaling, while a flat or divergent deviation falsifies it. A second test is to keep $H$ invertible but non-diagonally dominant while preserving a unique Nash equilibrium and observe whether convergence to the predicted neighborhood fails.","supporting_citations":[{"cited_title":"D¨ urr, M","cited_arxiv_id":null,"evidence_quote":"Supplies the Lie-bracket approximation theorem for extremum seeking systems and the multi-agent ES setup with unbounded update rates that this paper adapts to bounded rates."},{"cited_title":"Frihauf, M","cited_arxiv_id":null,"evidence_quote":"Establishes the model-free Nash equilibrium seeking approach with sinusoidal extremum seeking that this paper extends, and provides the strict diagonal dominance assumption and the oligopoly simulation parameters."},{"cited_title":"Gurvits and Z","cited_arxiv_id":null,"evidence_quote":"Provides the averaging theorem for nonholonomic systems used in the appendix, which yields the O(1/\\tilde{\\omega}) approximation error between the actual and averaged trajectories."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies Gershgorin's circle theorem, used to prove that the averaged error matrix has eigenvalues in the left half-plane under diagonal dominance."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the Lyapunov equation, the Rayleigh-Ritz inequality, and the comparison lemma used to derive the exponential decay in Theorem 5.1."},{"cited_title":"Scheinker and M","cited_arxiv_id":null,"evidence_quote":"Introduces extremum seeking with bounded update rates, the law whose cosine structure is carried into the Nash equilibrium seeking design."}],"review_version":1}