betaFeedback

WorksMathematics

A Hierarchical Variational Inequality Approach to Generalized Nash Equilibrium Seeking with Nonlinear Shared Constraints

Abstract

We study the computation of variational generalized Nash equilibria (v-GNE) in games with strongly monotone pseudo-gradients and nonlinear convex shared constraints. We show that the v-GNE problem is exactly equivalent to a hierarchical variational inequality, whose lower level is given by the gradient of a smooth convex penalty of the constraint violation over the local action sets. Building on this reformulation, we propose a hierarchical regularization scheme that operates entirely in the primal space and requires only projections onto the local action sets. In the centralized setting, we prove last-iterate squared distance convergence to the v-GNE with rate O(1/t2/3)O(1/t^{\scriptscriptstyle 2/3}) under a local error bound condition, which holds, e.g., under Slater's condition, improved to O(1/t)O(1/t) under a global error bound condition. We then extend the scheme to the partial-decision information setting, where the agents communicate over a network and maintain local estimates of the joint action. We derive a distributed algorithm with a constant stepsize operating in the primal space and converging to the v-GNE with rate O(1/t)O(1/t).

Introduction

Generalized Nash equilibrium problems (GNEPs) model noncooperative interactions in which self-interested agents are coupled not only through their cost functions but also through shared constraints on their joint actions [11]. Such problems arise in a variety of engineering applications, including electricity markets and demand-side management [6, 35], charging coordination of electric vehicles [18], traffic and transportation networks [8], and communication systems [31]. In many of these settings, the shared constraints represent physical limits of a common infrastructure, such as line ratings, transformer loadings, or voltage-stability margins in power networks, and are therefore inherently nonlinear [17]. Moreover, the agents are typically not coordinated by a central operator and possess only local information: each agent knows its own cost and local constraints and can exchange information only with its neighbors over a communication network [22].

Among the generalized Nash equilibria, a particularly relevant subclass is formed by the variational GNE (v-GNE), which correspond to solutions of a variational inequality (VI) defined by the game pseudo-gradient over the coupled feasible set [9]. The v-GNE are economically meaningful, as all agents face the same shadow price for the shared resources [16], and, under strong monotonicity of the

T. Tatarenko is with the Technical University of Darmstadt, Darmstadt, Germany (e-mail: [email protected]). P. Latafat and A. Bemporad are with the IMT School for Advanced Studies Lucca, Lucca, Italy (e-mail: [email protected]; [email protected]).

The work was funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation). Project number: 528033031. This work was also funded by the European Union (ERC Advanced Research Grant COMPACT, No. 101141351). Views and opinions expressed are however those of the authors only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them.

pseudo-gradient, a v-GNE exists and is unique [10]. The VI characterization suggests solving the problem by projection-type methods, such as projected gradient play or the extragradient method [2, 14, 15, 23]. However, these methods require projections onto the coupled feasible set. When the shared constraints are nonlinear, such projections are generally not available in closed form and require solving an auxiliary optimization problem at every iteration. Furthermore, since the coupled feasible set depends on the joint action profile, these projections cannot be computed locally by the agents.

For this reason, the majority of existing GNE seeking algorithms rely on the Karush–Kuhn–Tucker (KKT) conditions of the v-GNE and operate in the lifted primal–dual space, in which the shared constraints are handled through Lagrange multipliers [28, 32]. In the partial-decision information setting, where each agent maintains estimates of the actions of the others and communicates only with its neighbors [34], distributed primal–dual schemes based on operator splitting have been developed [5, 25]. These methods, however, require the agents to maintain, update, and reach consensus on local copies of the dual variables, which increases both the computational and the communication burden. Moreover, their convergence analysis concerns linear coupling constraints. For nonlinear shared constraints, the lifted operator is not globally Lipschitz continuous, even if the original game’s pseudo-gradient possesses this property, and, thus, constant-stepsize primal–dual methods lose their guarantees. In this case, additional mechanisms, such as adaptive or line-search stepsize rules [19, 20], are required. However, these rules are still applied to the lifted primal–dual operator and cannot be implemented in a distributed manner, as the line search requires the stepsize to be coordinated centrally among all agents.

