pith. sign in

arxiv: 2605.16002 · v2 · pith:5DZ7WM4Ynew · submitted 2026-05-15 · 🧮 math.OC

Towards A Goldfarb-Idnani Variant for Strongly Monotone Linear-Quadratic Games

Alberto Bemporad This is my paper

Pith reviewed 2026-05-21 07:43 UTC · model grok-4.3

classification 🧮 math.OC
keywords Goldfarb-Idnani algorithmdual active-set methodgeneralized Nash equilibriastrongly monotone gameslinear-quadratic gamesvariational equilibriamodel predictive control
0
0 comments X

The pith

A variant of the Goldfarb-Idnani dual active-set method preserves several properties when applied to strongly monotone linear-quadratic games with non-symmetric pseudogradient matrices.

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

The paper develops a simple variant of the Goldfarb-Idnani dual active-set method to compute variational generalized Nash equilibria for N-player games whose players have convex quadratic costs subject to shared affine inequality and equality constraints. It establishes that multiple algorithmic properties from the original method continue to hold even though the joint KKT system may contain a non-symmetric pseudogradient matrix. Convergence to an equilibrium is not assured, in contrast to the symmetric case handled by the standard algorithm. Numerical tests indicate the variant performs competitively against other solvers, including when used to derive game-theoretic linear model predictive control policies.

Core claim

The central claim is that a simple variant of the Goldfarb-Idnani dual active-set method applied to the joint KKT system of strongly monotone N-player linear-quadratic games maintains several properties of the original algorithm despite the presence of a possibly non-symmetric pseudogradient matrix, although convergence to an existing variational generalized Nash equilibrium is not guaranteed.

What carries the argument

The variant of the Goldfarb-Idnani dual active-set method applied directly to the joint KKT system of the game, which continues to function with a non-symmetric pseudogradient matrix while retaining core algorithmic features.

If this is right

  • The variant computes variational generalized Nash equilibria for N-player games with convex quadratic costs and shared affine constraints.
  • Several algorithmic properties of the original Goldfarb-Idnani method, such as active-set management rules, remain valid under non-symmetry.
  • The approach is competitive with existing solvers on benchmark problems, including those arising in game-theoretic linear model predictive control.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same variant might serve as a fast warm-start solver inside receding-horizon schemes where the pseudogradient changes slowly between time steps.
  • Relaxing strong monotonicity to mere monotonicity would likely require additional regularization or line-search steps to restore the preserved properties.
  • Direct comparison of iteration counts against interior-point or projection methods on the same non-symmetric instances could quantify practical speed-ups.

Load-bearing premise

The game must be strongly monotone so that a variational generalized Nash equilibrium exists and the non-symmetry does not invalidate the preserved properties of the active-set updates.

What would settle it

A concrete strongly monotone game instance with a known non-symmetric pseudogradient matrix in which the variant loses a key original-GI property, such as finite termination or correct identification of the active set at termination.

Figures

Figures reproduced from arXiv: 2605.16002 by Alberto Bemporad.

