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 →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
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.
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 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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)
- [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.
- [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)
- [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).
- [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.
- [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
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
assumptions (4)
- domain assumption Assumption 2.2: interaction matrix H is strictly diagonally dominant with H^i_ii < 0
- domain assumption Assumption 3.1: probing frequencies omega_i are rational multiples of a common base omega with distinct ratios
- standard math Assumption 2.1 / Nash condition: unique equilibrium is theta* = -H^{-1}h
- standard math Lie-bracket averaging theorem of Gurvits and Li [5, Theorem 2.1]
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
Reference graph
Works this paper leans on
-
[1]
T. Ba¸ sar and G. J. Olsder. Dynamic Noncooperative Game Theory. SIAM Series in Classics in Applied Mathematics. SIAM, Philadelphia, 1999
work page 1999
- [2]
- [3]
-
[4]
P. Frihauf, M. Krsti´ c, and T. Ba¸ sar. Nash equilibrium seeking in noncooperative games. IEEE Transactions on Automatic Control , 57:1192–1207, 2012
work page 2012
-
[5]
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
work page 1993
-
[6]
R. A. Horn and C. R. Johnson. Matrix Analysis. Cambridge University Press, 1985
work page 1985
-
[7]
H. K. Khalil. Nonlinear Systems. Prentice Hall, Upper Saddle River, NJ, 3rd edition, 2002
work page 2002
-
[8]
M. Krsti´ c and H.-H. Wang. Stability of extremum seeking feedback for general nonlinear dynamic systems. Automatica, 36:595–601, 2000
work page 2000
Show all 28 references
-
[9]
J. E. Mardsden and A. J. Tromba. Vector Calculus. W. H. Freeman and Company, New York, NY, USA, 5th edition, 2003. 18
2003
-
[10]
Monderer and L
D. Monderer and L. S. Shapley. Potential games. Games and Economic Behavior , 14:124–143, 1996
1996
-
[11]
J. F. Nash. Noncooperative games. Annals of Mathematics , 54:286–295, 1951
1951
-
[12]
T. R. Oliveira and M. Krstic. Extremum Seeking through Delays and PDEs . SIAM, Philadelphia, 2022
2022
-
[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
2021
- [14]
-
[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
1954
- [16]
- [17]
-
[18]
Scheinker
A. Scheinker. Bounded extremum seeking for angular velocity actuated control of nonholonomic unicycle. Optimal Control Applications & Methods , 38:575–585, 2017
2017
-
[19]
Scheinker
A. Scheinker. 100 years of extremum seeking: a survey. Automatica, 161(111481): 1–39, 2024
2024
-
[20]
Scheinker and M
A. Scheinker and M. Krsti´ c. Extremum seeking with bounded update rates.Systems & Control Letters , 63:25–31, 2014
2014
-
[21]
Scheinker and M
A. Scheinker and M. Krsti´ c.Model-Free Stabilization by Extremum Seeking. Springer, 1st edition, 2017
2017
-
[22]
Scheinker and D
A. Scheinker and D. Scheinker. Bounded extremum seeking with discontinuous dithers. Automatica, 69:250–257, 2016
2016
-
[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
2019
-
[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
2020
-
[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
2022
- [26]
-
[27]
O. Taussky. A recurring theorem on determinants. The American Mathematical Monthly, 56:672–676, 1949
1949
-
[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...
2007
Reviewed August 10, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.