Pith. sign in

REVIEW 2 major objections 3 minor 28 references

Lie-Bracket Nash Equilibrium Seeking with Bounded Update Rates for Noncooperative Games

T0 review · 2 major / 3 minor · reviewed 2026-08-10 · deepseek-v4-flash

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2501.12256 v1 pith:RQ4MKD6U submitted 2025-01-21 math.OC cs.SYeess.SY

classification math.OCcs.SYeess.SY MSC 91A1091A8093D0593C40
keywords NashequilibriumseekingnoncooperativegamesextremumboundedupdateratesLie-bracketapproximationquadraticpayoffdistributedcontrolpseudo-gradient
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • (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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 3 minor

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.

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 (2)
  1. [Theorem 5.1, Eq. (5.18), Appendix Theorem 7.1] 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.
  2. [Section 4, Eq. (4.3)] 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).
minor comments (3)
  1. [Section 6, Eqs. (6.1)-(6.4)] The third payoff in the simulation is labelled J2(t) but is defined with H3, h3, and c3; it should be labelled J3(t).
  2. [Section 6, after Eq. (6.13)] The line numbered (6.14) is an empty dangling equation before the definition of H4 and should be removed.
  3. [References and text] 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'.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the main theorem follows from an external averaging result plus a Lyapunov analysis, and no fitted parameter is relabeled as a prediction.

full rationale

The paper's derivation chain is not circular. The central bound in Theorem 5.1 is obtained in two independent parts: an exponential decay estimate for the averaged (Lie-bracket) error system (5.3)–(5.15), proved directly via Gershgorin discs and a Lyapunov equation, and a trajectory-approximation estimate ||θ(t) − θ̄(t)|| ≤ O(1/ω̃) in (5.18), invoked from the external averaging theorem of Gurvits and Li ([5, Thm. 2.1], restated as Appendix Thm. 7.1). No parameter is fitted to data and then called a prediction; the residual O(1/ω̃) is derived from the frequency scaling, not from simulation. The self-citations to [2], [4], and [20] concern published, parameter-free theorems with stated assumptions (rational frequencies, strict diagonal dominance, standard Lie-bracket averaging), and none of these cited results is equivalent to Theorem 5.1 itself. There is, however, a non-circular proof gap worth flagging: Eq. (5.18) asserts the approximation bound '∀t ≥ 0', while the quoted Appendix Theorem 7.1 states only '||x − z|| ≤ O(ε)' with no explicit time-uniformity qualification. Standard averaging theorems typically provide O(ε) agreement on compact intervals, so the uniform-in-time step in (5.18) is not directly justified by the quoted theorem. This is a correctness/rigor concern, not a circularity: the missing argument (e.g., combining exponential stability with a converse Lyapunov function) would not make the conclusion an input of the derivation. The paper's novel bounded-update-rate NES construction and its Lyapunov analysis are self-contained relative to the cited external results.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The main result depends on four external premises: the game satisfies strict diagonal dominance, probing frequencies are rational and distinct, the Nash equilibrium is characterized by the linear system, and the Lie-bracket averaging theorem of Gurvits and Li holds. No data fitting or invented entities are used.

assumptions (4)
  • domain assumption Assumption 2.2: interaction matrix H is strictly diagonally dominant with H^i_ii < 0
    Used in the Gershgorin argument (equation 5.5) to ensure the average error matrix AKH is Hurwitz. Without it the pseudo-gradient flow may fail to converge to a unique Nash equilibrium.
  • domain assumption Assumption 3.1: probing frequencies omega_i are rational multiples of a common base omega with distinct ratios
    Ensures cross terms of different players' sinusoids vanish in the Lie-bracket average, reducing equation (4.1) to the diagonal pseudo-gradient dynamics (4.13).
  • standard math Assumption 2.1 / Nash condition: unique equilibrium is theta* = -H^{-1}h
    Follows from the first-order conditions (2.2)-(2.3); stated as an assumption but is a consequence of the quadratic payoff model and invertibility of H.
  • standard math Lie-bracket averaging theorem of Gurvits and Li [5, Theorem 2.1]
    The approximation bound ||theta(t)-bar-theta(t)|| <= O(1/omega-tilde), equation (5.18), is taken from this external theorem; the paper does not prove it.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Lie-Bracket Nash Equilibrium Seeking with Bounded Update Rates for Noncooperative Games." pith.science (2026). https://pith.science/paper/RQ4MKD6U