Figure 1
Figure 1. Figure 1: Closed-loop output trajectories y1, . . . , y6 (top, solid lines), output refer￾ences (top, dashed lines), and input trajectories u1, . . . , u6 (bottom) for GT-MPC with prediction horizon T = 30. Colors indicate inputs (outputs) manipulated (more weighted) by each agent. focus on variational GNEs which, although a common assumption in the literature, limits its scope of applicability. Future research will… view at source ↗
Figure 2
Figure 2. Figure 2: CPU time per closed-loop step for GT-MPC ( [PITH_FULL_IMAGE:figures/full_fig_p013_2.png] view at source ↗
read the original abstract

We analyze a simple variant of the Goldfarb-Idnani (GI) dual active-set method for computing variational generalized Nash equilibria of strongly monotone N-player games with convex quadratic costs and shared affine inequality and equality constraints. We show that several properties of the GI algorithm are maintained in spite of having a possibly non-symmetric pseudogradient matrix in the joint KKT system of the game, although convergence to an existing equilibrium is not guaranteed as in the original algorithm. Our numerical results show that the method is potentially competitive with alternative state-of-the-art algorithms, including for computing solutions of game-theoretic linear model predictive control laws.

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

0 major / 3 minor

Summary. The manuscript analyzes a simple variant of the Goldfarb-Idnani dual active-set method applied to the joint KKT system of N-player strongly monotone linear-quadratic games with shared affine constraints. It claims that several core properties of the original GI algorithm (active-set update rules, dual feasibility maintenance) are preserved despite a possibly non-symmetric pseudogradient matrix, while explicitly noting that global convergence to a variational GNE is not guaranteed (unlike the symmetric case). Numerical experiments are presented to show practical competitiveness with state-of-the-art solvers, including for game-theoretic linear MPC.

Significance. If the preservation of the listed algorithmic properties is rigorously established under strong monotonicity, the work offers a practical extension of efficient active-set QP technology to variational GNE computation. This could be useful in multi-agent control and optimization settings where LQ games arise naturally. The explicit caveat on convergence is a positive feature that avoids overclaiming, and the numerical results provide supporting evidence of utility without substituting for analysis.

minor comments (3)
  1. Abstract: the phrase 'potentially competitive' is imprecise; replace with a brief quantitative statement (e.g., 'comparable iteration counts on problems up to dimension X') drawn from the numerical section.
  2. Notation section (likely §2): the joint KKT system is introduced without an explicit block-matrix display of the nonsymmetric pseudogradient; adding this would clarify how nonsymmetry enters the dual step.
  3. Numerical results section: the data-exclusion rules and stopping tolerances for the reported timings are not stated; add a short paragraph or table footnote to ensure reproducibility.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our manuscript, the recognition of its practical relevance to multi-agent control and game-theoretic MPC, and the recommendation for minor revision. We appreciate the explicit note that our caveat on the lack of global convergence is a positive feature.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper analyzes a variant of the Goldfarb-Idnani dual active-set method applied to the joint KKT system of strongly monotone linear-quadratic games, showing that several algorithmic properties are preserved even with a possibly non-symmetric pseudogradient matrix. The derivation relies on the structure of the original GI algorithm combined with the strong monotonicity assumption to ensure well-posedness and existence of a variational GNE, while explicitly noting that global convergence is not guaranteed. No load-bearing step reduces by construction to a fitted parameter, self-definition, or self-citation chain; the maintained properties (active-set updates, dual feasibility) follow directly from the algorithm's mechanics and the monotonicity condition without circular reduction to the target claims. The numerical examples serve only as practical illustration, not as proof substitutes, rendering the analysis self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on standard domain assumptions from optimization and game theory; no free parameters or invented entities are introduced in the abstract.

axioms (1)
  • domain assumption The N-player game is strongly monotone with convex quadratic costs and shared affine constraints
    This is invoked to guarantee existence of a variational GNE and to set up the joint KKT system to which the GI variant is applied.

pith-pipeline@v0.9.0 · 5625 in / 1331 out tokens · 39810 ms · 2026-05-21T07:43:08.305622+00:00 · methodology

Review history (2 revisions) →

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

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

  1. [1]

    \texttt{DR-DAQP}: An Hybrid Operator Splitting and Active-Set Solver for Affine Variational Inequalities

    D. Arnström, E. Benenati, and G. Belgioioso.DR-DAQP: An hybrid oper- ator splitting and active-set solver for affine variational inequalities.ArXiv 2604.02531, 2026

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  2. [2]

    Belgioioso, P

    G. Belgioioso, P. Yi, S. Grammatico, and L. Pavel. Distributed generalized Nash equilibrium seeking: An operator-theoretic perspective.IEEE Control Systems Magazine, 42(4):87–102, August 2022

    work page 2022

  3. [3]

    Bemporad

    A. Bemporad. NashOpt: A Python library for computing generalized Nash equilibria and game design.Optimization Methods & Software, 2026. code available athttps://github.com/bemporad/nashopt

    work page 2026

  4. [4]

    Börgens and C

    E. Börgens and C. Kanzow. ADMM-type methods for generalized Nash equilibrium problems in Hilbert spaces.SIAM Journal on Optimization, 31(1):377–403, 2021

    work page 2021

  5. [5]

    Cao and M.C

    M. Cao and M.C. Ferris. A pivotal method for affine variational inequalities. Mathematics of Operations research, 21(1):44–64, 1996

    work page 1996

  6. [6]

    Cottle, J.-S

    R.W. Cottle, J.-S. Pang, and R.E. Stone.The linear complementarity problem. SIAM, 2009

    work page 2009

  7. [7]

    do Nascimento, A

    A.A. do Nascimento, A. Papachristodoulou, and K. Margellos. A game the- oretic approach for safe and distributed control of unmanned aerial vehicles. InProc. 62nd IEEE Conference on Decision and Control, pages 1070–1075, 2023. 13

    work page 2023

  8. [8]

    Dreves, F

    A. Dreves, F. Facchinei, C. Kanzow, and S. Sagratella. On the solution of the KKT conditions of generalized Nash equilibrium problems.SIAM Journal on Optimization, 21(3):1082–1108, 2011

    work page 2011

  9. [9]

    Fabiani and A

    F. Fabiani and A. Bemporad. An active learning method for solving com- petitive multi-agent decision-making and control problems.IEEE Trans- actions on Automatic Control, 70(4):2374–2389, 2025. code availble at https://github.com/bemporad/gnep-learn

    work page 2025

  10. [10]

    Facchinei and J.-S

    F. Facchinei and J.-S. Pang.Finite-Dimensional Variational Inequalities and Complementarity Problems, volume I. Springer, 2003

    work page 2003

  11. [11]

    Goldfarb and A

    D. Goldfarb and A. Idnani. A numerically stable dual method for solving strictly convex quadratic programs.Mathematical Programming, 27(1):1– 33, 1983

    work page 1983

  12. [12]

    S. Hall, G. Belgioioso, D. Liao-McPherson, and F. Dörfler. Receding horizon games with coupling constraints for demand-side management. InProc. IEEE 61st Conference on Decision and Control, pages 3795–3800, 2022

    work page 2022

  13. [13]

    Hall and A

    S. Hall and A. Bemporad. Solving multiparametric generalized Nash equi- librium problems and explicit game-theoretic model predictive control. 2025. arXiv:2512.05505

    work page arXiv 2025

  14. [14]

    Kanzow and D

    C. Kanzow and D. Steck. Augmented Lagrangian methods for the solution of generalized Nash equilibrium problems.SIAM Journal on Optimization, 26(4):2034–2058, 2016

    work page 2034

  15. [15]

    Y . Kim, O. Huber, and M.C. Ferris. A structure-preserving pivotal method for affine variational inequalities.Mathematical Programming, 168(1):93–121, 2018

    work page 2018

  16. [16]

    Le Cleac’h, M

    S. Le Cleac’h, M. Schwager, and Z. Manchester. ALGAMES: a fast aug- mented Lagrangian solver for constrained dynamic games.Autonomous Robots, 46(1):201–215, 2022

    work page 2022

  17. [17]

    C.E. Lemke. Bimatrix equilibrium points and mathematical programming. Management science, 11(7):681–689, 1965

    work page 1965

  18. [18]

    Liu and D

    B. Liu and D. Liao-McPherson. A log-domain interior point method for con- vex quadratic games. InProc. American Control Conference, pages 4891– 4896, 2025

    work page 2025

  19. [19]

    Mignoni, R.R

    N. Mignoni, R.R. Baghbadorani, R. Carli, P.M. Esfahani, M. Dotoli, and S. Grammatico. monviso: A Python package for solving monotone varia- tional inequalities. InEuropean Control Conference, 2025

    work page 2025

  20. [20]

    Nocedal and S.J

    J. Nocedal and S.J. Wright.Numerical Optimization. Springer, 2 edition, 2006. 14

    work page 2006

  21. [21]

    J.B. Rosen. Existence and uniqueness of equilibrium points for concaveN- person games.Econometrica, 33(3):520–534, 1965

    work page 1965

  22. [22]

    Schiro, J.-S

    D.A. Schiro, J.-S. Pang, and U.V . Shanbhag. On the solution of affine general- ized Nash equilibrium problems with shared constraints by Lemke’s method. Mathematical Programming, 142(1–2):1–46, 2013

    work page 2013

  23. [23]

    Tatarenko and M

    T. Tatarenko and M. Kamgarpour. Learning generalized Nash equilibria in a class of convex games.IEEE Transactions on Automatic Control, 64(4):1426–1439, 2018

    work page 2018

  24. [24]

    Tatarenko, W

    T. Tatarenko, W. Shi, and A. Nedi´c. Geometric convergence of gradient play algorithms for distributed Nash equilibrium seeking.IEEE Transactions on Automatic Control, 66(11):5342–5353, 2021

    work page 2021

  25. [25]

    Yi and L

    P. Yi and L. Pavel. An operator splitting approach for distributed generalized Nash equilibria computation.Automatica, 102:111–121, 2019. 15

    work page 2019