In this paper, we take a different route and avoid dual variables altogether. We observe that the set of feasible joint actions coincides with the set of minimizers of a smooth convex penalty function defined for the constraint violation over the local action sets. As a consequence, the v-GNE problem is exactly equivalent to a hierarchical VI, in which the upper level is given by the game pseudo-gradient and the lower-level VI is given by the gradient of the penalty and involves only projections onto the local action sets. Hierarchical VIs have been studied by means of vanishing (Tikhonov-type) regularization [13, 21] (see also [1] for minimization problems) and extragradient-type schemes [30]. However, all these methods are centralized procedures: they assume that the full operators of both levels are available to a single computing unit and require full information on the joint decision vector at every iteration. These works address general monotone lower-level operators and typically provide guarantees for ergodic averages or in terms of gap functions. In contrast, the nonlinear lower-level VI in our reformulation corresponds to a convex optimization problem, and we exploit this structure to obtain last-iterate convergence rates to the v-GNE. To the best of our knowledge, the hierarchical VI reformulation has not been used before to design distributed GNE seeking algorithms that operate entirely in the primal space.

The main contributions of this paper are summarized as follows.

  • We propose an equivalent reformulation of the v-GNE problem with nonlinear convex shared constraints as a hierarchical VI,

which does not require the introduction of dual variables.

  • We develop a centralized hierarchical regularization scheme that performs a single projected step onto the local action sets per iteration. Under a local error bound condition on the constraint set, which holds, e.g., under Slater’s condition, we prove last-iterate squared distance convergence to the v-GNE with rate O(1/t2/3)O(1/t^{2/3}). Under a global error bound condition, which holds, e.g., for linear shared constraints and polyhedral local sets, we improve this rate to O(1/t)O(1/t).

  • We extend the scheme to the partial-decision information setting, in which the agents communicate over a connected undirected graph and maintain local estimates of the joint action. The resulting distributed algorithm uses a constant stepsize and requires no communication of dual variables. We prove its convergence to the v-GNE with rate O(1/t)O(1/t) under the local error bound condition (e.g., Slater’s condition) and bounded action sets.

  • We illustrate the performance of the proposed algorithms on randomly generated instances of multi-agent systems with nonlinear network constraints and on distributed problems with linear shared constraints, and compare them with the corresponding KKT-based lifted primal–dual methods [5, 15, 19].

The remainder of the paper is organized as follows. Section II formulates the problem and discusses the limitations of the projection-based and primal–dual approaches. Section III presents the hierarchical VI reformulation. The centralized and distributed hierarchical regularization schemes and their convergence analysis are presented in Sections IV and § 5, respectively. Section VI provides the simulation results, and the proofs of auxiliary lemmas are collected in the Appendix.

Notation

We write [N]={1,…,N}[N] = \{1,\ldots,N\} and R+m\mathbb{R}_{+}^{m} for the nonnegative orthant of Rm\mathbb{R}^{m}. For vectors u1,…,uNu^{1},\ldots,u^{N} of possibly different dimensions, [u1,…,uN][u^{1},\ldots,u^{N}] denotes the stacked column vector; a superscript ii refers to the block associated with player ii. For u,v∈Rnu,v \in\mathbb{R}^{n}, ⟨u,v⟩\langle u,v\rangle is the Euclidean inner product and ∥u∥\|u\| is the Euclidean norm; for a matrix, ∥⋅∥\|\cdot\| is the induced spectral norm. We denote by 00 the zero vector, by 1N\mathbf{1}_{N} the NN-dimensional vector of ones, by INI_{N} the N×NN \times N identity matrix, by A⊤A^{\top} the transpose of a matrix AA, and by ⊗\otimes the Kronecker product. For a symmetric matrix AA, A⪰0A \succeq0 means that AA is positive semidefinite, and λmin⁡(A)\lambda_{\min}(A) denotes its smallest eigenvalue. For t∈Rt \in\mathbb{R}, [t]+=max⁡{t,0}[t]_{+} = \max\{t,0\}; for vectors, [⋅]+[\cdot]_{+} is applied componentwise. For a differentiable function ϕ:Rn→R\phi:\mathbb{R}^{n}\to\mathbb{R}, ∇ϕ(a)\nabla\phi(a) is its gradient and ∇iϕ(a)\nabla_{i}\phi(a) is its partial with respect to aia^{i}.

