pith. machine review for the scientific record. sign in

arxiv: 2605.01898 · v1 · submitted 2026-05-03 · 🧮 math.OC

Recognition: unknown

Fast Newton methods for linear-quadratic dynamic games with application to autonomous vehicle platooning and intersection crossing

Reza Rahimi Baghbadorani , Sergio Grammatico
Authors on Pith no claims yet

Pith reviewed 2026-05-09 16:45 UTC · model grok-4.3

classification 🧮 math.OC
keywords linear-quadratic dynamic gamesNash equilibriaNewton methodsvariational inequalitiesreceding-horizon controlautonomous vehiclesplatooningintersection crossing
0
0 comments X

The pith

Reformulating Nash equilibria as receding-horizon affine variational inequalities enables Newton-type algorithms with local quadratic convergence for linear-quadratic dynamic games.

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

The paper shows that infinite-horizon Nash equilibria in constrained linear-quadratic dynamic games can be exactly reformulated as receding-horizon affine variational inequalities. This structured reformulation supports the design of Newton-type algorithms that converge quadratically in a local neighborhood. The fast convergence suits the methods for real-time receding-horizon control in embedded systems handling safety-critical tasks like autonomous vehicle platooning and intersection crossing. Simulations of these scenarios confirm substantial speed and accuracy gains compared with first-order and operator-splitting baselines.

Core claim

Infinite-horizon Nash equilibria of constrained linear-quadratic dynamic games are reformulated as receding-horizon affine variational inequalities that preserve sufficient structure. Newton-type algorithms designed on this formulation achieve local quadratic convergence, delivering extremely fast solutions suitable for real-time embedded receding-horizon control in traffic applications.

What carries the argument

The receding-horizon affine variational inequality reformulation of the infinite-horizon Nash equilibrium, which retains the structure required for quadratic local convergence of the Newton methods.

Load-bearing premise

The infinite-horizon Nash equilibria can be exactly reformulated as receding-horizon affine variational inequalities that retain enough structure for the Newton methods to converge quadratically.

What would settle it

A numerical experiment on platooning or intersection crossing where the Newton iterates fail to exhibit quadratic convergence rates or where the computed solutions deviate from the true Nash equilibria beyond numerical tolerance.

Figures

Figures reproduced from arXiv: 2605.01898 by Reza Rahimi Baghbadorani, Sergio Grammatico.

Figure 1
Figure 1. Figure 1: (a) Position of vehicles with respect to the leading view at source ↗
Figure 2
Figure 2. Figure 2: Iterations required for convergence of the VI view at source ↗
Figure 3
Figure 3. Figure 3: Computational time for convergence of the VI view at source ↗
Figure 4
Figure 4. Figure 4: (a) Distance between χ(i) and i. (b) Velocities. Let us adopt weighting matrices Qi = I and Ri = 1, supplemented by a warm-start strategy where the input sequence is shifted at each time step. As illustrated in Figures 5 and 6, the (Fast)-Newton approaches have supe￾rior computational efficiency, significantly outperforming standard Forward-Backward (FB) and Douglas-Rachford (DR) splitting methods in both … view at source ↗
Figure 7
Figure 7. Figure 7: Forward-Backward trajectories for 10 fixed itera view at source ↗
Figure 8
Figure 8. Figure 8: Douglas–Rachford trajectories for 10 fixed itera view at source ↗
read the original abstract

We consider constrained linear-quadratic dynamic games arising in autonomous vehicle platooning, intersection crossing and other cooperative driving scenarios. Infinite-horizon Nash equilibria are reformulated as receding-horizon affine variational inequalities with special structure. Exploiting this formulation, we design Newton-type algorithms with local quadratic convergence. The resulting methods achieve extremely fast convergence, making them well suited for real-time and embedded receding-horizon control in safety-critical traffic applications. Simulations of platooning and intersection crossing demonstrate substantial performance gains over first-order and operator-splitting approaches, hence high application potential.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper claims that infinite-horizon Nash equilibria in constrained linear-quadratic dynamic games can be exactly reformulated as receding-horizon affine variational inequalities preserving special structure. It designs Newton-type algorithms exploiting this structure to achieve local quadratic convergence, with simulations on autonomous vehicle platooning and intersection crossing demonstrating substantial gains over first-order and operator-splitting methods, positioning the approach for real-time embedded receding-horizon control.

Significance. If the exact reformulation and local quadratic convergence hold under the stated conditions, the work has high significance for safety-critical traffic applications. The structured VI reformulation and fast Newton solvers could enable responsive embedded control in platooning and intersection scenarios where first-order methods are too slow, advancing game-theoretic methods in autonomous driving.

