betaFeedback

WorksMathematics

Stability Filters for Receding-Horizon Games

Abstract

In receding-horizon games, self-interested players repeatedly solve a finite-horizon generalized Nash equilibrium problem (GNEP) and apply its first-stage actions. Ensuring stability of the resulting closed-loop system, however, is a challenging task that requires careful design of the players' strategies or additional constraints. We propose a stability filter that minimally modifies the variational equilibrium of the finite-horizon GNEP to enforce a prescribed decrease of a quadratic Lyapunov function. For receding-horizon games with linear dynamics, quadratic costs, and polyhedral coupling input constraints, whose associated GNEP is strongly monotone, we show that a filter always exists such that a closed-loop equilibrium exists, the filter is always feasible, does not intervene when the equilibrium already satisfies the decrease condition, and that renders the closed loop globally exponentially stable. Moreover, the filtered strategy is an εε-generalized Nash equilibrium, with epsilonepsilon vanishing exponentially along closed-loop trajectories.

Introduction

Many control problems involve several decision makers that are acting on the same dynamical system while pursuing individual objectives, for instance in demand-side management [1] or the charging of electric vehicles [2]. Coupled through the shared dynamics and the shared constraints, their interaction is naturally modeled as a generalized Nash equilibrium problem (GNEP) [3], [4], whose variational equilibrium (v-GNE) is characterized by a variational inequality with equal multipliers for all players [5], [6].

Receding-horizon games (RHGs) combine this model with the receding-horizon principle of model predictive control (MPC) [7], [8], [9]: at every time step, the players choose a sequence of future control actions by solving a finite-horizon GNEP, parameterized by the current state, and apply the first-stage actions of the resulting equilibrium. RHGs thus describe strategic agents that repeatedly re-plan their strategies in response to the evolving state.

Unlike in standard MPC, where the stage cost is chosen by the designer to optimize all control actions simultaneously, the costs in a RHG belong to the players and reflect their individual interests. Hence, the standard argument of using a single optimal cost as a Lyapunov function fails beyond potential games. Certifying closed-loop stability is of paramount importance for the applicability of RHGs in practice as, for example, agents can destabilize each other through an RHG even when their local dynamics are stable [10].

For strongly monotone games with stable linear dynamics, [10] derives, via dissipativity and monotone operator theory, a sufficient condition in the form of a linear matrix inequality (LMI) that certifies global asymptotic stability, together with guidelines for tuning the cost weights. Other works equip the finite-horizon game with terminal ingredients: [9] obtains an explicit stabilizing terminal cost for linear-quadratic games from an equivalent regulator in an augmented space, and [11], [12] derive conditions on the players’ objectives that guarantee asymptotic stability under terminal constraints or Lyapunov terminal costs via α\alpha-quasi GNEPs. Closed-loop stability under input and state constraints is instead achieved in [13] by introducing in the GNEP a shared linear constraint on the first control moves that forces a certain polyhedral control Lyapunov function to decrease. These approaches either certify stability of a given RHG, with no remedy when the certificate fails, or modify the players’ costs or constraints, which may severely perturb the players’ private interests.

A different mechanism proposed in the MPC literature to ensure stability is the use of stability filters [14], [15], [16] and control barrier and control Lyapunov function based quadratic programs [17], [18], which minimally modify a nominal input to enforce safety or stability.

Contributions. For open-loop Schur stable linear dynamical systems, quadratic costs defining a game with strongly monotone pseudo-gradient, and compact polyhedral coupling constraints, we propose a stability filter that replaces the v-GNE at every time step by the closest feasible joint strategy that guarantees a prescribed decrease of a quadratic Lyapunov function. Since the filtered strategy is in general no longer an equilibrium, a central question is how much strategic optimality is sacrificed for stability. We establish the following properties:

  1. The proposed convex filter is feasible for every state, leaves the v-GNE unchanged whenever it already satisfies the decrease condition, and intervenes by an amount bounded linearly in the distance to the equilibrium.

  2. The filtered closed loop is globally exponentially stable, with a rate prescribed by the designer.

  3. The filtered strategy is an ϵ\epsilon-generalized Nash equilibrium, with ϵ\epsilon bounded by the v-GNE multipliers and the size of the intervention and vanishing exponentially

T. Tatarenko is with the Department of Control Theory and Intelligent Systems, TU Darmstadt, Germany. E-mail: [email protected].

A. Bemporad is with the IMT School for Advanced Studies, Piazza San Francesco 19, Lucca, Italy. E-mail: [email protected].

This 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. along the closed loop. Hence strategic optimality is recovered asymptotically.

Organization. Section II introduces the RHG and the standing assumptions. Section III establishes existence of a closed-loop equilibrium, introduces the stability filter, proves global exponential stability of the filtered closed loop, and analyzes the resulting strategic loss; the main results are summarized in Theorem 4. A numerical example is provided in Section IV and the paper concludes with a discussion in Section V.

Problem Formulation

We consider the linear system

x(t+1)=Ax(t)+Bv(t),t=0,1,2,…,(1)x(t+1)=Ax(t)+Bv(t),\qquad t=0,1,2,\ldots, \tag*{(1)}

where x(t)∈Rnxx(t) \in\mathbb{R}^{n_x} is the system state at time tt and v(t)∈Rnvv(t) \in\mathbb{R}^{n_v} is the command input applied by all NN players. In game-theoretic MPC, v(t)v(t) is obtained from the first stage of the joint finite-horizon strategy, i.e., v(t)=Ξu(t)v(t)=\Xi u(t), where u(t)∈Rnuu(t) \in\mathbb{R}^{n_u} denotes the joint finite-horizon strategy generated at time tt by solving the receding-horizon game, and the matrix Ξ\Xi extracts the first-stage joint action from the finite-horizon strategy.

The strategy u(t)=(ui(t))i∈Nu(t)=(u_i(t))_{i\in\mathcal{N}} is partitioned into the decision blocks indexed by N={1,…,N}\mathcal{N}=\{1,\ldots,N\}. Each player’s block is itself a finite-horizon sequence of length NpN_p,

ui(t)=(ui(0∣t),…,ui(Np−1∣t)),(2)u_i(t)=\left(u_i(0|t),\ldots,u_i(N_p-1|t)\right), \tag*{(2)}

where ui(k∣t)u_i(k|t) is player ii’s action planned at time tt for prediction step kk, and u−i(t)=(uj(t))j≠iu_{-i}(t)=(u_j(t))_{j\ne i} collects the sequences of all other players. The cost of player ii is

Ji(ui,u−i,x)=∑k=0Np−1[ui(k∣t)u−i(k∣t)x(k∣t)]TWi[ui(k∣t)u−i(k∣t)x(k∣t)],(3)J_i(u_i,u_{-i},x)=\sum_{k=0}^{N_p-1} \begin{bmatrix} u_i(k|t)\\ u_{-i}(k|t)\\ x(k|t) \end{bmatrix}^{\mathsf T} \mathcal{W}_i \begin{bmatrix} u_i(k|t)\\ u_{-i}(k|t)\\ x(k|t) \end{bmatrix}, \tag*{(3)}
Wi=[WiiWi,−iKiW−i,iW−i,−iK−iKiTK−iTQi]\mathcal{W}_i= \begin{bmatrix} W_{ii} & W_{i,-i} & K_i\\ W_{-i,i} & W_{-i,-i} & K_{-i}\\ K_i^{\mathsf T} & K_{-i}^{\mathsf T} & Q_i \end{bmatrix}