For a nonempty closed convex set X⊆RnX \subseteq\mathbb{R}^{n}, ΠX(u)=argmin⁡y∈X∥y−u∥\Pi_{X}(u) = \operatorname*{argmin}_{y\in X}\|y-u\| is the Euclidean projection of uu onto XX, dist⁡(u,X)=∥u−ΠX(u)∥\operatorname{dist}(u,X)=\|u-\Pi_{X}(u)\| is the distance from uu to XX, NX(u)={v:⟨v,y−u⟩≤0 ∀y∈X}N_{X}(u)=\{v:\langle v,y-u\rangle\leq0\ \forall y\in X\} is the normal cone to XX at u∈Xu\in X, and int⁡X\operatorname{int}X and ri⁡X\operatorname{ri}X are the interior and the relative interior of XX. Given F:X→RnF:X\to\mathbb{R}^{n}, VI⁡(X,F)\operatorname{VI}(X,F) is the problem of finding u∈Xu\in X such that ⟨F(u),y−u⟩≥0\langle F(u),y-u\rangle\geq0 for all y∈Xy\in X, and SOL⁡(X,F)\operatorname{SOL}(X,F) is its solution set.

A mapping F:X→RnF:X\to\mathbb{R}^{n} is LL-Lipschitz continuous on XX if ∥F(u)−F(v)∥≤L∥u−v∥\|F(u)-F(v)\|\leq L\|u-v\|, monotone if ⟨F(u)−F(v),u−v⟩≥0\langle F(u)-F(v),u-v\rangle\geq0, μ\mu-strongly monotone if ⟨F(u)−F(v),u−v⟩≥μ∥u−v∥2\langle F(u)-F(v),u-v\rangle\geq\mu\|u-v\|^{2}, and 1L\frac{1}{L}-cocoercive if ⟨F(u)−F(v),u−v⟩≥1L∥F(u)−F(v)∥2\langle F(u)-F(v),u-v\rangle\geq\frac{1}{L}\|F(u)-F(v)\|^{2}, for all u,v∈Xu,v\in X. If F=∇ϕF=\nabla\phi for a convex differentiable function ϕ\phi and FF is LL-Lipschitz continuous on an open convex set UU, then FF is 1L\frac{1}{L}-cocoercive on UU [26 Thm. 3.1]. For nonnegative sequences, ut=O(vt)u_{t}=O(v_{t}) means that there exists c>0c>0 such that ut≤cvtu_{t}\leq cv_{t} for all sufficiently large tt.

Problem Formulation

We consider a non-cooperative game Γ\Gamma between NN players. Let player ii, i∈[N]i\in[N], choose its local action from Rdi\mathbb{R}^{d_{i}} and Ji:RD→R\mathcal{J}^{i}:\mathbb{R}^{D}\to\mathbb{R}, with D=∑i=1NdiD=\sum_{i=1}^{N}d_{i}, denote its cost function. We assume the existence of a local constraint set Ai⊆Rdi\mathcal{A}^{i}\subseteq\mathbb{R}^{d_{i}} for each player i∈[N]i\in[N] as well as of a shared coupling constraint set C\mathcal{C} defined by the following system of inequalities:

C={a∈RD:g(a)≤0},(1)\mathcal{C}=\{a\in\mathbb{R}^{D}:g(a)\leq0\}, \tag*{(1)}

where g(a)=[g1(a),…,gm(a)]⊤:RD→Rmg(a)=[g_{1}(a),\ldots,g_{m}(a)]^{\top}:\mathbb{R}^{D}\to\mathbb{R}^{m}, a=[a1,…,aN]⊤∈RDa=[a^{1},\ldots,a^{N}]^{\top}\in\mathbb{R}^{D}, with ai=[ai,1,…,ai,di]⊤a^{i}=[a^{i,1},\ldots,a^{i,d_{i}}]^{\top} being the action of player ii and a−ia^{-i} denoting the joint action of all players except player ii. Thus, the feasible action set in game Γ\Gamma is A∩C\mathcal{A}\cap\mathcal{C}, where A=A1×⋯×AN\mathcal{A}=\mathcal{A}^{1}\times\cdots\times\mathcal{A}^{N} and the coupled action set of agent ii is Ai∩Ci(a−i)\mathcal{A}^{i}\cap\mathcal{C}^{i}(a^{-i}), where Ci(a−i)={ai∈Rdi:g(a)≤0}\mathcal{C}^{i}(a^{-i})=\{a^{i}\in\mathbb{R}^{d_{i}}:g(a)\leq0\}. Throughout this work, we assume that the individual action sets Ai\mathcal{A}^{i}, i∈[N]i\in[N], possess a structure that permits efficient computation of Euclidean projections.