@misc{pith2026250112256,
  author       = {Pith},
  title        = {Pith review of: Lie-Bracket Nash Equilibrium Seeking with Bounded Update Rates for Noncooperative Games},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RQ4MKD6U}},
  note         = {Machine review of arXiv:2501.12256}
}
read the original abstract

This paper proposes a novel approach for local convergence to Nash equilibrium in quadratic noncooperative games based on a distributed Lie-bracket extremum seeking control scheme. This is the first instance of noncooperative games being tackled in a model-free fashion integrated with the extremum seeking method of bounded update rates. In particular, the stability analysis is carried out using Lie-bracket approximation and Lyapunov's direct method. We quantify the size of the ultimate small residual sets around the Nash equilibrium and illustrate the theoretical results numerically on an example in an oligopoly setting.

Figures

Figures reproduced from arXiv: 2501.12256 by the authors.

Figure 1
Figure 1. Block Diagram of the proposed Lie-bracket Nash equilibrium seeking with [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Players’ actions, θi(t) . In order to achieve the Nash equilibrium (6.20) and (6.21), without requiring detailed modeling information, Players P1, P2, P3, and P4 implement the proposed Lie-Bracket NES strategy to determine their optimal actions. Figures 2 and 3 depict the time evolu￾tion of the proposed Lie-Bracket NES approach, evaluating the coordinated efforts to drive 16 [PITH_FULL_IMAGE:figures/full_fig_p016_2.png] view at source ↗
Figure 3
Figure 3. Payoff functions, Ji(t). the system toward the Nash equilibrium, as shown in [PITH_FULL_IMAGE:figures/full_fig_p017_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

28 extracted references · 27 canonical work pages

  1. [1]

    Ba¸ sar and G

    T. Ba¸ sar and G. J. Olsder. Dynamic Noncooperative Game Theory. SIAM Series in Classics in Applied Mathematics. SIAM, Philadelphia, 1999

  2. [2]

    D¨ urr, M

    H.-B. D¨ urr, M. S. Stankovi´ c, C. Ebenbauer, and K. H. Johansson. Lie bracket approximation of extremum seeking systems. Automatica, 49:1538–1552, 2013

  3. [3]

    D¨ urr, M

    H.-B. D¨ urr, M. Krsti´ c, A. Scheinker, and C. Ebenbauer. Singularly perturbed lie bracket approximation. IEEE Transactions on Automatic Control , 60:3287–3292, 2015

  4. [4]

    Frihauf, M

    P. Frihauf, M. Krsti´ c, and T. Ba¸ sar. Nash equilibrium seeking in noncooperative games. IEEE Transactions on Automatic Control , 57:1192–1207, 2012

  5. [5]

    Gurvits and Z

    L. Gurvits and Z. X. Li. Smooth time-periodic feedback solutions for nonholonomic motion planning. In Z. Li and J. F. Canny, editors, Nonholonomic Motion Planning , volume 1, pages 53–90. Springer Science, Business Media New York, New York, NY, USA, 1st edition, 1993

  6. [6]

    R. A. Horn and C. R. Johnson. Matrix Analysis. Cambridge University Press, 1985

  7. [7]

    H. K. Khalil. Nonlinear Systems. Prentice Hall, Upper Saddle River, NJ, 3rd edition, 2002

  8. [8]

    Krsti´ c and H.-H

    M. Krsti´ c and H.-H. Wang. Stability of extremum seeking feedback for general nonlinear dynamic systems. Automatica, 36:595–601, 2000

Show all 28 references
  1. [9]

    J. E. Mardsden and A. J. Tromba. Vector Calculus. W. H. Freeman and Company, New York, NY, USA, 5th edition, 2003. 18

  2. [10]

    Monderer and L

    D. Monderer and L. S. Shapley. Potential games. Games and Economic Behavior , 14:124–143, 1996

  3. [11]

    J. F. Nash. Noncooperative games. Annals of Mathematics , 54:286–295, 1951

  4. [12]

    T. R. Oliveira and M. Krstic. Extremum Seeking through Delays and PDEs . SIAM, Philadelphia, 2022

  5. [13]

    T. R. Oliveira, V. H. P. Rodrigues, M. Krsti´ c, and T. Ba¸ sar. Nash equilibrium seeking in quadratic noncooperative games under two delayed information-sharing schemes. Journal of Optimization Theory and Applications , 191:700–735, 2021

  6. [14]

    T. R. Oliveira, M. Krsti´ c, and T. Ba¸ sar. Extremum and nash equilibrium seeking with delays and pdes: designs & applications. Arxiv, 2024. https://doi.org/10. 48550/arXiv.2411.13234

  7. [15]

    J. I. Poveda, M. Krsti´ c, and T. Ba¸ sar. Fixed-time nash equilibrium seeking in time- varying networks. IEEE Trans. Automat. Contr. , 68:1954–1969, 2023

  8. [16]

    V. H. P. Rodrigues, T. R. Oliveira, M. Krsti´ c, and T. Ba¸ sar. Nash equilibrium seeking for noncooperative duopoly games via event-triggered control. Arxiv, 2024. https://doi.org/10.48550/arXiv.2404.07287

  9. [17]

    V. H. P. Rodrigues, T. R. Oliveira, M. Krsti´ c, and T. Ba¸ sar. Sliding-mode nash equilibrium seeking for a quadratic duopoly game. Arxiv, 2024. https://doi.org/ 10.48550/arXiv.2405.15762

  10. [18]

    Scheinker

    A. Scheinker. Bounded extremum seeking for angular velocity actuated control of nonholonomic unicycle. Optimal Control Applications & Methods , 38:575–585, 2017

  11. [19]

    Scheinker

    A. Scheinker. 100 years of extremum seeking: a survey. Automatica, 161(111481): 1–39, 2024

  12. [20]

    Scheinker and M

    A. Scheinker and M. Krsti´ c. Extremum seeking with bounded update rates.Systems & Control Letters , 63:25–31, 2014

  13. [21]

    Scheinker and M

    A. Scheinker and M. Krsti´ c.Model-Free Stabilization by Extremum Seeking. Springer, 1st edition, 2017

  14. [22]

    Scheinker and D

    A. Scheinker and D. Scheinker. Bounded extremum seeking with discontinuous dithers. Automatica, 69:250–257, 2016

  15. [23]

    Scheinker, D

    A. Scheinker, D. Bohler, S. Tomin, R. Kammering, I. Zagorodnov, H. Schlarb, M. Scholz, B. Beutner, and W. Decking. Model-independent tuning for maximiz- ing free electron laser pulse energy. Physical Review Accelerators and Beams , 22: 082802, 2019. 19

  16. [24]

    Scheinker, S

    A. Scheinker, S. Hirlaender, F. M. Velotti, S. Gessner, G. Z. D. Porta, V. Kain, B. Goddard, and R. Ramjiawan. Online multi-objective particle accelerator optimiza- tion of the awake electron beam line for simultaneous emittance and orbit control. AIP Advances, 10:055320, 2020

  17. [25]

    Scheinker, E.-C

    A. Scheinker, E.-C. Huang, and C. Taylor. Extremum seeking-based control sys- tem for particle accelerator beam loss minimization. IEEE Transactions on Control Systems Technology, 30:2261–2268, 2022

  18. [26]

    M. Tang, U. Javed, X. Chen, M. Krsti´ c, and J. I. Poveda. Deception in nash equi- librium seeking. Arxiv, 2024. https://doi.org/10.48550/arXiv.2407.05168

  19. [27]

    O. Taussky. A recurring theorem on determinants. The American Mathematical Monthly, 56:672–676, 1949

  20. [28]

    Zhang, D

    C. Zhang, D. Arnold, N. Ghods, A. Siranosian, and M. Krstic. Source seeking with nonholonomic unicycle without position measurement and with tuning of forward velocity. Systems and Control Letters , 56:245–252, 2007. Appendix Averaging of Nonholonomic Systems [5] In this secti...

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.