with Wi⪰0\mathcal{W}_i\succeq0 and Wii=WiiT≻0W_{ii}=W_{ii}^{\mathsf T}\succ0 where the predicted states are generated from the current state x=x(t)=x(0∣t)x=x(t)=x(0|t) as

x(k∣t)=Akx+∑j=0k−1Ak−1−jBu(j∣t),(4)x(k|t)=A^k x+\sum_{j=0}^{k-1}A^{k-1-j}Bu(j|t), \tag*{(4)}

with u(j∣t)=(ui(j∣t))i∈Nu(j|t)=(u_i(j|t))_{i\in\mathcal{N}}. Since the game solved at time tt depends on tt only through x=x(t)x=x(t), we omit the time index in JiJ_i and in all quantities derived from it below, which we treat as functions of a generic state xx.

Given xx and the sequences u−iu_{-i}, each player ii solves

ui∈arg⁡min⁡zi:(zi,u−i)∈Z Ji(zi,u−i,x)∀i∈N,(5)u_i\in\underset{z_i:(z_i,u_{-i})\in Z}{\arg\min}\ J_i(z_i,u_{-i},x)\qquad\forall i\in\mathcal{N}, \tag*{(5)}

where the polyhedral constraint set

Z={u∈Rnu∣Cu≤d, Eu=e}(6)Z=\{u\in\mathbb{R}^{n_u}\mid Cu\le d,\ Eu=e\} \tag*{(6)}

encodes shared linear inequality and, possibly, equality constraints the input variables of all players need to satisfy.

The players’ pseudo-gradient F(u,x)=(Fi(u,x))i∈NF(u,x)=(F_i(u,x))_{i\in\mathcal{N}} stacks the partial gradients Fi(u,x)=∇uiJi(ui,u−i,x)F_i(u,x)=\nabla_{u_i}J_i(u_i,u_{-i},x). As from (4) x(k∣t)x(k|t) is affine in (u,x)(u,x), JiJ_i’s are quadratic and the associated pseudogradient FF is affine, i.e.

F(u,x)=Hu+Gx+h.(7)F(u,x)=Hu+Gx+h. \tag*{(7)}

with HH, GG, hh obtained from the standard condensed representation of (5), and HiH_i, GiG_i, hih_i denoting the corresponding ii-th block row/entry. Note that, for better generality, we retain the constant term hh in the affine representation of the pseudogradient, even though hi=0h_i=0 for each player ii when the game is generated from (3)–(6).

We impose the following standing assumptions.

Assumption 1: The following conditions hold:

  1. ZZ is a nonempty and compact polyhedron;

  1. F(⋅,x)F(\cdot,x) is strongly monotone on ZZ, uniformly in xx, with constant μF>0\mu_F>0, i.e., ⟨F(z1,x)−F(z2,x),z1−z2⟩≥μF∥z1−z2∥2\langle F(z_1,x)-F(z_2,x),z_1-z_2\rangle\ge\mu_F\lVert z_1-z_2\rVert^2 for all z1,z2∈Zz_1,z_2\in Z and all admissible xx.

  1. for every player ii, the cost Ji(⋅,u−i,x)J_i(\cdot,u_{-i},x) is mim_i-strongly convex in the player’s own decision variable, with mi>0m_i>0;

  1. AA is Schur stable.

Remark 1 (Relation between Assumption 1.2 and 1.3): Since Fi(⋅,x)=∇uiJi(⋅,u−i,x)F_i(\cdot,x)=\nabla_{u_i}J_i(\cdot,u_{-i},x), the strong monotonicity inequality of Assumption 1.2 implies Assumption 1.3 with mi≥μFm_i\ge\mu_F, as can be seen by testing the inequality on vectors z1,z2∈Zz_1,z_2\in Z such that z1,−i=z2,−i=0z_{1,-i}=z_{2,-i}=0. We retain it as a separate hypothesis only to allow, for each player, a constant mim_i tighter than μF\mu_F. Such tighter constants directly sharpen the bounds of Theorems 2 and 3 below.

Under Assumption 1, for a given state xx, the variational generalized Nash equilibrium (v-GNE) of the game (5) is characterized by the variational inequality VI(Z,F(⋅,x))VI(Z,F(\cdot,x)), which, by strong monotonicity of FF and Assumption 1.1, admits a unique solution for every xx. We denote the corresponding equilibrium solution mapping by

S(x)=SOL⁡(F(⋅,x),Z).(8)S(x)=\operatorname{SOL}(F(\cdot,x),Z). \tag*{(8)}

Computing S(x)S(x) at every time step is tractable: since F(⋅,x)F(\cdot,x) is affine and strongly monotone and ZZ is a polyhedron, the v-GNE can be computed by centralized projection-type methods for strongly monotone variational inequalities, such as projected gradient [6]. Alternatively, it can be computed in a distributed manner, in which each player updates only its own decision variable, by gradient-play and learning algorithms with convergence rate guarantees for strongly monotone games [19], including settings with coupling constraints [20].

Since FF is affine in xx and strongly monotone in uu, the solution mapping is globally Lipschitz continuous [6 Thm. 2.3]. In particular,

∥S(x)−S(y)∥≤LS∥x−y∥,LS≤∥G∥μF.(9)\lVert S(x)-S(y)\rVert\le L_S\lVert x-y\rVert,\qquad L_S\le\frac{\lVert G\rVert}{\mu_F}. \tag*{(9)}

Stability Filter Design and Guarantees

Closed-loop equilibrium

We first establish existence of an equilibrium of the nominal receding-horizon closed loop. Thus, existence of such an equilibrium does not need to be imposed separately.

Proposition 1: Suppose Assumption 1 holds. Then there exists (xˉ,uˉ)(\bar{x},\bar{u}) satisfying

uˉ=S(xˉ),xˉ=Axˉ+BΞuˉ.(10)\bar{u}=S(\bar{x}),\qquad\bar{x}=A\bar{x}+B\Xi\bar{u}. \tag*{(10)}

Proof: Since AA is Schur, I−AI-A is nonsingular. Define T(u)=S((I−A)−1BΞu)T(u)=S\left((I-A)^{-1}B\Xi u\right). The mapping TT is continuous because SS is (see (9)). Moreover, T(Z)⊆ZT(Z)\subseteq Z as any GNE solution is also feasible.

Since ZZ is nonempty, compact, and convex, Brouwer’s fixed-point theorem implies that there exists uˉ∈Z\bar{u}\in Z such that T(uˉ)=uˉT(\bar{u})=\bar{u}. Define xˉ=(I−A)−1BΞuˉ\bar{x}=(I-A)^{-1}B\Xi\bar{u}. Then uˉ=S(xˉ)\bar{u}=S(\bar{x}) and (I−A)xˉ=BΞuˉ(I-A)\bar{x}=B\Xi\bar{u}, or equivalently xˉ=Axˉ+BΞuˉ\bar{x}=A\bar{x}+B\Xi\bar{u}. This proves (10).