A generalized Nash equilibrium (GNE) in game Γ\Gamma represents a joint action from which no player has any incentive to unilaterally deviate.

Definition 1: A joint action a⋆∈A∩Ca^{\star}\in\mathcal{A}\cap\mathcal{C} in the game Γ=(N,{Ai},{Ji},C)\Gamma=(N,\{\mathcal{A}^{i}\},\{\mathcal{J}^{i}\},\mathcal{C}) with the coupling constraints C\mathcal{C} is called a generalized Nash equilibrium (GNE) if Ji(ai,⋆,a−i,⋆)≤Ji(ai,a−i,⋆)\mathcal{J}^{i}(a^{i,\star},a^{-i,\star})\leq\mathcal{J}^{i}(a^{i},a^{-i,\star}) for any i∈[N]i\in[N] and ai∈Ai∩Ci(a−i,⋆)a^{i}\in\mathcal{A}^{i}\cap\mathcal{C}^{i}(a^{-i,\star}).

We consider convex games as defined below.

Assumption 1: The game under consideration is convex. Namely, (i) for all i∈[N]i\in[N] the cost function Ji(ai,a−i)\mathcal{J}^{i}(a^{i},a^{-i}) is defined on RD\mathbb{R}^{D}, continuously differentiable in aa and convex in aia^{i} for fixed a−ia^{-i}; (ii) the set A\mathcal{A} is closed and convex, gj:RD→Rg_{j}:\mathbb{R}^{D}\to\mathbb{R} is convex and continuously differentiable for any j∈[m]j\in[m], and the set A∩C\mathcal{A}\cap\mathcal{C} is nonempty.

Given the differentiability of the cost functions, we can define the game’s pseudo-gradient mapping below.