major comments (2)
  1. [Abstract] Abstract and algorithm design section: the claim of local quadratic convergence for the Newton-type methods on the receding-horizon affine VIs is load-bearing but unsupported by any derivation details, error bounds, or proof sketches. Standard semismooth Newton methods require local strong monotonicity (or CD-regularity) of the stacked VI operator, yet no such verification is supplied.
  2. [Sections 5.1–5.2] Sections 5.1–5.2 (platooning and intersection examples): no report of the minimal eigenvalue of the symmetric part of the Jacobian (or equivalent monotonicity constant) for the chosen cost weights and constraint sets. Without this, it cannot be confirmed that the operator satisfies the conditions for quadratic convergence, so the observed speed-ups cannot be attributed to the Newton step rather than other algorithmic features.
minor comments (2)
  1. The abstract and introduction should explicitly define acronyms on first use (e.g., VI, LQ) and briefly indicate the precise Newton variant (semismooth, etc.) employed.
  2. [Simulation sections] Simulation figures and tables would benefit from expanded captions that include all numerical parameter values, constraint bounds, and solver tolerances to support reproducibility.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful review and valuable comments. These points help clarify the presentation of our theoretical results and numerical validations. We provide point-by-point responses below and will make the necessary revisions to the manuscript.

read point-by-point responses

  1. Referee: [Abstract] Abstract and algorithm design section: the claim of local quadratic convergence for the Newton-type methods on the receding-horizon affine VIs is load-bearing but unsupported by any derivation details, error bounds, or proof sketches. Standard semismooth Newton methods require local strong monotonicity (or CD-regularity) of the stacked VI operator, yet no such verification is supplied.

    Authors: We acknowledge the referee's observation that the manuscript does not include detailed derivation or proof sketches for the local quadratic convergence of the Newton-type methods. The reformulation as receding-horizon affine VIs is intended to allow the application of standard semismooth Newton theory, but we agree that explicit verification of the local strong monotonicity or CD-regularity of the stacked VI operator is necessary to support the claims. In the revised manuscript, we will add a proof sketch in the algorithm design section, including the relevant conditions and error bounds. revision: yes

  2. Referee: [Sections 5.1–5.2] Sections 5.1–5.2 (platooning and intersection examples): no report of the minimal eigenvalue of the symmetric part of the Jacobian (or equivalent monotonicity constant) for the chosen cost weights and constraint sets. Without this, it cannot be confirmed that the operator satisfies the conditions for quadratic convergence, so the observed speed-ups cannot be attributed to the Newton step rather than other algorithmic features.

    Authors: We agree that reporting the minimal eigenvalue of the symmetric part of the Jacobian or the monotonicity constant for the specific parameters in the platooning and intersection examples is important for confirming the conditions for quadratic convergence. We will compute these values for the chosen cost weights and constraint sets and include them in the revised Sections 5.1 and 5.2. This will provide evidence that the observed performance gains are indeed due to the quadratic convergence of the Newton methods. revision: yes

Circularity Check

0 steps flagged

No circularity; reformulation and Newton methods follow standard LQ game and VI theory without self-referential reductions.

full rationale

The derivation begins with the standard infinite-horizon LQ dynamic game formulation, reformulates Nash equilibria as receding-horizon affine VIs (preserving the LQ structure by the usual dynamic programming recursion), and then applies semismooth Newton methods whose local quadratic convergence is a general result under CD-regularity or strong monotonicity of the VI operator. These steps cite external theory rather than defining the output in terms of itself or fitting parameters to data and relabeling them as predictions. No self-citation chain is load-bearing for the central claims, and the numerical examples serve only as validation, not as the source of the convergence guarantee. The chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The approach rests on standard assumptions from linear-quadratic game theory and variational inequality solvers; no free parameters, invented entities, or ad-hoc axioms are mentioned in the abstract.

axioms (1)
  • domain assumption Constrained linear-quadratic dynamic games admit infinite-horizon Nash equilibria that can be recast as receding-horizon affine variational inequalities with exploitable structure.
    This is the foundational modeling step stated in the abstract that enables the Newton methods.

pith-pipeline@v0.9.0 · 5390 in / 1130 out tokens · 33258 ms · 2026-05-09T16:45:19.439259+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

20 extracted references · 1 canonical work pages · 1 internal anchor

  1. [1]

    Influence of connected and autonomous vehicles on traffic flow stability and through- put,

    A. Talebpour and H. S. Mahmassani, “Influence of connected and autonomous vehicles on traffic flow stability and through- put,” Transportation Research part C: Emerging technologies, pp. 143–163, 2016

    2016

  2. [2]

    Distributed consensus strategy for platooning of vehicles in the presence of time- varying heterogeneous communication delays,

    M. Di Bernardo, A. Salvi, and S. Santini, “Distributed consensus strategy for platooning of vehicles in the presence of time- varying heterogeneous communication delays,” IEEE Transac- tions on Intelligent Transportation Systems, vol. 16, no. 1, pp. 102–112, 2014

    2014

  3. [3]

    A real-time game theoretic planner for autonomous two- player drone racing,

    R. Spica, E. Cristofalo, Z. Wang, E. Montijano, and M. Schwa- ger, “A real-time game theoretic planner for autonomous two- player drone racing,” IEEE Transactions on Robotics, vol. 36, pp. 1389–1403, 2020

    2020

  4. [4]

    Game-theoretic planning for self-driving cars in multivehicle competitive scenarios,

    M. Wang, Z. Wang, J. Talbot, J. C. Gerdes, and M. Schwager, “Game-theoretic planning for self-driving cars in multivehicle competitive scenarios,” IEEE Transactions on Robotics, vol. 37, no. 4, pp. 1313–1325, 2021

    2021

  5. [5]

    Başar and G

    T. Başar and G. J. Olsder, Dynamic noncooperative game theory. SIAM, 1998

    1998

  6. [6]

    On the uniqueness of the Nash solution in linear- quadratic differential games,

    T. Basar, “On the uniqueness of the Nash solution in linear- quadratic differential games,” International Journal of Game Theory, vol. 5, no. 2-3, pp. 65–90, 1976

    1976

  7. [7]

    Feedback and open-loop nash equilibria for lq infinite-horizon discrete-time dynamic games,

    A. Monti, B. Nortmann, T. Mylvaganam, and M. Sassano, “Feedback and open-loop nash equilibria for lq infinite-horizon discrete-time dynamic games,” SIAM Journal on Control and Optimization, vol. 62, no. 3, pp. 1417–1436, 2024

    2024

  8. [8]

    Linear-quadratic dynamic games as receding-horizon variational inequalities,

    E. Benenati and S. Grammatico, “Linear-quadratic dynamic games as receding-horizon variational inequalities,” IEEE Transactions on Automatic Control, 2026

    2026

  9. [9]

    A Douglas-Rachford Splitting Method for Solving Monotone Variational Inequalities in Linear-quadratic Dynamic Games

    R. R. Baghbadorani, E. Benenati, and S. Grammatico, “A Douglas–Rachford splitting method for solving monotone vari- ational inequalities in linear-quadratic dynamic games,” arXiv preprint arXiv:2504.05757, 2025

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  10. [10]

    monviso: A python package for solving monotone variational inequalities,

    N. Mignoni, R. R. Baghbadorani, R. Carli, P. M. Esfahani, M. Dotoli, and S. Grammatico, “monviso: A python package for solving monotone variational inequalities,” in 2025 European Control Conference (ECC). IEEE, 2025

    2025

  11. [11]

    Facchinei and J.-S

    F. Facchinei and J.-S. Pang, Finite-dimensional variational inequalities and complementarity problems. Springer, 2003

    2003

  12. [12]

    On the local superlinear convergence of a newton- type method for lcp under weak conditions,

    F. Andreas, “On the local superlinear convergence of a newton- type method for lcp under weak conditions,” Optimization Methods and Software, vol. 6, no. 2, pp. 83–107, 1995

    1995

  13. [13]

    Smooth approximations to nonlinear complementarity problems,

    B. Chen and P. T. Harker, “Smooth approximations to nonlinear complementarity problems,” SIAM Journal on Optimization, vol. 7, no. 2, pp. 403–420, 1997

    1997

  14. [14]

    Some noninterior continuation methods for linear complementarity problems,

    C. Kanzow, “Some noninterior continuation methods for linear complementarity problems,” SIAM Journal on Matrix Analysis and Applications, vol. 17, no. 4, pp. 851–868, 1996

    1996

  15. [15]

    A. L. Dontchev and R. T. Rockafellar, Implicit functions and solution mappings. Springer, 2009, vol. 543

    2009

  16. [16]

    Minimization of functions having lipschitz contin- uous first partial derivatives,

    L. Armijo, “Minimization of functions having lipschitz contin- uous first partial derivatives,” Pacific Journal of Mathematics, vol. 16, 1966

    1966

  17. [17]

    J. E. Dennis Jr and R. B. Schnabel, Numerical methods for unconstrained optimization and nonlinear equations. SIAM, 1996

    1996

  18. [18]

    On distributed model predictive control for vehicle platooning with a recursive feasibility guarantee,

    S. Shi and M. Lazar, “On distributed model predictive control for vehicle platooning with a recursive feasibility guarantee,” IF AC-PapersOnLine, vol. 50, no. 1, pp. 7193–7198, 2017

    2017

  19. [19]

    Nemirovski and D

    A. Nemirovski and D. Yudin, Problem Complexity and Method Efficiency in Optimization. John Wiley, 1983

    1983

  20. [20]

    Operator-splitting methods for monotone affine variational inequalities, with a parallel appli- cation to optimal control,

    J. Eckstein and M. C. Ferris, “Operator-splitting methods for monotone affine variational inequalities, with a parallel appli- cation to optimal control,” INFORMS Journal on Computing, vol. 10, pp. 218–235, 1998

    1998