Remark 2: Proposition 1 establishes existence of (xˉ,uˉ)(\bar{x},\bar{u}), but Brouwer’s theorem does not rule out several fixed points of TT. None of the results that follow, namely global feasibility (Proposition 2), nonintervention (Proposition 3), the intervention bound (Proposition 4), closed-loop stability (Theorem 1), or the strategic-loss analysis in Section III-C, use uniqueness of (xˉ,uˉ)(\bar{x},\bar{u}). Each requires only that a single pair satisfying (10) to be fixed once and used consistently as the reference in the filter constraint defined below in (18). When (10) admits multiple solutions, (xˉ,uˉ)(\bar{x},\bar{u}) should therefore be understood as one such pair, selected offline (for instance via Corollary 1 below, when applicable); every guarantee below then holds relative to that fixed choice, uniformly in the online state xx.

Corollary 1 (Sufficient condition for uniqueness): Let

LT=LS∥(I−A)−1BΞ∥,(11)L_T=L_S\left\|(I-A)^{-1}B\Xi\right\|, \tag*{(11)}

with LSL_S as in (9). If LT<1L_T<1, then (xˉ,uˉ)(\bar{x},\bar{u}) in Proposition 1 is the unique pair satisfying (10). Moreover, for any u(0)∈Zu^{(0)}\in Z, the iterates u(n+1)=T(u(n))u^{(n+1)}=T(u^{(n)}) satisfy

∥u(n)−uˉ∥≤LTn∥u(0)−uˉ∥,(12)\left\|u^{(n)}-\bar{u}\right\|\leq L_T^n\left\|u^{(0)}-\bar{u}\right\|, \tag*{(12)}

so uˉ\bar{u}, and hence xˉ\bar{x}, can be computed offline to any desired accuracy.

Proof: For u,v∈Zu,v\in Z, the Lipschitz bound (9) gives

∥T(u)−T(v)∥=∥S((I−A)−1BΞu)−S((I−A)−1BΞv)∥≤LT∥u−v∥.\left\|T(u)-T(v)\right\|=\left\|S\left((I-A)^{-1}B\Xi u\right)-S\left((I-A)^{-1}B\Xi v\right)\right\|\leq L_T\left\|u-v\right\|.

If LT<1L_T<1, TT is a contraction on ZZ, which is complete since it is a compact subset of Rnu\mathbb{R}^{n_u}. The Banach fixed-point theorem then gives a unique fixed point uˉ∈Z\bar{u}\in Z, together with the stated geometric convergence rate of the iterates Tn(u(0))T^n(u^{(0)}). Since xˉ=(I−A)−1BΞuˉ\bar{x}=(I-A)^{-1}B\Xi\bar{u}, it is likewise unique.

Stability filter

Since AA is Schur, for any Q≻0Q\succ0 there exists a unique P≻0P\succ0 satisfying the discrete-time Lyapunov equation

A⊤PA−P=−Q.(13)A^\top P A-P=-Q. \tag*{(13)}

Define V(ξ)=ξ⊤PξV(\xi)=\xi^\top P\xi and

ρA=λmax⁡(P−1/2A⊤PAP−1/2).(14)\rho_A=\lambda_{\max}\left(P^{-1/2}A^\top P A P^{-1/2}\right). \tag*{(14)}

By (13), P−1/2A⊤PAP−1/2=I−P−1/2QP−1/2P^{-1/2}A^\top P A P^{-1/2}=I-P^{-1/2}QP^{-1/2}, hence

0≤ρA=1−λmin⁡(P−1/2QP−1/2)<1(15)0\leq\rho_A=1-\lambda_{\min}\left(P^{-1/2}QP^{-1/2}\right)<1 \tag*{(15)}

and

V(Aξ)≤ρAV(ξ)∀ξ.(16)V(A\xi)\leq\rho_A V(\xi)\qquad\forall\xi. \tag*{(16)}

Choose a prescribed contraction factor

ρ∈[ρA,1).(17)\rho\in[\rho_A,1). \tag*{(17)}

Throughout, xˉ\bar{x} denotes the first component of a fixed pair (xˉ,uˉ)(\bar{x},\bar{u}) satisfying (10), in the sense of Remark 2. We define the stability-filtered strategy by

S~(x)=arg min⁡u∈Z 12∥u−S(x)∥R2\widetilde{S}(x)=\underset{u\in Z}{\operatorname{arg\,min}}\ \frac{1}{2}\left\|u-S(x)\right\|_{R}^{2}
s.t.V(Ax+BΞu−xˉ)≤ρV(x−xˉ),(18)\text{s.t.}\quad V(Ax+B\Xi u-\bar{x})\leq\rho V(x-\bar{x}), \tag*{(18)}

where R≻0R\succ0.

The filter therefore selects the feasible strategy closest to the nominal v-GNE while enforcing a prescribed Lyapunov contraction defined by (17).

Remark 3: The constant ρA=∥P1/2AP−1/2∥2\rho_A=\left\|P^{1/2}AP^{-1/2}\right\|^2 depends on QQ through PP and always satisfies ρA≥ρ(A)2\rho_A\geq\rho(A)^2, where ρ(A)\rho(A) is the spectral radius of AA. Conversely, for every ε>0\varepsilon>0 there exists P≻0P\succ0 with ∥P1/2AP−1/2∥≤ρ(A)+ε\left\|P^{1/2}AP^{-1/2}\right\|\leq\rho(A)+\varepsilon, and Q=P−A⊤PA≻0Q=P-A^\top PA\succ0 then yields ρA≤(ρ(A)+ε)2\rho_A\leq(\rho(A)+\varepsilon)^2. Hence a suitable choice of QQ brings ρA\rho_A arbitrarily close to ρ(A)2\rho(A)^2, which enlarges the admissible range of contraction factors in (17).

We next establish the basic properties of the filter. We show that it is feasible for every state (Proposition 2), that it leaves the v-GNE unchanged whenever the latter already satisfies the contraction condition (Proposition 3), and that its deviation from the v-GNE is bounded linearly in ∥x−xˉ∥\left\|x-\bar{x}\right\| (Proposition 4). Building on these results, Theorem 1 proves global exponential stability of the filtered closed loop, and Corollary 2 shows that the intervention vanishes exponentially along it.

Proposition 2: Under Assumption 1, the stability filter (18) is feasible for every x∈Rnxx\in\mathbb{R}^{n_x}.

Proof: Consider the constant candidate u=uˉu=\bar{u}. By Proposition 1, uˉ=S(xˉ)∈Z\bar{u}=S(\bar{x})\in Z. Moreover,

Ax+BΞuˉ−xˉ=Ax+BΞuˉ−(Axˉ+BΞuˉ)Ax+B\Xi\bar{u}-\bar{x}=Ax+B\Xi\bar{u}-(A\bar{x}+B\Xi\bar{u})
=A(x−xˉ).=A(x-\bar{x}).

Consequently,

V(Ax+BΞuˉ−xˉ)=V(A(x−xˉ))≤ρAV(x−xˉ)V(Ax+B\Xi\bar{u}-\bar{x})=V(A(x-\bar{x}))\leq\rho_A V(x-\bar{x})
≤ρV(x−xˉ).\leq\rho V(x-\bar{x}).

Thus uˉ\bar{u} is feasible for (18) for every xx.

Proposition 3: If the nominal equilibrium strategy satisfies

V(Ax+BΞS(x)−xˉ)≤ρV(x−xˉ),(19)V(Ax+B\Xi S(x)-\bar{x})\leq\rho V(x-\bar{x}), \tag*{(19)}

then S~(x)=S(x)\widetilde{S}(x)=S(x).

Proof: If (19) holds, then S(x)S(x) is feasible for (18). The objective in (18) is nonnegative and equals zero at u=S(x)u=S(x). Since R≻0R\succ0, this point is the unique optimizer.

Proposition 4: Let

δ(x)=S~(x)−S(x).(20)\delta(x)=\widetilde{S}(x)-S(x). \tag*{(20)}

Then ∥δ(x)∥≤Cδ∥x−xˉ∥\|\delta(x)\|\leq C_\delta\|x-\bar{x}\| for every xx, where one may take

Cδ=λmax⁡(R)λmin⁡(R)LS≤λmax⁡(R)λmin⁡(R)∥G∥μF.(21)C_\delta=\sqrt{\frac{\lambda_{\max}(R)}{\lambda_{\min}(R)}}L_S\leq\sqrt{\frac{\lambda_{\max}(R)}{\lambda_{\min}(R)}}\frac{\|G\|}{\mu_F}. \tag*{(21)}

Proof: Since uˉ\bar{u} is feasible for (18), optimality of S~(x)\widetilde{S}(x) gives

∥S~(x)−S(x)∥R≤∥uˉ−S(x)∥R.\|\widetilde{S}(x)-S(x)\|_R\leq\|\bar{u}-S(x)\|_R.

Since uˉ=S(xˉ)\bar{u}=S(\bar{x}), the Lipschitz property (9) yields

∥uˉ−S(x)∥≤LS∥x−xˉ∥.\|\bar{u}-S(x)\|\leq L_S\|x-\bar{x}\|.

Using norm equivalence,

∥δ(x)∥≤λmax⁡(R)λmin⁡(R)LS∥x−xˉ∥,\|\delta(x)\|\leq\sqrt{\frac{\lambda_{\max}(R)}{\lambda_{\min}(R)}}L_S\|x-\bar{x}\|,

which proves the claim.

Theorem 1: Consider the filtered closed loop

x(t+1)=Ax(t)+BΞS~(x(t)),(22)x(t+1)=Ax(t)+B\Xi\widetilde{S}(x(t)), \tag*{(22)}

initialized at x(0)=x0x(0)=x_0. Then xˉ\bar{x} is globally exponentially stable. More precisely,

∥x(t)−xˉ∥≤λmax⁡(P)λmin⁡(P)ρt/2∥x0−xˉ∥.(23)\|x(t)-\bar{x}\|\leq\sqrt{\frac{\lambda_{\max}(P)}{\lambda_{\min}(P)}}\rho^{t/2}\|x_0-\bar{x}\|. \tag*{(23)}

Proof: The contraction inequality V(x(t+1)−xˉ)≤ρV(x(t)−xˉ)V(x(t+1)-\bar{x})\leq\rho V(x(t)-\bar{x}) follows directly from the constraint in (18). Hence, iteration yields V(x(t)−xˉ)≤ρtV(x0−xˉ)V(x(t)-\bar{x})\leq\rho^tV(x_0-\bar{x}). Finally,

λmin⁡(P)∥ξ∥2≤V(ξ)≤λmax⁡(P)∥ξ∥2\lambda_{\min}(P)\|\xi\|^2\leq V(\xi)\leq\lambda_{\max}(P)\|\xi\|^2

gives (23).

Corollary 2: Along the filtered closed loop,

∥S~(x(t))−S(x(t))∥=O(ρt/2).(24)\|\widetilde{S}(x(t))-S(x(t))\|=O(\rho^{t/2}). \tag*{(24)}

More precisely,

∥S~(x(t))−S(x(t))∥≤Cδλmax⁡(P)λmin⁡(P)ρt/2∥x0−xˉ∥.(25)\|\widetilde{S}(x(t))-S(x(t))\|\leq C_\delta\sqrt{\frac{\lambda_{\max}(P)}{\lambda_{\min}(P)}}\rho^{t/2}\|x_0-\bar{x}\|. \tag*{(25)}

Proof: The result follows immediately from Proposition 4 and Theorem 1.

Remark 4: Corollary 2 measures the intervention in the space of strategies only. Closeness of S~(x)\widetilde{S}(x) to S(x)S(x) does not by itself imply that S~(x)\widetilde{S}(x) is close to an equilibrium in the strategic sense: equilibrium is characterized by the players’ unilateral optimality, i.e., by comparing Ji(S~(x),x)J_i(\widetilde{S}(x),x) with the best cost player ii can achieve against the filtered strategies S~−i(x)\widetilde{S}_{-i}(x) of the others, rather than by the cost incurred at the v-GNE. Moreover, when coupling constraints are active at S(x)S(x), a deviation δ\delta may induce a regret of first order in ∥δ∥\|\delta\|, whose magnitude is governed by the associated multipliers, as opposed to the second-order effect one would expect at an unconstrained equilibrium. This loss of strategic optimality is quantified in the following subsection (Theorems 2 and 3).

Strategic loss induced by stability filtering

By the construction and results above, the filtered strategy S~(x)\widetilde{S}(x) is feasible for the original game and renders the closed loop globally exponentially stable (Theorem 1). However, whenever the filter intervenes, S~(x)\widetilde{S}(x) need not itself be a GNE. What remains is therefore to characterize its optimality in terms of the players’ cost functions JiJ_i, i.e., to quantify the loss of strategic optimality incurred for the sake of stability.

For a feasible strategy u∈Zu\in Z, define the maximum unilateral regret

ϵ(u,x)=max⁡i{Ji(ui,u−i,x)−min⁡zi:(zi,u−i)∈ZJi(zi,u−i,x)}.(26)\epsilon(u,x)=\max_i\left\{J_i(u_i,u_{-i},x)-\min_{z_i:(z_i,u_{-i})\in Z}J_i(z_i,u_{-i},x)\right\}. \tag*{(26)}

Thus uu is an ϵ\epsilon-GNE whenever its maximum unilateral regret is bounded by ϵ\epsilon.

For u⋆=S(x)u^\star=S(x), the v-GNE optimality conditions imply the existence of common multipliers λ≥0\lambda\geq0 and ν\nu satisfying (see, e.g., [6, Thm. 12.1)

F(u⋆,x)+CTλ+ETν=0,(27)F(u^\star,x)+C^\mathsf{T}\lambda+E^\mathsf{T}\nu=0, \tag*{(27)}
Cu⋆≤d,Eu⋆=e,(28)Cu^\star\leq d,\qquad Eu^\star=e, \tag*{(28)}
λT(d−Cu⋆)=0.(29)\lambda^\mathsf{T}(d-Cu^\star)=0. \tag*{(29)}

We first establish that the multipliers required in the subsequent analysis can always be selected locally bounded.

Lemma 1: Under Assumption 1, for every compact set X⊂Rnx\mathcal{X}\subset\mathbb{R}^{n_x} there exists a constant Mλ(X)<∞M_\lambda(\mathcal{X})<\infty such that, for every x∈Xx\in\mathcal{X}, there exists a KKT multiplier pair (λ(x),ν(x))(\lambda(x),\nu(x)) associated with S(x)S(x) satisfying

∥λ(x)∥≤Mλ(X).(30)\|\lambda(x)\|\leq M_\lambda(\mathcal{X}). \tag*{(30)}

In particular, the inequality multipliers admit a locally bounded selection in a neighborhood of xˉ\bar{x}.

The proof, which relies on Hoffman's error bound for linear systems [21], is given in Appendix I.

Theorem 2: Let u⋆=S(x)u^\star=S(x), u~=S~(x)\tilde{u}=\widetilde{S}(x), and δ=u~−u⋆\delta=\tilde{u}-u^\star. Under Assumption 1, let (λ(x),ν(x))(\lambda(x),\nu(x)) be any KKT multiplier pair associated with u⋆u^\star. Then

ϵ(u~,x)≤λ(x)T(d−Cu~)+max⁡i∥(Hδ)i∥22mi\epsilon(\tilde{u},x)\leq\lambda(x)^\mathsf{T}(d-C\tilde{u})+\max_i\frac{\|(H\delta)_i\|^2}{2m_i}
=−λ(x)TCδ+max⁡i∥(Hδ)i∥22mi.(31)=-\lambda(x)^\mathsf{T}C\delta+\max_i\frac{\|(H\delta)_i\|^2}{2m_i}. \tag*{(31)}

Proof: Fix a player ii and any feasible unilateral deviation ziz_i, i.e., z=(zi,u~−i)∈Zz=(z_i,\tilde{u}_{-i})\in Z. By strong convexity of JiJ_i with respect to its own decision variable,

Ji(u~i,u~−i,x)−Ji(zi,u~−i,x)≤Fi(u~,x)T(u~i−zi)−mi2∥u~i−zi∥2.(32)J_i(\tilde{u}_i,\tilde{u}_{-i},x)-J_i(z_i,\tilde{u}_{-i},x)\leq F_i(\tilde{u},x)^\mathsf{T}(\tilde{u}_i-z_i)-\frac{m_i}{2}\|\tilde{u}_i-z_i\|^2. \tag*{(32)}

Since FF is affine, F(u~,x)=F(u⋆,x)+HδF(\tilde{u},x)=F(u^\star,x)+H\delta. Thus, by the v-GNE stationarity condition (see (27)),

F(u~,x)=−CTλ−ETν+Hδ.(33)F(\tilde{u},x)=-C^{\mathsf T}\lambda-E^{\mathsf T}\nu+H\delta. \tag*{(33)}

Let w=u~−zw=\tilde{u}-z. Since u~\tilde{u} and zz differ only in player ii’s decision block, Fi(u~,x)T(u~i−zi)=F(u~,x)TwF_i(\tilde{u},x)^{\mathsf T}(\tilde{u}_i-z_i)=F(\tilde{u},x)^{\mathsf T}w. Furthermore, both u~\tilde{u} and zz satisfy the equality constraints, and hence Ew=0Ew=0. Therefore, by (31)

F(u~,x)Tw=−λTCw+(Hδ)Tw≤λT(d−Cu~)+(Hδ)Tw,(34)\begin{aligned} F(\tilde{u},x)^{\mathsf T}w &=-\lambda^{\mathsf T}Cw+(H\delta)^{\mathsf T}w\\ &\leq\lambda^{\mathsf T}(d-C\tilde{u})+(H\delta)^{\mathsf T}w, \tag*{(34)} \end{aligned}

since Cz≤dCz\leq d and −λTCw=λT(Cz−Cu~)-\lambda^{\mathsf T}Cw=\lambda^{\mathsf T}(Cz-C\tilde{u}). Substitution of (32) into (30) gives

Ji(u~i,u~−i,x)−Ji(zi,u~−i,x)≤λT(d−Cu~)+(Hδ)iT(u~i−zi)−mi2∥u~i−zi∥2≤λT(d−Cu~)+∥(Hδ)i∥22mi.(35)\begin{aligned} J_i(\tilde{u}_i,\tilde{u}_{-i},x)-J_i(z_i,\tilde{u}_{-i},x) &\leq\lambda^{\mathsf T}(d-C\tilde{u})+(H\delta)_i^{\mathsf T}(\tilde{u}_i-z_i)-\frac{m_i}{2}\lVert\tilde{u}_i-z_i\rVert^2\\ &\leq\lambda^{\mathsf T}(d-C\tilde{u})+\frac{\lVert(H\delta)_i\rVert^2}{2m_i}. \tag*{(35)} \end{aligned}

where we used (Hδ)iT(u~i−zi)−mi2∥u~i−zi∥2≤∥(Hδ)i∥22mi(H\delta)_i^{\mathsf T}(\tilde{u}_i-z_i)-\frac{m_i}{2}\lVert\tilde{u}_i-z_i\rVert^2\leq\frac{\lVert(H\delta)_i\rVert^2}{2m_i}. Since the inequality (33) holds for every feasible unilateral deviation, taking the supremum over ziz_i and then the maximum over players gives

ϵ(u~,x)≤λ(x)T(d−Cu~)+max⁡i∥(Hδ)i∥22mi.\epsilon(\tilde{u},x)\leq\lambda(x)^{\mathsf T}(d-C\tilde{u})+\max_i\frac{\lVert(H\delta)_i\rVert^2}{2m_i}.

Finally, λT(d−Cu⋆)=0\lambda^{\mathsf T}(d-Cu^\star)=0 implies

λT(d−Cu~)=λT(d−Cu⋆)−λTC(u~−u⋆)=−λTCδ,\lambda^{\mathsf T}(d-C\tilde{u})=\lambda^{\mathsf T}(d-Cu^\star)-\lambda^{\mathsf T}C(\tilde{u}-u^\star)=-\lambda^{\mathsf T}C\delta,

which proves (29). ■

Remark 5: The bound (29) separates the strategic loss into two qualitatively different contributions:

ϵ(u~,x)≤λ(x)T(d−Cu~)⏟constraint-release loss+max⁡i∥(Hδ)i∥22mi⏟stationarity perturbation.(36)\epsilon(\tilde{u},x)\leq\underbrace{\lambda(x)^{\mathsf T}(d-C\tilde{u})}_{\text{constraint-release loss}}+\underbrace{\max_i\frac{\lVert(H\delta)_i\rVert^2}{2m_i}}_{\text{stationarity perturbation}}. \tag*{(36)}

The second term is quadratic in the stability intervention δ\delta. In contrast, moving away from an inequality that is active at the nominal v-GNE and has a positive equilibrium multiplier can generate a first-order loss. Thus, the potentially first-order strategic effect of stability filtering is entirely associated with releasing positively priced active constraints.

Theorem 3. Under Assumption 1, for every initial condition x0∈Rnxx_0\in\mathbb{R}^{n_x} there exists a constant Cϵ(x0)>0C_\epsilon(x_0)>0 such that, along the filtered closed loop (22) initialized at x(0)=x0x(0)=x_0,

ϵ(S~(x(t)),x(t))≤Cϵ(x0)∥x(t)−xˉ∥,t=0,1,2,…(37)\epsilon(\tilde{S}(x(t)),x(t))\leq C_\epsilon(x_0)\lVert x(t)-\bar{x}\rVert,\qquad t=0,1,2,\ldots \tag*{(37)}

Consequently, ϵ(t)=ϵ(S~(x(t)),x(t))=O(ρt/2)\epsilon(t)=\epsilon(\tilde{S}(x(t)),x(t))=O(\rho^{t/2}), for every x0x_0. In particular, lim⁡t→∞ϵ(t)=0\lim_{t\to\infty}\epsilon(t)=0 regardless of the initial condition.

Proof: Fix x0x_0 and define the sublevel set

Xx0={ξ∈Rnx∣V(ξ−xˉ)≤V(x0−xˉ)}.(38)\mathcal{X}_{x_0}=\{\xi\in\mathbb{R}^{n_x}\mid V(\xi-\bar{x})\leq V(x_0-\bar{x})\}. \tag*{(38)}

Since VV is a positive-definite quadratic, Xx0\mathcal{X}_{x_0} is a compact ellipsoid, and every ξ∈Xx0\xi\in\mathcal{X}_{x_0} satisfies

∥ξ−xˉ∥≤R(x0):=λmax⁡(P)λmin⁡(P)∥x0−xˉ∥.(39)\lVert\xi-\bar{x}\rVert\leq R(x_0):=\sqrt{\frac{\lambda_{\max}(P)}{\lambda_{\min}(P)}}\lVert x_0-\bar{x}\rVert. \tag*{(39)}

By the contraction inequality, V(x(t+1)−xˉ)≤ρV(x(t)−xˉ)≤V(x(t)−xˉ)V(x(t+1)-\bar{x})\leq\rho V(x(t)-\bar{x})\leq V(x(t)-\bar{x}) along the filtered closed loop; since x0∈Xx0x_0\in\mathcal{X}_{x_0} trivially, induction on tt gives x(t)∈Xx0x(t)\in\mathcal{X}_{x_0} for every t=0,1,2,…t=0,1,2,\ldots, so Xx0\mathcal{X}_{x_0} contains the entire trajectory.

By Lemma 1 applied to the compact set Xx0\mathcal{X}_{x_0}, there is a valid KKT multiplier selection with

∥λ(x)∥≤Mλ(x0),x∈Xx0,\lVert\lambda(x)\rVert\leq M_\lambda(x_0),\qquad x\in\mathcal{X}_{x_0},

where Mλ(x0)=Mλ(Xx0)M_\lambda(x_0)=M_\lambda(\mathcal{X}_{x_0}) is a finite constant depending on x0x_0. By Proposition 4, ∥δ(x)∥≤Cδ∥x−xˉ∥\lVert\delta(x)\rVert\leq C_\delta\lVert x-\bar{x}\rVert for every xx. Using Theorem 2,

ϵ(S~(x),x)≤−λ(x)TCδ(x)+max⁡i∥(Hδ(x))i∥22mi≤Mλ(x0)∥C∥Cδ∥x−xˉ∥+cH∥δ(x)∥2,(40)\epsilon(\tilde{S}(x),x)\leq-\lambda(x)^{\mathsf T}C\delta(x)+\max_i\frac{\lVert(H\delta(x))_i\rVert^2}{2m_i} \leq M_\lambda(x_0)\lVert C\rVert C_\delta\lVert x-\bar{x}\rVert+c_H\lVert\delta(x)\rVert^2, \tag*{(40)}

where cH=max⁡i∥Hi∥22mic_H=\max_i\frac{\lVert H_i\rVert^2}{2m_i}. Therefore, for every x∈Xx0x\in\mathcal{X}_{x_0},

ϵ(S~(x),x)≤Mλ(x0)∥C∥Cδ∥x−xˉ∥+cHCδ2∥x−xˉ∥2.(41)\epsilon(\tilde{S}(x),x)\leq M_\lambda(x_0)\lVert C\rVert C_\delta\lVert x-\bar{x}\rVert+c_HC_\delta^2\lVert x-\bar{x}\rVert^2. \tag*{(41)}

By (37), ∥x−xˉ∥≤R(x0)\lVert x-\bar{x}\rVert\leq R(x_0) for every x∈Xx0x\in\mathcal{X}_{x_0}. Thus,

cHCδ2∥x−xˉ∥2≤cHCδ2R(x0)∥x−xˉ∥,x∈Xx0.c_HC_\delta^2\lVert x-\bar{x}\rVert^2\leq c_HC_\delta^2R(x_0)\lVert x-\bar{x}\rVert,\qquad x\in\mathcal{X}_{x_0}.

Substituting into (39) gives, for every x∈Xx0x\in\mathcal{X}_{x_0} and in particular for every x(t)x(t),

ϵ(S~(x),x)≤[Mλ(x0)∥C∥Cδ+cHCδ2R(x0)]⏟=:Cϵ(x0)∥x−xˉ∥,\epsilon(\tilde{S}(x),x)\leq\underbrace{\left[M_\lambda(x_0)\lVert C\rVert C_\delta+c_HC_\delta^2R(x_0)\right]}_{=:C_\epsilon(x_0)}\lVert x-\bar{x}\rVert,

which proves (35).

Finally, by Theorem 1,

∥x(t)−xˉ∥≤λmax⁡(P)λmin⁡(P)ρt/2∥x0−xˉ∥,\lVert x(t)-\bar{x}\rVert\leq\sqrt{\frac{\lambda_{\max}(P)}{\lambda_{\min}(P)}}\rho^{t/2}\lVert x_0-\bar{x}\rVert,

so combining with (35),

ϵ(t)≤Cϵ(x0)λmax⁡(P)λmin⁡(P)ρt/2∥x0−xˉ∥,\epsilon(t)\leq C_\epsilon(x_0)\sqrt{\frac{\lambda_{\max}(P)}{\lambda_{\min}(P)}}\rho^{t/2}\lVert x_0-\bar{x}\rVert,

and therefore ϵ(t)→0\epsilon(t)\to0, for every x0x_0. ■

Main result

We now collect the results of this section into a single statement, which constitutes the main result of the paper: the stability filter renders the receding-horizon game globally exponentially stable while preserving strategic optimality asymptotically.

Theorem 4. Suppose Assumption 1 holds. Then the following statements are true.

  1. Equilibrium: there exists (xˉ,uˉ)(\bar{x},\bar{u}) with uˉ=S~(xˉ)\bar{u}=\tilde{S}(\bar{x}) and xˉ=Aˉxˉ+Bˉuˉ\bar{x}=\bar{A}\bar{x}+\bar{B}\bar{u}.

  1. Global feasibility: the filtered strategy S~(x)\widetilde{S}(x) defined in (18) exists for every x∈Rnxx \in\mathbb{R}^{n_x}.

  1. Exact nonintervention: if S(x)S(x) satisfies (19), then S~(x)=S(x)\widetilde{S}(x) = S(x).

  1. Global exponential stability: for every x0∈Rnxx_0 \in\mathbb{R}^{n_x}, the trajectory of the filtered closed loop x(t+1)=Ax(t)+BΞS~(x(t))x(t+1)=Ax(t)+B\Xi\widetilde{S}(x(t)), x(0)=x0x(0)=x_0, satisfies

∥x(t)−xˉ∥≤λmax⁡(P)λmin⁡(P)ρt/2∥x0−xˉ∥,t≥0.\lVert x(t)-\bar{x}\rVert\le\sqrt{\frac{\lambda_{\max}(P)}{\lambda_{\min}(P)}}\rho^{t/2}\lVert x_0-\bar{x}\rVert,\qquad t\ge0.
  1. Strategic recovery: for every x0∈Rnxx_0 \in\mathbb{R}^{n_x}, the maximum unilateral regret along the filtered closed loop satisfies ϵ(t)=O(ρt/2)\epsilon(t)=O(\rho^{t/2}); in particular, lim⁡t→∞ϵ(t)=0\lim_{t\to\infty}\epsilon(t)=0.

Numerical example

We consider a random system (1) with nx=2n_x=2 and nv=3n_v=3, whose matrix AA has eigenvalues 0.950.95 and 0.88440.8844. Each of the N=3N=3 players controls one input over the horizon Np=5N_p=5. After reordering the stage vector in (3) as [v(k∣t)⊤ x(k∣t)⊤]⊤[v(k|t)^\top\ x(k|t)^\top]^\top, player ii’s weight is Wi=LiLi⊤+eiei⊤W_i=L_iL_i^\top+e_ie_i^\top, where Li∈R5×2L_i\in\mathbb{R}^{5\times2} has random Gaussian entries and eie_i is the iith unit vector. The low-rank term couples each player’s input to the state in a selfish way. The set ZZ contains the shared constraints ∣v1(k∣t)+v2(k∣t)∣≤0.4\lvert v_1(k|t)+v_2(k|t)\rvert\le0.4 and ∣v1(k∣t)+v3(k∣t)∣≤0.3\lvert v_1(k|t)+v_3(k|t)\rvert\le0.3 and the local bounds ∣vj(k∣t)∣≤1\lvert v_j(k|t)\rvert\le1 at all prediction steps. The game is strongly monotone with μF=0.410\mu_F=0.410 and 3.10≤mi≤5.423.10\le m_i\le5.42. Since h=0h=0 and 0∈Z0\in Z, (xˉ,uˉ)=(0,0)(\bar{x},\bar{u})=(0,0) satisfies (10). We set Q=IQ=I in (13), which gives ρA=0.9680\rho_A=0.9680, and take ρ=ρA+0.1(1−ρA)=0.9712\rho=\rho_A+0.1(1-\rho_A)=0.9712 and R=IR=I. At each tt, S(x(t))S(x(t)) is computed with the QP-based method of [22] in NashOpt [23]; when (19) fails, (18) is solved as a second-order cone program by Clarabel [24].

Figure 1 shows the closed loop from x0=[1.9518 −2.2783]⊤x_0=[1.9518\ -2.2783]^\top. During the transient 0≤t≤50\le t\le5, the v-GNE alone would increase VV; the filter intervenes at these steps, with ∥Ξδ(x(t))∥∞\lVert\Xi\delta(x(t))\rVert_\infty decreasing from 0.500.50 to 0.030.03, in agreement with Corollary 2. For t≥6t\ge6, S(x(t))S(x(t)) satisfies (19) and is applied unchanged (Proposition 3). As guaranteed by Theorem 1, V(x(t+1))≤ρV(x(t))V(x(t+1))\le\rho V(x(t)) at every step, and V(x(20))≈0V(x(20))\approx0 (Figure 2(a)). During the transient, the v-GNE lies on the edge v1+v2=−0.4v_1+v_2=-0.4 of ZZ, while the filter moves the applied input away from it and onto the edge v1+v3=0.3v_1+v_3=0.3 for 1≤t≤31\le t\le3 (Figure 2(b)).

Figure 1. Closed-loop states (top) and inputs (bottom). Solid: applied input v(t)=S~(x(t))v(t)=\widetilde{S}(x(t)). Dotted: first move Sˉ(x(t))\bar{S}(x(t)) of the v-GNE. Dashed: bounds. The red ellipse marks the steps where the filter intervenes.

Figure 2. (a) Closed-loop trajectory with level sets of VV through x(t)x(t) every 4 steps. (b) v1+v2v_1+v_2 versus v1+v3v_1+v_3 for the v-GNE first move (crosses) and the applied input (circles), with the bounds of the shared constraints (dashed). Red arrows: corrections applied by the filter.

Conclusion

In this paper, we have proposed the use of a control-input filtering mechanism to ensure desired behavior and stability of a given constrained closed-loop game-theoretic MPC system. We have illustrated via a simple numerical example the effectiveness of the approach in guiding the system towards the desired equilibrium while satisfying all constraints. Future work will focus on extending the methodology to control unstable open-loop systems, handling state-constraints, and solving set-point tracking problems.

Proof of Lemma 1

The proof relies on the following classical error bound for linear systems.

Lemma 2 (Hoffman [21]). Let A∈Rm×nA\in\mathbb{R}^{m\times n} and B∈Rk×nB\in\mathbb{R}^{k\times n}. There exists cA,B≥0c_{A,B}\ge0, depending only on AA and BB, such that for all a∈Rma\in\mathbb{R}^m and b∈Rkb\in\mathbb{R}^k for which the polyhedron

P(a,b)={y∈Rn∣Ay≤a, By=b}P(a,b)=\{y\in\mathbb{R}^n\mid Ay\le a,\ By=b\}

is nonempty, and for all y0∈Rny_0\in\mathbb{R}^n,

dist⁡(y0,P(a,b))≤cA,B(∥Ay0−a∥++∥By0−b∥),\operatorname{dist}(y_0,P(a,b))\le c_{A,B}(\lVert Ay_0-a\rVert_+ + \lVert By_0-b\rVert),

where (⋅)+(\cdot)_+ denotes the componentwise positive part.

Proof of Lemma 1: Fix x∈Xx\in\mathcal{X} and write g=F(S(x),x)g=F(S(x),x) and A={j∣CjS(x)=dj}\mathcal{A}=\{j\mid C_jS(x)=d_j\} for the active set. Consider

Λ(x)={(λ,ν)∣λ≥0, λj=0 (j∉A), C⊤λ+E⊤ν=−g}.\Lambda(x)=\{(\lambda,\nu)\mid\lambda\geq0,\ \lambda_j=0\ (j\notin\mathcal{A}),\ C^{\top}\lambda+E^{\top}\nu=-g\}.

Every (λ,ν)∈Λ(x)(\lambda,\nu)\in\Lambda(x) is a KKT multiplier pair associated with S(x)S(x): (27) and λ≥0\lambda\geq0 hold by definition, (28) holds since S(x)∈ZS(x)\in Z, and (29) holds since λj=0\lambda_j=0 whenever dj−CjS(x)>0d_j-C_jS(x)>0. Conversely, since ZZ is polyhedral, the KKT conditions (27) are necessary for S(x)S(x) to solve VI(Z,F(⋅,x))VI(Z,F(\cdot,x)) [6], so a KKT pair exists, and by (29) it lies in Λ(x)\Lambda(x). Hence Λ(x)≠∅\Lambda(x)\ne\varnothing.

With y=(λ,ν)y=(\lambda,\nu), the set Λ(x)\Lambda(x) has the form P(a,b)P(a,b) of Lemma 2 with

A=[−I0],a=0,BA=[C⊤E⊤IAc0],b=[−g0].A=\begin{bmatrix}-I&0\end{bmatrix},\quad a=0,\quad B_{\mathcal{A}}=\begin{bmatrix}C^{\top}&E^{\top}\\ I_{\mathcal{A}^{c}}&0\end{bmatrix},\quad b=\begin{bmatrix}-g\\0\end{bmatrix}.

where IAcI_{\mathcal{A}^{c}} collects the rows of the identity indexed by j∉Aj\notin\mathcal{A}. The matrices AA and BAB_{\mathcal{A}} depend only on CC, EE, and A\mathcal{A}; the state xx enters only through the right-hand side bb. Let cA=cA,BAc_{\mathcal{A}}=c_{A,B_{\mathcal{A}}} be the corresponding Hoffman constant.

At y0=0y_0=0 the inequality constraints are satisfied, (Ay0−a)+=0(Ay_0-a)_+=0, and the equality residual is ∥BAy0−b∥=∥g∥\lVert B_{\mathcal{A}}y_0-b\rVert=\lVert g\rVert. Lemma 2 therefore gives

dist⁡(0,Λ(x))≤cA∥g∥.\operatorname{dist}(0,\Lambda(x))\leq c_{\mathcal{A}}\lVert g\rVert.

Since Λ(x)\Lambda(x) is nonempty and closed, it contains an element (λ(x),ν(x))(\lambda(x),\nu(x)) of minimal norm, which is a KKT multiplier pair by Step 1 and satisfies

∥λ(x)∥≤∥(λ(x),ν(x))∥=dist⁡(0,Λ(x))≤cA∥F(S(x),x)∥.\lVert\lambda(x)\rVert\leq\lVert(\lambda(x),\nu(x))\rVert=\operatorname{dist}(0,\Lambda(x))\leq c_{\mathcal{A}}\lVert F(S(x),x)\rVert.

The active set A\mathcal{A} varies with xx, but it is a subset of the finitely many constraint indices. Hence cZ=max⁡AcA<∞c_Z=\max_{\mathcal{A}}c_{\mathcal{A}}<\infty is independent of xx, and

∥λ(x)∥≤cZ∥F(S(x),x)∥.(42)\lVert\lambda(x)\rVert\leq c_Z\lVert F(S(x),x)\rVert. \tag*{(42)}

Finally, F(S(x),x)F(S(x),x) is continuous with respect to xx (see (9)), hence bounded on the compact set X\mathcal{X}, which gives (30) with Mλ=cZmax⁡x∈X∥F(S(x),x)∥M_\lambda=c_Z\max_{x\in\mathcal{X}}\lVert F(S(x),x)\rVert.

References

References

  1. [1]H. Chen, Y. Li, R. H. 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, vol. 5, no. 4, pp. 1744–1754, 2014.DOI
  2. [2]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, vol. 21, no. 1, pp. 67–78, 2011.
  3. [3]F. Facchinei and C. Kanzow, “Generalized Nash equilibrium problems,” 4OR, vol. 5, no. 3, pp. 173–210, 2007.
  4. [4]A. Fischer, M. Herrich, and K. Schönfeld, “Generalized Nash equilibrium problems-recent advances and challenges,” Pesquisa Operacional, vol. 34, no. 3, pp. 521–558, 2014.DOI
  5. [5]A. A. Kulkarni and U. V. Shanbhag, “On the variational equilibrium as a refinement of the generalized Nash equilibrium,” Automatica, vol. 48, no. 1, pp. 45–55, 2012.DOI
  6. [6]J.-S. Pang and F. Facchinei, Finite-dimensional variational inequalities and complementarity problems : vol. 1, ser. Springer series in operations research. New York, Berlin, Heidelberg: Springer, 2003.
  7. [7]W. van den Broek, “Moving horizon control in dynamic games,” Journal of Economic Dynamics and Control, vol. 26, no. 6, pp. 937–961, 2002.
  8. [8]S. Hall, L. Guerrini, F. Dörfler, and D. Liao-McPherson, “Receding horizon games for modeling competitive supply chains,” IFAC-PapersOnLine, vol. 58, no. 18, pp. 8–14, 2024.arxiv.org/abs/2401.09853
  9. [9]E. Benenati and S. Grammatico, “Kinematic, “Linear-quadratic dynamic games as receding-horizon variational inequalities,” IEEE Transactions on Automatic Control, vol. 71, no. 4, pp. 2404–2417, 2026.arxiv.org/abs/2408.15703
  10. [10]S. Hall, G. Belgioioso, F. Dörfler, and D. Liao-McPherson, “Stability certificates for receding-horizon games,” IEEE Transactions on Automatic Control, vol. 71, no. 5, pp. 3511–3518, 2026.arxiv.org/abs/2404.12165
  11. [11]F. M. Hante and A. Topalovic, “Stabilizing GNEP-based model predictive control: Quasi-GNEPs and end constraints,” Optimization Online preprint, 2024.
  12. [12]——, “Stabilizing model predictive control for generalized Nash equilibrium problems using approximation by α-quasi-GNEPs and Lyapunov end cost,” in 2025 European Control Conference (ECC), 2025, pp. 2427–2432.DOI
  13. [13]E. Dimou, F. Fabiani, and A. Bemporad, “Receding horizon games with stability guarantees,” 65th IEEE Conference on Decision and Control, 2026, available on line at https://cse.lab.imtlucca.it/~bemp­orad/publications/papers/cdc26_gtmpc.pdf.
  14. [14]K. P. Wabersich and M. N. Zeilinger, “A predictive safety filter for learning-based control of constrained nonlinear dynamical systems,” Automatica, vol. 129, p. 109597, 2021.
  15. [15]K. P. Wabersich, A. J. Taylor, J. J. Choi, K. Sreenath, C. J. Tomlin, A. D. Ames, and M. N. Zeilinger, “Data-driven safety filters: Hamilton-Jacobi reachability, control barrier functions, and predictive methods for uncertain systems,” IEEE Control Systems Magazine, vol. 43, no. 5, pp. 137–177, 2023.DOI
  16. [16]K.-C. Hsu, H. Hu, and J. F. Fisac, “The safety filter: A unified view of safety-critical control in autonomous systems,” Annual Review of Control, Robotics, and Autonomous Systems, vol. 7, pp. 47–72, 2024.arxiv.org/abs/2309.05837
  17. [17]A. D. Ames, X. Xu, J. W. Grizzle, and P. Tabuada, “Control barrier function based quadratic programs for safety critical systems,” IEEE Transactions on Automatic Control, vol. 62, no. 8, pp. 3861–3876, 2017.DOI
  18. [18]A. D. Ames, K. Galloway, K. Sreenath, and J. W. Grizzle, “Rapidly exponentially stabilizing control Lyapunov functions and hybrid zero dynamics,” IEEE Transactions on Automatic Control, vol. 59, no. 4, pp. 876–891, 2014.DOI
  19. [19]T. Tataraneko, W. Shi, and A. Nedić, “Geometric convergence of gradient play algorithms for distributed Nash equilibrium seeking,” IEEE Transactions on Automatic Control, vol. 66, no. 11, pp. 5342–5353, 2021.
  20. [20]T. Tataraneko and M. Kangkampour, “Convergence rate of payoff-based generalized Nash equilibrium learning,” European Journal of Control, open access, 2025.
  21. [21]A. J. Hoffman, “On approximate solutions of systems of linear inequalities,” Journal of Research of the National Bureau of Standards, vol. 49, no. 4, pp. 263–265, 1952.
  22. [22]A. Bemporad and T. Tateraneko, “Solving monotone linear-quadratic generalized Nash equilibrium problems via quadratic programming,” arXiv preprint 2608.07336, 2026.arxiv.org/abs/2608.07336
  23. [23]A. Bemporad, “NashOpt: A Python library for computing generalized Nash equilibria and game design,” arXiv preprint 2512.23636, 2025, https://github.com/bemporad/nashopt.
  24. [24]P. J. Goulart and Y. Chen, “Clarabel: An interior-point solver for conic programs with quadratic objectives,” Mathematical Programming Computation, pp. 1–83, 2026.arxiv.org/abs/2405.12762

Paper details

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

views · 0

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