References

  1. [1]H. Attouch. Viscosity solutions of minimization problems. SIAM Journal on Optimization, 6(3):769–806, 1996.DOI
  2. [2]A. Bakushinskii and B. T. Polyak. On the solution of variational inequalities. Doklady Akademii Nauk SSSR, 219(5):1038–1041, 1974.
  3. [3]A. Bemporad. NashOpt: A Python library for computing generalized Nash equilibrium and game design. Optimization Methods & Software, 41(3):732–753, 2026. code available at https://github.com/bemporad/nashopt.
  4. [4]A. Bemporad and T. Tatarenko. Learning parametric monotone games, 2026. available on arXiv at https://arxiv.org/abs/2609.02494.
  5. [5]M. Bianchi, G. Belgioioso, and S. Grammatico. Fast generalized Nash equilibrium seeking under partial-decision information. Automatica, 136:110080, 2022.DOI
  6. [6]H. Chen, Y. Li, R. H. Y. Louie, and B. Vucetic. Autonomous demand side management based on energy consumption scheduling and instantaneous load billing: An aggregative game approach. IEEE Transactions on Smart Grid, 5(4):1744–1754, 2014.DOI
  7. [7]K. L. Chung. On a stochastic approximation method. The Annals of Mathematical Statistics, 25(3):463–483, 1954.
  8. [8]S. Dafermos. Traffic equilibrium and variational inequalities. Transportation Science, 14(1):42–54, 1980.DOI
  9. [9]F. Facchinei and C. Kanzow. Generalized Nash equilibrium problems. 4OR, 5(3):173–210, 2007.
  10. [10]F. Facchinei and J.-S. Pang. Finite-Dimensional Variational Inequalities and Complementarity Problems, volume I of Springer Series in Operations Research. Springer, New York, 2003.
  11. [11]A. Fischer, M. Herrich, and K. Schönefeld. Generalized Nash equilibrium problems—recent advances and challenges. Pesquisa Operacional, 34(3):521–558, 2014.DOI
  12. [12]A. J. Hoffman. On approximate solutions of systems of linear inequalities. Journal of Research of the National Bureau of Standards, 49(4):263–265, 1952.
  13. [13]V. V. Kalashnikov and N. I. Kalashnikova. Solving two-level variational inequality. Journal of Global Optimization, 8(3):289–294, 1996.
  14. [14]G. M. Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747–756, 1976.
  15. [15]G. Kotsalis, G. Lan, and T. Li. Simple and optimal methods for stochastic variational inequalities, I: Operator extrapolation. SIAM Journal on Optimization, 32(3):2041–2073, 2022.arxiv.org/abs/2011.02987
  16. [16]A. A. Kulkarni and U. V. Shanbhag. On the variational equilibrium as a refinement of the generalized Nash equilibrium. Automatica, 48(1):45–55, 2012.DOI
  17. [17]S. H. Low. Convex relaxation of optimal power flow—Part I: Formulations and equivalence. IEEE Transactions on Control of Network Systems, 1(1):15–27, 2014.
  18. [18]Z. Ma, D. S. Callaway, and I. A. Hiskens. Decentralized charging control of large populations of plug-in electric vehicles. IEEE Transactions on Control Systems Technology, 21(1):67–78, 2013.
  19. [19]Y. Malitsky. Golden ratio algorithms for variational inequalities. Mathematical Programming, 184(1):383–410, 2020.
  20. [20]Y. Malitsky and K. Mishchenko. Adaptive gradient descent without descent. In Proceedings of the 37th International Conference on Machine Learning (ICML), volume 119 of Proceedings of Machine Learning Research, pages 6702–6712, 2020.
  21. [21]M. Marschner and M. Staudigl. Tikhonov regularized exterior penalty methods for hierarchical variational inequalities. In Proceedings of the 64th IEEE Conference on Decision and Control (CDC), pages 7240–7245, Rio de Janeiro, Brazil, 2025.arxiv.org/abs/2508.20872
  22. [22]D. K. Molzahn, F. Dörfler, H. Sandberg, S. H. Low, S. Chakrabarti, R. Baldick, and J. Lavaei. A survey of distributed optimization and control algorithms for electric power systems. IEEE Transactions on Smart Grid, 8(6):2941–2962, 2017.DOI
  23. [23]Y. Nesterov and L. Scrimali. Solving strongly monotone variational and quasi-variational inequalities. Discrete and Continuous Dynamical Systems – Series A, 31(4):1383–1396, 2011.
  24. [24]A. Olshevsky and J. N. Tsitsiklis. Convergence speed in distributed consensus and averaging. SIAM Journal on Control and Optimization, 48(1):33–55, 2009.DOI
  25. [25]L. Pavel. Distributed GNE seeking under partial-decision information over networks via a doubly-augmented operator splitting approach. IEEE Transactions on Automatic Control, 65(4):1584–1597, 2020.DOI
  26. [26]P. Pérez-Aros and E. Vilches. An enhanced Baillon–Haddad theorem for convex functions defined on convex sets. Applied Mathematics & Optimization, 83(3):2241–2252, 2021.
  27. [27]B. T. Polyak. Introduction to Optimization. Optimization Software, New York, 1987.
  28. [28]L. Ran, H. Li, L. Zheng, J. Li, Z. Li, and J. Hu. Distributed generalized Nash equilibria computation of noncooperative games via novel primal-dual splitting algorithms. IEEE Transactions on Signal and Information Processing over Networks, 10:179–194, 2024.DOI
  29. [29]R. T. Rockafellar. Convex Analysis. Princeton University Press, Princeton, NJ, 1970.
  30. [30]S. Samadi and F. Yousefian. Improved guarantees for optimal Nash equilibrium seeking and bilevel variational inequalities. SIAM Journal on Optimization, 35(1):369–399, 2025.arxiv.org/abs/2307.12511
  31. [31]G. Scutari, D. P. Palomar, F. Facchinei, and J.-S. Pang. Monotone games for cognitive radio systems. In R. Johansson and A. Rantzer, editors, Distributed Decision Making and Control, volume 417 of Lecture Notes in Control and Information Sciences, pages 83–112. Springer, London, 2012.DOI
  32. [32]T. Tatarenko and M. Kamgarpour. Learning generalized Nash equilibria in a class of convex games. IEEE Transactions on Automatic Control, 64(4):1426–1439, 2019.
  33. [33]T. Tatarenko and M. Kamgarpour. Convergence rate of payoff-based generalized Nash equilibrium learning. European Journal of Control, page 101372, 2025.
  34. [34]T. Tatarenko, W. Shi, and A. Nedić. Geometric convergence of gradient play algorithms for distributed Nash equilibrium seeking. IEEE Transactions on Automatic Control, 66(11):5342–5353, 2021.
  35. [35]A. C. Tellidou and A. G. Bakirtzis. Agent-based analysis of capacity withholding and tacit collusion in electricity markets. IEEE Transactions on Power Systems, 22(4):1735–1742, 2007.DOI

Paper details

vlnc:W_fbj2u3kx
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents