betaFeedback

WorksMathematics

Learning Parametric Monotone Games

Abstract

We study the problem of learning from data a parametric Nash equilibrium (NE) problem that is monotone (or strongly monotone) for all parameter values. In the presence of local and shared convex constraints, monotonicity enables efficient computation of generalized Nash equilibria of the learned game. We consider two learning scenarios: (i) direct learning of the NE problem from samples of the agents' costs, and (ii) inverse learning of surrogate agents' costs from samples of their best responses. We propose two methods to solve these tasks. The first is a penalty-based approach that promotes monotonicity of the learned game during training. The second, based on a representation theorem we introduce for a broad class of monotone games, parameterizes the agents' costs so that monotonicity of the NE problem is guaranteed by construction, for all parameter values, regardless of the training data used. We illustrate the applicability of the proposed methods on several numerical examples. A Python library and the examples reported in the paper are available at https://github.com/bemporad/learn_monotone_games.

Introduction

Game theory has become a foundational modeling tool across a wide range of engineering and economic applications where multiple self-interested decision-makers interact with each other [5]. Such a noncooperative multi-agent decision scenario is naturally captured by generalized games, in which several agents choose their decisions by optimizing individual objective functions subject to both local and shared coupling constraints on their decision variables. Such settings arise in economics [?], energy management [?, ?, ?], control of multi-agent systems [?], and in many other domains. In all of these settings, the cost function and the feasible set of each agent depend on the decisions of the other agents, and the relevant solution concept is the generalized Nash equilibrium (GNE) [3, ?], a state in which no agent has an incentive, or even the possibility, to unilaterally change its decision, given the decisions of the others.

Despite this ubiquity, computing a GNE is fundamentally harder than solving a single-agent optimization problem. In centralized optimization, convexity underlies essentially all guarantees of practical interest: existence and uniqueness properties of an optimizer, convergence of different and very efficient solution methods, and tractable optimality certificates via duality [?]. In game-theoretic optimization, the analogous role is played by monotonicity of the game’s pseudo-gradient mapping, or of the variational inequality that characterizes the equilibrium [?]. Monotonicity, and its strengthened variants such as strong or strict monotonicity, are often used as a key condition for establishing existence and uniqueness of equilibria, as well as specific convergence properties of equilibrium-seeking algorithms. In this sense, monotonicity is to game-theoretic optimization what convexity is to classical optimization: a structural assumption allowing for constructive solution approaches. Building on this vision, a rich body of distributed methods for solving monotone games has been developed, in which agents seek a GNE through local computations and/or limited communication with their neighbors, while retaining the convergence guarantees afforded by monotonicity [4, ?, ?].

When dealing with a family of GNE problems (GNEPs), parameterized by a vector of parameters, and when the agents’ costs, or their best responses, are only available through black-box queries for given parameter and other agents’ decision values, recent work has investigated approaches to learning surrogate models, in the form of a solution mapping from parameters to equilibrium strategies, or approximate primitives, such as surrogates of the agents’ costs or best-response functions. Such surrogate-based approaches to GNE computation can be divided into two main groups: (i) learning an approximation of the solution mapping directly, as in [?], where the Nikaido–Isoda gap function is used as a loss to train a neural network model of a continuous GNE selection, and in [?], where Generative Adversarial Equilibrium Solvers (GAES) are used to learn to output GNE of pseudo-games; and (ii) learning a surrogate of the game (for a given parameter vector) and solving it, as in [?], where a GNE is actively learned from pairwise preference data alone, collected for a specific instance of the game, without the ability to measure either best responses or agents’ costs, or in [?], which instead relies on Gaussian processes as surrogates for unknown utilities, casting equilibrium-seeking as no-regret optimization of an unknown objective. However, even if the underlying problem is monotone, neither approach in the works mentioned above to learn a surrogate of the game guarantees that the learned game is monotone, and the learning phase, being part of the solution procedure, must be repeated for every different instance of the parameter vector. For learning convex constraint sets from feasible/infeasible samples, we refer the reader to [?].

Contribution

In this paper, we present different approaches to learning a parametric NE problem from data that is guaranteed to be monotone (or strongly monotone) for all parameter values. We consider both the direct learning from samples of the agents’ costs and inverse learning from samples of their best responses. These samples can be either measured by querying the agents or generated by evaluating the costs or best-responses of a given parametric NE problem at different parameter values to monotonify it, by learning a surrogate game that is monotone for all parameter values. The approach can be considered as the game-theoretic counterpart of linear system identification of possibly nonlinear dynamics for control design [?], or constructing convex approximations of nonconvex functions, which is a common approach in optimization and control [?, ?].

We first propose a penalty-based approach that promotes monotonicity of a generic (input-convex) parameterization of the agents’ costs by penalizing violations of the monotonicity condition on the pseudogradient or on its Jacobian on training data. To guarantee monotonicity independently of the training dataset used, a second contribution of this paper is to analyze a class of convex parametric monotone games whose pseudogradient admits the splitting F(x,p)=Fs(x,p)+Fa(x,p)F(x,p) = F_s(x,p) + F_a(x,p), where the Jacobians ∇Fs\nabla F_s, ∇Fa\nabla F_a are symmetric and anti-symmetric, respectively, showing that FsF_s must be the gradient of a convex potential term and FaF_a affine with skew-symmetric Jacobian. Parameterizing the costs accordingly, in particular by neural network functions of the parameter pp, we guarantee by construction, regardless of the training data, that the learned game is monotone for all values of pp, so it can be solved with standard algorithms for monotone games and generalized NE problems. Although this class does not cover all monotone game, as the skew-symmetric part of the pseudogradient Jacobian is necessarily constant, we show that it covers all monotone convex quadratic games. For the special case of inverse learning of quadratic monotone games from best-response samples, we show that the learning problem can be solved via convex semidefinite programming.

Unlike our recent work [?], where we approximate the solution map of a given parametric GNEP, here we learn the game itself. This paper, compared to [?], has a twofold advantage. First, any convex constraint can be added after training, while the solution map learnt as in [?] would have to be recomputed if the constraints change. Second, in [?] the learned solution map may violate some constraints for certain values of pp, due to limitations of the adopted neural network architecture or training algorithm, while here, due to the imposed monotonicity, feasible GNE can be computed efficiently for each given pp by leveraging existing algorithms for solving monotone GNE problems.

The paper is structured as follows. Section 2 formulates the direct and inverse learning problems. Section 3 introduces the penalty-based approach to promote monotonicity, and Section 4 the parameterization that enforces it by construction, together with the corresponding training problem and its extension to nonsmooth costs and shared constraints. Section 5 specializes inverse learning to quadratic monotone games. Section 7 illustrates the proposed approaches on numerical examples of quadratic and nonlinear convex games, as well as the inverse learning of a game-theoretic multivariable controller.

Notation

We denote by Rn\mathbb{R}^n the nn-dimensional Euclidean space. Given mm vectors v1,…,vmv_1,\ldots,v_m from Rn\mathbb{R}^n, we denote by col⁡(v1,…,vm)\operatorname{col}(v_1,\ldots,v_m) their vertical concatenation. Given a vector vv, ∥v∥\lVert v\rVert denotes its Euclidean norm and given two vectors u,v∈Rnu,v \in\mathbb{R}^n, u⊙vu \odot v denotes their entrywise product. Given a matrix AA, ∥A(p)∥=λmax⁡(ATA)\lVert A(p)\rVert= \sqrt{\lambda_{\max}(A^\mathsf{T}A)} denotes its spectral norm and ∥A∥F=∑i,jAij2\lVert A\rVert_F = \sqrt{\sum_{i,j} A_{ij}^2} its Frobenius norm.

Problem statement

We consider a parametric game setting with NN agents, each choosing a decision vector xi∈Rnix_i \in\mathbb{R}^{n_i} to minimize a cost function J~i:Rn×Rm→R\widetilde{J}_i : \mathbb{R}^n \times\mathbb{R}^m \to\mathbb{R}, i=1,…,Ni = 1,\ldots,N, where J~i(x,p)\widetilde{J}_i(x,p) is the cost of agent ii when the agents’ decision vector is x=col⁡(x1,…,xN)∈Rnx = \operatorname{col}(x_1,\ldots,x_N) \in\mathbb{R}^n, n=∑i=1Nnin = \sum_{i=1}^N n_i, for a given vector of parameters p∈Rmp \in\mathbb{R}^m. In general, J~i\widetilde{J}_i depends on the entire vector x−ix_{-i} collecting all the components of xx but those of xix_i, leading to the following parametric Nash equilibrium (NE) problem

xi⋆(p)∈arg⁡min⁡xi∈Rni J~i(x,p)∣x−i=x−i⋆(p),i=1,…,N.(1)x_i^\star(p) \in\underset{x_i \in\mathbb{R}^{n_i}}{\arg\min}\ \widetilde{J}_i(x,p)\bigg|_{x_{-i}=x_{-i}^\star(p)}, \qquad i=1,\ldots,N. \tag*{(1)}

In general, the costs J~i\widetilde{J}_i are unknown, e.g., because they encode private preferences or objectives of the agents that cannot be directly measured or evaluated in closed form, and only data in the form of cost or best-response samples are available. To be able to find a solution to the NE problem defined in (1) in this case, our goal is to learn a surrogate NE problem from such data, i.e., to learn a parametric model {Ji(x,p;θ)}i=1N\{J_i(x,p;\theta)\}_{i=1}^{N} of the agents’ costs, where θ\theta is the vector of parameters of the model, θ∈Rnθ\theta\in\mathbb{R}^{n_\theta}, and Ji:Rn×Rm×Rnθ→RJ_i:\mathbb{R}^{n}\times\mathbb{R}^{m}\times\mathbb{R}^{n_\theta}\to\mathbb{R} is convex w.r.t. xix_i for all x−ix_{-i}, pp, and θ\theta. In particular, we are interested in learning the agents’ costs, i.e. defining θ⋆\theta^{\star}, so that the resulting convex NE problem, with the costs {Ji(x,p)=Ji(x,p;θ⋆)}i=1N\{J_i(x,p)=J_i(x,p;\theta^{\star})\}_{i=1}^{N}, is monotone (or strongly monotone) for all pp, according to the following definition:

Definition 2.1. Let F:Rn×Rm→RnF:\mathbb{R}^{n}\times\mathbb{R}^{m}\to\mathbb{R}^{n} be the pseudogradient of the game with the costs {Ji(x,p)}i\{J_i(x,p)\}_i,

F(x,p)=col⁡(∇x1J1(x,p),…,∇xNJN(x,p))∈Rn.F(x,p)=\operatorname{col}(\nabla_{x_1}J_1(x,p),\ldots,\nabla_{x_N}J_N(x,p))\in\mathbb{R}^{n}.

The game is monotone with monotonicity constant μ≥0\mu\ge0 (or strongly monotone if μ>0\mu>0) if FF is a μ\mu-monotone operator, i.e., if

(x−y)T(F(x,p)−F(y,p))≥μ∥x−y∥2∀x,y∈Rn, ∀p∈Rm.(2)(x-y)^{\mathsf{T}}(F(x,p)-F(y,p))\ge\mu\lVert x-y\rVert^{2}\qquad\forall x,y\in\mathbb{R}^{n},\ \forall p\in\mathbb{R}^{m}. \tag*{(2)}

In the case that all costs are also twice continuously differentiable w.r.t. xx (which implies F∈C1F\in C^{1} w.r.t. xx), monotonicity can be equivalently defined in terms of the Jacobian ∇F\nabla F of the pseudogradient (calculated w.r.t. xx) as follows:

∇F(x,p)+∇F(x,p)T2⪰μI∀x∈Rn, ∀p∈Rm.(3)\frac{\nabla F(x,p)+\nabla F(x,p)^{\mathsf{T}}}{2}\succeq\mu I\qquad\forall x\in\mathbb{R}^{n},\ \forall p\in\mathbb{R}^{m}. \tag*{(3)}

i.e., the symmetric part of ∇F(x,p)\nabla F(x,p) is uniformly positive semidefinite (positive definite if μ>0\mu>0). Monotonicity is a key property of NE problems. In particular, it implies that each JiJ_i is convex and C1C^{1} w.r.t. xix_i, and, thus, x⋆(p)x^{\star}(p) is a NE of the game if and only if F(x⋆(p),p)=0F(x^{\star}(p),p)=0 [?]. If, in addition, μ>0\mu>0, then the NE x⋆(p)x^{\star}(p) exists and is unique [?]. In the case of a generalized NE problem with shared constraints, strong monotonicity of the pseudogradient is a sufficient condition for the existence and uniqueness of a variational GNE [?]. Moreover, monotonicity is a sufficient condition for the convergence of many algorithms for computing a NE or a variational GNE [?]. This motivates us to target monotonicity directly when learning a parametric game or its surrogate from data.

Note that we do not assume that the underlying game {J~i}i=1N\{\widetilde{J}_i\}_{i=1}^{N} is itself monotone. Instead, we learn the closest monotone surrogate {Ji}i=1N\{J_i\}_{i=1}^{N} to it. As a result, perfect approximation of the true game cannot be guaranteed in general. Nevertheless, when agents’ best responses can be queried, the quality of the surrogate can be assessed a posteriori by estimating the deviation between the equilibrium values predicted by the learned surrogate game and each agent’s best response to those values.

We will consider two different learning scenarios, described in the next two subsections, depending on whether we have access to samples of the agents’ costs or, alternatively, to samples of their best responses.

In the following discussion of the learning problems, we will use F(x,p;θ)F(x,p;\theta) and ∇F(x,p;θ)\nabla F(x,p;\theta), without abuse of notation, to denote the pseudogradient of the game with costs {Ji(x,p;θ)}i=1N\{J_i(x,p;\theta)\}_{i=1}^{N} and its Jacobian, respectively.

Direct learning from agents’ costs

Assume that we have a set DJ={(xk,pk,{J~i(xk,pk)}i=1N)}k=1KD_J = \{(x_k,p_k,\{\tilde{J}_i(x_k,p_k)\}_{i=1}^{N})\}_{k=1}^{K} of data samples of the agents’ costs at different decision and parameter vector values xk∈Rnx_k \in\mathbb{R}^n, pk∈Rmp_k \in\mathbb{R}^m. The true functions J~i\tilde{J}_i may be either known or their values may be just observed from data. The goal is to learn a surrogate NE problem in which the costs JiJ_i approximate J~i\tilde{J}_i as much as possible, according to the following loss function

LDJ(θ)=1K∑k=1K∑i=1N∥Ji(xk,pk;θ)−J~i(xk,pk)∥2(4)\mathcal{L}_{D_J}(\theta) = \frac{1}{K}\sum_{k=1}^{K}\sum_{i=1}^{N}\left\lVert J_i(x_k,p_k;\theta)-\tilde{J}_i(x_k,p_k)\right\rVert^2 \tag*{(4)}

under the condition that the learned game is monotone for all values of pp.

Inverse-learning from best responses

Suppose now that, instead, we have no information about the costs J~i\tilde{J}_i, but rather have a set DX={xk,pk,ik}k=1KD_X = \{x_k,p_k,i_k\}_{k=1}^{K} of best-response observations, where ik∈{1,…,N}i_k \in\{1,\ldots,N\} is the index of the agent whose best response is observed at sample kk and xk=(xk,ik,xk,−ik)x_k=(x_{k,i_k},x_{k,-i_k}). In particular, for each sample kk, we observe the best response xk,ikx_{k,i_k} of agent iki_k to the other agents’ actions xk,−ikx_{k,-i_k} at parameter value pkp_k:

xk,ik≜arg⁡min⁡xi∈Rni J~i(x,pk)∣x−ik=xk,−ik.x_{k,i_k} \triangleq\underset{x_i\in\mathbb{R}^{n_i}}{\arg\min}\ \left.\tilde{J}_i(x,p_k)\right|_{x_{-i_k}=x_{k,-i_k}}.

This may represent a common practical situation in which we can only observe the agents’ actions, under the assumption that they are acting optimally at different parameter values and other agents’ decisions, but their costs are not disclosed. The goal is to learn a surrogate NE problem in which the costs JiJ_i provide similar best responses to the true costs J~i\tilde{J}_i at the observed samples, captured by the following (bilevel) loss

LDX(θ)=1K∑k=1K∥arg⁡min⁡xikJik(x∣x−ik=xk,−ik,pk,θ)−xk,ik∥2.(5)\mathcal{L}_{D_X}(\theta) = \frac{1}{K}\sum_{k=1}^{K}\left\lVert\left.\arg\min_{x_{i_k}} J_{i_k}(x\mid_{x_{-i_k}=x_{k,-i_k}},p_k,\theta)\right.-x_{k,i_k}\right\rVert^2. \tag*{(5)}

We will show in Section 5 that, in the special case of inverse learning of quadratic monotone games, the bilevel loss can be avoided and (5) can be remapped into either a nonlinear least-squares problem or a convex semidefinite program (SDP).

Optional NE samples

Besides having cost or best response samples, there might be cases in which a second dataset of NE samples is also available, either DEJ={(xk⋆,pk,J~i(xk⋆,pk))}k=1K⋆D_{EJ}=\{(x_k^\star,p_k,\tilde{J}_i(x_k^\star,p_k))\}_{k=1}^{K^\star} or DEX={(xk⋆,pk)}k=1K⋆D_{EX}=\{(x_k^\star,p_k)\}_{k=1}^{K^\star}, where xk⋆x_k^\star is an unconstrained NE of the game at parameter value pkp_k and K⋆K^\star is the number of NE samples, K⋆≥0K^\star\geq0. Accordingly, when K⋆>0K^\star>0, the following losses can be added to the training problems (4) or (5) to promote the matching of the NE samples:

LEF(θ)=λ2K⋆∑k=1K⋆∥F(xk⋆,pk;θ)∥2(6)\mathcal{L}_{EF}(\theta)=\frac{\lambda_2}{K^\star}\sum_{k=1}^{K^\star}\left\lVert F(x_k^\star,p_k;\theta)\right\rVert^2 \tag*{(6)}

and either

LEJ(θ)=λ1K∗∑k=1K∗∑i=1N∥Ji(xk∗,pk;θ)−J~i(xk∗,pk)∥2(7)\mathcal{L}_{EJ}(\theta)=\frac{\lambda_1}{K^*}\sum_{k=1}^{K^*}\sum_{i=1}^{N}\left\|J_i(x_k^*,p_k;\theta)-\widetilde{J}_i(x_k^*,p_k)\right\|^2 \tag*{(7)}

or

LEX(θ)=λ1K∗∑k=1K∗∑i=1N∥arg⁡min⁡xi Ji(x∣x−i=xk,−i∗,pk;θi)−xk,i∗∥2(8)\mathcal{L}_{EX}(\theta)=\frac{\lambda_1}{K^*}\sum_{k=1}^{K^*}\sum_{i=1}^{N}\left\|\underset{x_i}{\arg\min}\ J_i(x\mid_{x_{-i}=x^*_{k,-i}},p_k;\theta_i)-x^*_{k,i}\right\|^2 \tag*{(8)}

where λ1,λ2≥0\lambda_1,\lambda_2 \ge0 are penalties that balance the importance of fitting the best-response samples in DXD_X and matching the NE samples in either DEJD_{EJ} or DEXD_{EX}.

Although we mainly focus on learning the costs JiJ_i in a game without constraints (see (1)), once an unconstrained monotone game is learned, it can be extended to handle local constraints xi∈Xi(p)x_i \in\mathcal{X}_i(p) and to a GNEP when shared constraints x∈X(p)x \in\mathcal{X}(p) are added to the game. Note that, in the presence of constraints, the penalty (8) is relevant only if the training points xk∗x_k^* are still NEs, not GNEs, otherwise (6c) must be modified to include the constraint x∈X(p)x \in\mathcal{X}(p) in the inner optimization problem, in the case X(p)\mathcal{X}(p) is already available during the learning phase. Moreover, while (6b) is relevant no matter the nature of xk∗x_k^* is, when xk∗x_k^* are GNEs the penalty (6a) should not be included.

So far, we have formulated the learning problems (4) and (5) without explicitly enforcing the monotonicity of the resulting game. In the next sections we will introduce two different approaches to learning the costs JiJ_i so that they define a parametric monotone game. The first approach is to parameterize each agent’s cost function as a generic input-convex parametric model Ji(x,p;θ)J_i(x,p;\theta) and enforce monotonicity by adding further penalties that promote the monotonicity of the resulting game. The second approach is to enforce monotonicity by construction, leveraging a suitable parameterization of the models JiJ_i, so that the resulting game is monotone for all pp no matter what the model parameters θ\theta and the dataset used are.

Monotonicity enforcement via penalties

Let DM={(xj,pj)}j=1MD_M=\{(x_j,p_j)\}_{j=1}^{M} be a further set of samples of the decision and parameter vectors generated in the range of xx and pp of interest, such as in the smallest hyperboxes containing the training samples in DJD_J or DXD_X, respectively. Note that the samples in DMD_M do not contain any measurement of the agents’ costs or best responses.

We consider the following three alternative penalties for promoting monotonicity:

LM1(θ)=γM(M−1)∑j=1M∑h=1h≠jMmax⁡{0,μ∥xh−xj∥2−(xj−xh)T(F(xj,pj;θ)−F(xh,pj;θ))}2(9)\mathcal{L}_{M1}(\theta)=\frac{\gamma}{M(M-1)}\sum_{j=1}^{M}\sum_{\substack{h=1\\h\ne j}}^{M}\max\left\{0,\mu\|x_h-x_j\|^2-(x_j-x_h)^\mathsf{T}\left(F(x_j,p_j;\theta)-F(x_h,p_j;\theta)\right)\right\}^2 \tag*{(9)}

related to the violation of the monotonicity condition (2), with γ≫1\gamma\gg1 a large penalty weight, or

LM2(θ)=γM∑j=1Mmax⁡{0,2μ−λmin⁡(∇xF(xj,pj;θ)+∇xF(xj,pj;θ)T)}2(10)\mathcal{L}_{M2}(\theta)=\frac{\gamma}{M}\sum_{j=1}^{M}\max\left\{0,2\mu-\lambda_{\min}\left(\nabla_xF(x_j,p_j;\theta)+\nabla_xF(x_j,p_j;\theta)^\mathsf{T}\right)\right\}^2 \tag*{(10)}

related instead to the violation of the monotonicity condition (3). The latter is also satisfied whenever the symmetric part of the pseudogradient Jacobian is the Hessian of a convex function with strong-convexity parameter μ\mu (cf. Lemma 4.1 below), which leads to the following third alternative penalty to promote monotonicity: introduce an auxiliary, twice differentiable, input-convex network Φ(x,p;θ)\Phi(x,p;\theta) and penalize

LM3(θ)=γM∑j=1M∥∇xF(xj,pj;θ)+∇xF(xj,pj;θ)⊤−∇x2Φ(xj,pj;θ)−2μI∥F2(11)\mathcal{L}_{M3}(\theta)=\frac{\gamma}{M}\sum_{j=1}^{M}\left\|\nabla_xF(x_j,p_j;\theta)+\nabla_xF(x_j,p_j;\theta)^{\top}-\nabla_x^2\Phi(x_j,p_j;\theta)-2\mu I\right\|_F^2 \tag*{(11)}

Note that in (7c), θ\theta also includes the parameters of Φ\Phi, which is only auxiliary and can be discarded after training.

Finally, the learning problem can be formulated as follows:

min⁡θLD(θ)+LM(θ)+LE(θ)+LEF(θ)+ρ2∥θ∥2(12)\min_{\theta}\mathcal{L}_D(\theta)+\mathcal{L}_M(\theta)+\mathcal{L}_E(\theta)+\mathcal{L}_{EF}(\theta)+\frac{\rho}{2}\|\theta\|^2 \tag*{(12)}

where LD\mathcal{L}_D is either LDJ\mathcal{L}_{DJ} or LDX\mathcal{L}_{DX}, LM\mathcal{L}_M is one of the three penalties LM1\mathcal{L}_{M1}, LM2\mathcal{L}_{M2}, or LM3\mathcal{L}_{M3}, and LE\mathcal{L}_E is either LEJ\mathcal{L}_{EJ} or LEX\mathcal{L}_{EX} if NE samples are available, and zero otherwise, and similarly LEF(θ)\mathcal{L}_{EF}(\theta) is zero if no NE samples are given. The last term is a standard ℓ2\ell_2-regularization introduced to prevent overfitting.

Monotonicity enforcement by construction

The main drawback of the monotonicity-enforcing approach described in Section 3 is that no guarantee exists that the resulting game is monotone for all values of the parameter pp, as the result largely depends on the weight γ\gamma in LM\mathcal{L}_M and on the richness of the dataset DM\mathcal{D}_M. In order to construct agents’ costs JiJ_i that enforce the monotonicity condition (3) by construction, in this section we propose a different approach. The following lemma (Lemma 4.1) shows that a sufficient condition for monotonicity is that the pseudogradient FF can be split into a symmetric and a skew-symmetric part. For simplicity of notation, in the following we omit the dependence of FF on the parameter pp and on the model parameters θ\theta.

Lemma 4.1. Let F:Rn→RnF:\mathbb{R}^n\to\mathbb{R}^n be the pseudogradient of a game with costs Ji:Rn→RJ_i:\mathbb{R}^n\to\mathbb{R}, Ji∈C2J_i\in C^2 and convex in xix_i, ∀i=1,…,N\forall i=1,\ldots,N, and assume that

F(x)=Fs(x)+Fa(x)(13)F(x)=F_s(x)+F_a(x) \tag*{(13)}

where Fs,Fa:Rn→RnF_s,F_a:\mathbb{R}^n\to\mathbb{R}^n, Fs∈C1F_s\in C^1, Fa∈C2F_a\in C^2 are such that ∇Fs(x)\nabla F_s(x) is symmetric and positive semidefinite for all xx, and ∇Fa(x)\nabla F_a(x) is skew-symmetric for all xx. Then:

(i) Fs(x)=∇Ψ(x)F_s(x)=\nabla\Psi(x) for some convex function Ψ:Rn→R\Psi:\mathbb{R}^n\to\mathbb{R}, Ψ∈C2\Psi\in C^2;

(ii) Fa(x)=Sx+rF_a(x)=Sx+r is affine, with S⊤=−SS^\top=-S, r∈Rnr\in\mathbb{R}^n;

(iii) the game is monotone and each cost function necessarily has the form

Ji(x)=Ψ(x)+∑j≠ixi⊤Sijxj+ri⊤xi+ϕi(x−i)(14)J_i(x)=\Psi(x)+\sum_{j\ne i}x_i^\top S_{ij}x_j+r_i^\top x_i+\phi_i(x_{-i}) \tag*{(14)}

where ϕi:Rn−ni→R\phi_i:\mathbb{R}^{n-n_i}\to\mathbb{R} and S=[Sij]S=[S_{ij}], r=col⁡(r1,…,rN)r=\operatorname{col}(r_1,\ldots,r_N) are partitioned according to the dimensions n1,…,nNn_1,\ldots,n_N of the agents’ decision vectors.

Proof. (i) Since ∇Fs(x)\nabla F_s(x) is symmetric for all xx and Rn\mathbb{R}^n is simply connected, by the Poincaré lemma FsF_s is a gradient field: there exists Ψ∈C2(Rn)\Psi\in C^2(\mathbb{R}^n) with Fs=∇ΨF_s = \nabla\Psi. Since ∇2Ψ(x)=∇Fs(x)⪰0\nabla^2\Psi(x) = \nabla F_s(x) \succeq0 for all xx, Ψ\Psi is convex.

(ii) The condition ∇Fa(x)+∇Fa(x)T=0\nabla F_a(x) + \nabla F_a(x)^\mathsf{T} = 0 for all xx is equivalent to

∂(Fa)i∂xj(x)+∂(Fa)j∂xi(x)=0i,j=1,…,n.(15)\frac{\partial(F_a)_i}{\partial x_j}(x) + \frac{\partial(F_a)_j}{\partial x_i}(x) = 0 \qquad i,j=1,\ldots,n. \tag*{(15)}

Differentiating with respect to xkx_k, exploiting the symmetry of Hessian matrices, and cyclically permuting the indices (i,j,k)(i,j,k) yields

∂k∂j(Fa)i=−∂k∂i(Fa)j=−∂i∂k(Fa)j=∂i∂j(Fa)k=∂j∂i(Fa)k=−∂j∂k(Fa)i=−∂k∂j(Fa)i\begin{aligned} \partial_k\partial_j(F_a)_i &= -\partial_k\partial_i(F_a)_j = -\partial_i\partial_k(F_a)_j \\ &= \partial_i\partial_j(F_a)_k = \partial_j\partial_i(F_a)_k \\ &= -\partial_j\partial_k(F_a)_i = -\partial_k\partial_j(F_a)_i \end{aligned}

which in turn implies that ∂k∂j(Fa)i=0\partial_k\partial_j(F_a)_i=0 for all j,k,i=1,…,nj,k,i=1,\ldots,n, i.e., all second derivatives of (Fa)i(F_a)_i are zero, for all i=1,…,ni=1,\ldots,n. Therefore, Fa(x)=Sx+rF_a(x)=Sx+r with S=∇FaS=\nabla F_a constant and ST=−SS^\mathsf{T}=-S due to the assumed skew-symmetry of FaF_a.

(iii) By (i)–(ii), the pseudogradient has the form

F(x)=∇Ψ(x)+Sx+r∇F(x)=∇2Ψ(x)+SF(x)=\nabla\Psi(x)+Sx+r \qquad\nabla F(x)=\nabla^2\Psi(x)+S

whose symmetric part is 12(∇F(x)+∇F(x)T)=∇2Ψ(x)⪰0\frac{1}{2}(\nabla F(x)+\nabla F(x)^\mathsf{T})=\nabla^2\Psi(x)\succeq0; hence FF is monotone. Moreover, since Fi(x)=∇xiJi(x)F_i(x)=\nabla_{x_i}J_i(x), integrating with respect to xix_i for fixed x−ix_{-i} gives

Ji(x)=Ψ(x)+xiT∑j≠iSijxj+12xiTSiixi+riTxi+ϕi(x−i)J_i(x)=\Psi(x)+x_i^\mathsf{T}\sum_{j\ne i}S_{ij}x_j+\frac{1}{2}x_i^\mathsf{T}S_{ii}x_i+r_i^\mathsf{T}x_i+\phi_i(x_{-i})

for some function ϕi\phi_i such that ϕi(x−i)\phi_i(x_{-i}) is independent of xix_i, and xiTSiixi=0x_i^\mathsf{T}S_{ii}x_i=0 because SiiS_{ii} is skew-symmetric, leading to the form (14). □\square

The convex potential term Ψ(x)\Psi(x) can be a rather arbitrary function in C2C^2. Special cases of Ψ(x)\Psi(x) include general input-convex neural networks, and the smooth approximation of the indicator function of the set defined by known constraints on agents’ actions; for example, for a box constraint x∈[xmin⁡,xmax⁡]x\in[x_{\min},x_{\max}], the smooth barrier function

Ψ(x)=βε(log⁡(1+e(xmin⁡−x)/ε)+log⁡(1+e(x−xmax⁡)/ε))\Psi(x)=\beta\varepsilon\left(\log\left(1+e^{(x_{\min}-x)/\varepsilon}\right)+\log\left(1+e^{(x-x_{\max})/\varepsilon}\right)\right)

where β≫1\beta\gg1 and ε≪1\varepsilon\ll1.

Remark 4.2. A simple extension to allow Ji∉C2J_i\notin C^2 is to consider an arbitrary convex potential term Φ:Rn→R\Phi:\mathbb{R}^n\to\mathbb{R} and set Ji(x)=Φ(x)+Hi(x)J_i(x)=\Phi(x)+H_i(x), with Hi∈C2H_i\in C^2 and the game defined by the costs HiH_i satisfying the splitting assumption (9), possibly with a zero symmetric part of the associated pseudogradient if no further potential terms are required. By Lemma 4.1, the resulting game is monotone and has the form (14), with Ψ(x)=Φ(x)+ΨH(x)\Psi(x)=\Phi(x)+\Psi_H(x), where ΨH∈C2\Psi_H\in C^2 is the convex potential due to the smooth part HiH_i. An example of extending the construction to nonsmooth convex cost functions is to select

Φ(x)=max⁡j=1,…,MΦj(x)\Phi(x)=\max_{j=1,\ldots,M}\Phi_j(x)

where each Φj(x)\Phi_j(x) is a smooth convex function. By introducing a slack variable yiy_i for each agent, the associated NE problem can be rewritten as the following jointly convex merely monotone generalized Nash equilibrium (GNE) problem with shared constraints:

min⁡xi,yiyi+Ψ(x)+∑j≠ixiTSijxj+riTxi+ϕi(x−i)s.t.Φj(x)≤yi,j=1,…,M,i=1,…,N.\begin{aligned} \min_{x_i,y_i}\quad& y_i+\Psi(x)+\sum_{j\ne i}x_i^{\mathsf T}S_{ij}x_j+r_i^{\mathsf T}x_i+\phi_i(x_{-i})\\ \text{s.t.}\quad& \Phi_j(x)\le y_i,\quad j=1,\ldots,M,\quad i=1,\ldots,N. \end{aligned}

At the equilibrium, each agent ii has yi∗=max⁡j=1,…,MΦj(x∗)y_i^*=\max_{j=1,\ldots,M}\Phi_j(x^*) due to minimizing yiy_i. Special cases of this formulation include convex piecewise quadratic terms Φ(x)\Phi(x), which can be expressed as the maximum of a finite number of quadratic functions Φj(x)\Phi_j(x), and convex piecewise linear terms Φ(x)\Phi(x), which can be expressed as the maximum of a finite number of affine functions Φj(x)\Phi_j(x).

Remark 4.3. The splitting assumption (9) is sufficient for monotonicity but not necessary. Consider the two-player game with scalar decisions and costs

J1(x)=12x12+x1sin⁡x2J2(x)=12x22−x2sin⁡x1J_1(x)=\frac{1}{2}x_1^2+x_1\sin x_2\qquad J_2(x)=\frac{1}{2}x_2^2-x_2\sin x_1

each smooth and strongly convex in the agent’s own variable. Its pseudogradient and Jacobian are

F(x)=[x1+sin⁡x2x2−sin⁡x1]∇F(x)=[1cos⁡x2−cos⁡x11].F(x)=\begin{bmatrix}x_1+\sin x_2\\x_2-\sin x_1\end{bmatrix} \qquad \nabla F(x)=\begin{bmatrix}1&\cos x_2\\-\cos x_1&1\end{bmatrix}.

The eigenvalues of the symmetric part of ∇F(x)\nabla F(x) are given by

det⁡[λ−112(cos⁡x2−cos⁡x1)12(cos⁡x1−cos⁡x2)λ−1]=0\det\begin{bmatrix} \lambda-1 & \frac{1}{2}(\cos x_2-\cos x_1)\\ \frac{1}{2}(\cos x_1-\cos x_2) & \lambda-1 \end{bmatrix}=0

or λ2−2λ+1−14(cos⁡x2−cos⁡x1)2=0\lambda^2-2\lambda+1-\frac{1}{4}(\cos x_2-\cos x_1)^2=0, which gives λ=1±12∣cos⁡x2−cos⁡x1∣\lambda=1\pm\frac{1}{2}|\cos x_2-\cos x_1|. As both eigenvalues are nonnegative, the game is monotone. However, the skew-symmetric part

12(∇F(x)−∇F(x)T)=cos⁡x1+cos⁡x22[01−10]\frac{1}{2}\left(\nabla F(x)-\nabla F(x)^{\mathsf T}\right)=\frac{\cos x_1+\cos x_2}{2}\begin{bmatrix}0&1\\-1&0\end{bmatrix}

depends on xx; hence, by Lemma 4.1, no decomposition F=Fs+FaF=F_s+F_a with ∇Fs\nabla F_s symmetric and ∇Fa\nabla F_a skew-symmetric everywhere exists for this game, otherwise the skew-symmetric part would be constant.

While Remark 4.3 shows that the splitting assumption (9) is not necessary in general for monotonicity, the following lemma shows that it is indeed necessary when restricting to the class of monotone quadratic games.

Lemma 4.4. If the costs JiJ_i are convex quadratic functions of xx and the game is monotone with monotonicity constant μ≥0\mu\ge0, then F(x)=Fs(x)+Fa(x)F(x)=F_s(x)+F_a(x) with

Fs(x)=(CTC+μI)xFa(x)=(D−DT)x+qF_s(x)=(C^{\mathsf T}C+\mu I)x\qquad F_a(x)=(D-D^{\mathsf T})x+q

for some upper-triangular matrix C∈Rn×nC \in\mathbb{R}^{n \times n} and block strictly upper-triangular matrix D∈Rn×nD \in\mathbb{R}^{n \times n} where blocks refer to the partition of xx into the agents’ decision vectors x1,…,xNx_1,\ldots,x_N, i.e., D=[Dij]D = [D_{ij}] with Dij∈Rni×njD_{ij} \in\mathbb{R}^{n_i \times n_j} and Dij=0D_{ij} = 0 for i≥ji \ge j. Moreover, by letting the resulting pseudogradient matrix be

A=CTC+D−DT+μI(16)A = C^{\mathsf{T}}C + D - D^{\mathsf{T}} + \mu I \tag*{(16)}

the individual cost functions can be written, without loss of generality, as

Ji(x)=12xiTAiixi+∑j≠ixiTAijxj+qiTxi+12x−iTA−i,−ix−i.(17)J_i(x) = \frac{1}{2}x_i^{\mathsf{T}}A_{ii}x_i + \sum_{j \ne i}x_i^{\mathsf{T}}A_{ij}x_j + q_i^{\mathsf{T}}x_i + \frac{1}{2}x_{-i}^{\mathsf{T}}A_{-i,-i}x_{-i}. \tag*{(17)}

Proof. Since the game is quadratic, its pseudogradient F(x)=Ax+qF(x) = Ax + q. By splitting A=A+AT2+A−AT2A = \frac{A+A^{\mathsf{T}}}{2} + \frac{A-A^{\mathsf{T}}}{2} we get F(x)=Fs(x)+Fa(x)F(x) = F_s(x) + F_a(x), with Fs(x)=A+AT2xF_s(x) = \frac{A+A^{\mathsf{T}}}{2}x and Fa(x)=A−AT2x+qF_a(x) = \frac{A-A^{\mathsf{T}}}{2}x + q. By assumption, the matrix M=A+AT2−μIM = \frac{A+A^{\mathsf{T}}}{2} - \mu I is symmetric and positive semidefinite, so M=BTBM = B^{\mathsf{T}}B for some matrix BB. By taking the QR factorization B=QCB = QC (with QTQ=IQ^{\mathsf{T}}Q = I and CC upper-triangular) we get M=CTCM = C^{\mathsf{T}}C and hence Fs(x)=(CTC+μI)xF_s(x) = (C^{\mathsf{T}}C + \mu I)x. Moreover, each diagonal block Aii=∇xixi2JiA_{ii} = \nabla^2_{x_i x_i}J_i is a Hessian and hence symmetric, so the diagonal blocks Aii−AiiT2\frac{A_{ii}-A_{ii}^{\mathsf{T}}}{2} of the skew-symmetric matrix A−AT2\frac{A-A^{\mathsf{T}}}{2} vanish. Next, let DD be its block strictly upper-triangular part, i.e., Dij=Aij−AjiT2D_{ij} = \frac{A_{ij}-A_{ji}^{\mathsf{T}}}{2} for i<ji < j and Dij=0D_{ij} = 0 for i≥ji \ge j. Then A−AT2=D−DT\frac{A-A^{\mathsf{T}}}{2} = D - D^{\mathsf{T}} and hence Fa(x)=(D−DT)x+qF_a(x) = (D-D^{\mathsf{T}})x + q. Finally, since the ii-th block of FF is ∇xiJi(x)=Aiixi+∑j≠iAijxj+qi\nabla_{x_i}J_i(x) = A_{ii}x_i + \sum_{j \ne i}A_{ij}x_j + q_i, integrating with respect to xix_i determines JiJ_i up to an additive term depending only on x−ix_{-i}. As such a term does not affect the optimization of player ii, it can be normalized to 12x−iTA−i,−ix−i\frac{1}{2}x_{-i}^{\mathsf{T}}A_{-i,-i}x_{-i}, giving (12b).

Training problem

Building on the parameterization of Lemma 4.4, we now let CC, DD, and qq depend on the parameter vector pp and train them from data so as to fit a parametric family of monotone quadratic games. Similarly to [?], we parameterize each nonzero entry of CC, DD, and qq as a function of the parameter vector pp, such as a neural network, and we also parameterize the potential function Ψ(x,p;θ)\Psi(x,p;\theta) as an input-convex neural network, as well as neural-network functions ϕi(x−i,p;θ)\phi_i(x_{-i},p;\theta). In this case, θ\theta collects all the parameters of these neural networks. Other classes of parametric functions can be used as well. The resulting learning problem, which reads as in (8) with LM(θ)=0L_M(\theta) = 0, provides a model J(x,p;θ)J(x,p;\theta) that trades off between fitting the data and ensuring monotonicity by construction for all values of pp.

Remark 4.5. The monotonicity parameter μ\mu is a degree of freedom of the learning approach: it trades off the flexibility of the model (small μ\mu, even μ=0\mu= 0) against the numerical and convergence properties that the online solution method should enjoy for any instance of pp (large μ\mu), especially when shared constraints are added to the game after the agents’ costs have been learned. Note that we choose here a uniform μ\mu for all values of pp, as parameter-dependent monotonicity can already be enforced by properly selecting Ψ(x,p;θ)\Psi(x,p;\theta), for example by setting Ψ(x,p;θ)=μ~(p;θ)2∥x∥2+Ψ~(x,p;θ)\Psi(x,p;\theta) = \frac{\tilde{\mu}(p;\theta)}{2}\lVert x\rVert^2 + \tilde{\Psi}(x,p;\theta) with Ψ~\tilde{\Psi} convex in xx and μ~(p;θ)≥0\tilde{\mu}(p;\theta) \ge0 for all pp.

Inverse-learning of monotone quadratic games

We now specialize the inverse-learning problem of Section 2 to convex quadratic games, showing that the bilevel loss (5) can be avoided altogether and the training problem recast as a tractable nonlinear least-squares problem or, in the monotone case, as a convex semidefinite program.

Convex quadratic games

Consider again the learning problem in (5) with convex quadratic costs JiJ_i as in (12b). The low-level problem is solved by xˉk,i\bar{x}_{k,i} such that

∇xiJi=Aiixˉk,i+Ai,−ixk,−i+qi=0(18)\nabla_{x_i} J_i = A_{ii}\bar{x}_{k,i} + A_{i,-i}x_{k,-i} + q_i = 0 \tag*{(18)}

which gives the affine best-response expression xˉk,i=−Aii−1(Ai,−ixk,−i+qi)\bar{x}_{k,i} = -A_{ii}^{-1}\left(A_{i,-i}x_{k,-i} + q_i\right). We provide below three different approaches to address the learning problem (5) based on such an affine relation between xˉk,i\bar{x}_{k,i} and xk,−ix_{k,-i}.

Nonlinear least-squares formulation

Given the pseudogradient-matrix parameterization in (12a), the learning problem can be formulated as the following nonlinear least-squares problem:

min⁡θρ2∥θ∥2+1K∑k=1K∥Aii−1(Ai,−ixk,−i+qi)+xk,i∥22(19)\min_{\theta} \frac{\rho}{2}\lVert\theta\rVert^2 + \frac{1}{K}\sum_{k=1}^{K}\left\lVert A_{ii}^{-1}\left(A_{i,-i}x_{k,-i} + q_i\right) + x_{k,i}\right\rVert_2^2 \tag*{(19)}

where i=iki=i_k and we have omitted the explicit dependence of AiiA_{ii}, Ai,−iA_{i,-i}, and qiq_i on pkp_k and θ\theta for brevity, and AA is parameterized as in (12a) to ensure the monotonicity of the learned game.

Semidefinite programming formulation

By weighting each residual in (14) by AiiA_{ii}, which corresponds to considering the violation of the zero-gradient condition (13) instead of the best-response errors as in (14), and directly parameterizing the pseudogradient matrix AA as a free parameter independent of pp and q=q0+q1pq=q_0+q_1p as affine, θ=(A,q0,q1)\theta=(A,q_0,q_1), problem (14) can be reformulated as the following convex SDP problem in θ\theta:

min⁡θρ2∥θ∥2+1K∑k=1K∥Ai,−ixk,−i+q0i+q1ipk+Aiixk,i∥22s.t.12(A+AT)⪰μIAii=AiiT, i=1,…,Ntr⁡(A)=n(20)\begin{aligned} \min_{\theta}\quad&\frac{\rho}{2}\lVert\theta\rVert^2+\frac{1}{K}\sum_{k=1}^{K}\left\lVert A_{i,-i}x_{k,-i}+q_{0i}+q_{1i}p_k+A_{ii}x_{k,i}\right\rVert_2^2\\ \text{s.t.}\quad&\frac{1}{2}\left(A+A^{\mathsf{T}}\right)\succeq\mu I\\ &A_{ii}=A_{ii}^{\mathsf{T}},\ i=1,\ldots,N\\ &\operatorname{tr}(A)=n \tag*{(20)} \end{aligned}

which can be solved to global optimality. Note that the constraint tr⁡(A)=n\operatorname{tr}(A)=n is added to avoid the trivial solution θ=(0,0,0)\theta=(0,0,0) when μ=0\mu=0, and only corresponds to a scaling of the resulting learned cost functions.

Least-squares/semidefinite programming formulation

Problem (15) can be further manipulated into the cascade of an unconstrained least-squares problem and an SDP problem. To this end, let us introduce the following new variables:

Pi≜−Aii−1Ai,−i∈Rni×n−iP_i \triangleq-A_{ii}^{-1}A_{i,-i} \in\mathbb{R}^{n_i \times n_{-i}}
fji≜−Aii−1q0i∈Rni,j=0,1.(21)f_{ji} \triangleq-A_{ii}^{-1}q_{0i} \in\mathbb{R}^{n_i}, \quad j=0,1. \tag*{(21)}

Substituting the affine best response into (5), the bilevel problem collapses to the linear least-squares problem

min⁡{Pi,fi}i=1N1K∑i=1N∑k:ki=i∥Pixk,−i+fi0+fi1pk−xk,i∥22(22)\min_{\{P_i,f_i\}_{i=1}^{N}} \frac{1}{K}\sum_{i=1}^{N}\sum_{k: k_i=i}\left\|P_i x_{k,-i}+f_{i0}+f_{i1}p_k-x_{k,i}\right\|_2^2 \tag*{(22)}

which decouples across agents: each (Pi,fi)(P_i,f_i) is obtained from an ordinary least-squares fit of agent ii’s measured best responses on the opponents’ decisions. After solving (17), the original pseudogradient matrix AA and vectors q0,q1q_0,q_1 are related to the optimal least-squares estimates (Pi,fi0,fi1)(P_i,f_{i0},f_{i1}) by the linear relations

AiiPi=−Ai,−i,Aiifji=−qji,j=0,1.(23)A_{ii}P_i=-A_{i,-i}, \qquad A_{ii}f_{ji}=-q_{ji}, \quad j=0,1. \tag*{(23)}

Since no convexity or monotonicity constraints are imposed in (17), to recover a monotone game we can solve the following SDP problem:

min⁡A,q∑i=1N∥[Aii Pi fi0 fi1]+[Ai,−i qi0 qi1]∥F2s.t.constraints in (15)(24)\begin{aligned} \min_{A,q}\quad&\sum_{i=1}^{N}\left\|[A_{ii}\ P_i\ f_{i0}\ f_{i1}]+[A_{i,-i}\ q_{i0}\ q_{i1}]\right\|_{F}^{2}\\ \text{s.t.}\quad&\text{constraints in (15)} \tag*{(24)} \end{aligned}

whose cost function is the sum of the squared residuals of the linear equations (18). Problem (19) is again an LMI-constrained least-squares problem, but unlike (15), its cost function is independent of the number of samples KK. The advantage of such a two-stage approach is that the first stage (17) is a standard unconstrained least-squares problem that can be solved very efficiently, and the second stage (19) is an semidefinite program whose size depends only on the number of agents and their decision dimensions, but not on the number of samples KK.

Extensions

The formulation (14) can be extended to appropriate non-quadratic monotone games by modeling the agents’ costs as in Section 4, so that the pseudogradient of the game is F(x,p;θ)=A(p;θ)x+q(p;θ)+∇xΨ(x,p;θ)F(x,p;\theta)=A(p;\theta)x+q(p;\theta)+\nabla_x\Psi(x,p;\theta), with A(p;θ)A(p;\theta) parameterized as in (12a) and Ψ\Psi convex in xx, and minimizing the residual of the first-order optimality condition ∇xiJi=0\nabla_{x_i}J_i=0 in a nonlinear least-squares sense, similarly to the loss adopted in (15):

min⁡θρ2∥θ∥2+1K∑k=1K∥∇xiΨ(xk,pk;θ)+Aii(pk;θ)xk,i+Ai,−i(pk;θ)xk,−i+qi(pk;θ)∥22+1K∑k=1K(tr⁡(A(pk;θ))−n)2(25)\begin{aligned} \min_{\theta}\frac{\rho}{2}\|\theta\|^2+\frac{1}{K}\sum_{k=1}^{K}\left\|\nabla_{x_i}\Psi(x_k,p_k;\theta)+A_{ii}(p_k;\theta)x_{k,i}+A_{i,-i}(p_k;\theta)x_{k,-i}+q_i(p_k;\theta)\right\|_2^2 \\ &+\frac{1}{K}\sum_{k=1}^{K}\left(\operatorname{tr}(A(p_k;\theta))-n\right)^2 \tag*{(25)} \end{aligned}

where i=iki=i_k and the last term plays the role of the constraint tr⁡(A)=n\operatorname{tr}(A)=n in (20) to avoid the trivial zero solution. The resulting problem is a nonlinear least-squares problem in θ\theta.

We can also extend the above approach to monotone generalized NE problems, where the agents’ decisions are subject to a shared polyhedral constraint set X\mathcal{X}

X={x∈Rn:Axx≤bx},Ax∈Rm×n,bx∈Rm(26)\mathcal{X}=\left\{x\in\mathbb{R}^{n}: A_xx\le b_x\right\},\qquad A_x\in\mathbb{R}^{m\times n},\quad b_x\in\mathbb{R}^{m} \tag*{(26)}

where AxA_x and bxb_x are known or learnable. In this case, the best response of agent i=iki=i_k to xˉk,−i\bar{x}_{k,-i} is the solution of the quadratic program

xˉi(θ,pk,xk,−i;θ)∈arg⁡min⁡xi Ji(x,pk;θ)\bar{x}_i(\theta,p_k,x_{k,-i};\theta)\in\underset{x_i}{\arg\min}\ J_i(x,p_k;\theta)
s.t.Axx≤bx,where x−i=xk,−i(27)\text{s.t.}\quad A_xx\le b_x,\quad\text{where }x_{-i}=x_{k,-i} \tag*{(27)}

and the inverse problem becomes the following bilevel program

min⁡θ 1K∑k=1K∥arg⁡min⁡xi:Axx≤bx, x−i=xk,−i Ji(x,pk;θ)−xk,i∥22(28)\underset{\theta}{\min}\ \frac{1}{K}\sum_{k=1}^{K}\left\|\underset{x_i:A_xx\le b_x,\ x_{-i}=x_{k,-i}}{\arg\min}\ J_i(x,p_k;\theta)-x_{k,i}\right\|_2^2 \tag*{(28)}

which can be solved as a nonlinear least-squares problem by employing differentiable quadratic programming (QP) solvers [1, ?] when the costs JiJ_i are parameterized as in (12).

Lipschitz constant of the pseudogradient

In the previous sections, we have shown how to fit a parametric surrogate monotone game to data, with the goal of learning a model that can predict the agents’ behavior for new values of the parameter pp and other agent’s decisions x−ix_{-i}. When the goal is to compute a Nash equilibrium of the surrogate game for a given pp, and, in particular, a variational GNE (v-GNE) when imposing shared constraints, different online algorithms can be used. Solution methods include minimizing the residual of the joint KKT conditions [?], or using iterative methods tailored to monotone games, such as Korpelevich’s extragradient method [?] or gradient play with its accelerated versions [?, ?] in the case μ>0\mu>0. The convergence of iterative algorithms often depends on the inverse of the Lipschitz constant L(p)L(p) of the pseudogradient F(x,p;θ∗)=A(p;θ∗)x+q(p;θ∗)+∇xΨ(x,p;θ∗)F(x,p;\theta^*)=A(p;\theta^*)x+q(p;\theta^*)+\nabla_x\Psi(x,p;\theta^*), where θ∗\theta^* is the learned parameter vector, A(p;θ∗)A(p;\theta^*) is parameterized as in (12a) and Ψ\Psi is convex in xx.

In the special case of a quadratic game (Ψ(x,p;θ∗)≡0\Psi(x,p;\theta^*)\equiv0), the Lipschitz constant of the pseudogradient is simply given by the spectral norm of the pseudogradient matrix AA, i.e., L(p)=∥A(p;θ∗)∥L(p)=\|A(p;\theta^*)\|. In the next proposition, we show how to compute an upper bound on L(p)L(p) for a specific class of input-convex neural networks Ψ(x,p;θ)\Psi(x,p;\theta). For further results on estimating Lipschitz constants of the gradient of neural networks, see, e.g., [?] and [?]. We will drop the explicit dependence on pp and θ∗\theta^* for notation simplicity.

Proposition 6.1. Let Ψ(x)\Psi(x) be an input-convex neural network with YY layers, softplus activation σ(t)=log⁡(1+et)\sigma(t)=\log(1+e^t), and linear bypass:

z1=σ(W0x+b0),zk+1=σ(Wkzk+Ukx+bk),k=1,…,Y−1z_1=\sigma(W_0x+b_0),\qquad z_{k+1}=\sigma(W_kz_k+U_kx+b_k),\qquad k=1,\ldots,Y-1
Ψ(x)=wYTzY+UYx+c\Psi(x)=w_Y^{\mathsf{T}}z_Y+U_Yx+c

where Wk≥0W_k \ge0 entrywise for k=1,…,Y−1k = 1, \ldots, Y - 1 and wY≥0w_Y \ge0 enforce convexity. Define the following scalar quantities recursively:

G1=∥W0∥,Gk+1=∥Wk∥Gk+∥Uk∥G_1 = \lVert W_0 \rVert,\qquad G_{k+1} = \lVert W_k \rVert G_k + \lVert U_k \rVert
H1=14G12,Hk+1=14Gk+12+∥Wk∥Hk,k=1,…,Y−1.H_1 = \frac{1}{4}G_1^2,\qquad H_{k+1} = \frac{1}{4}G_{k+1}^2 + \lVert W_k \rVert H_k,\qquad k = 1,\ldots,Y - 1.

Then ∇Ψ\nabla\Psi is Lipschitz continuous with constant LΨ≤∥wY∥2HYL_\Psi\le\lVert w_Y \rVert_2 H_Y.

Proof. Let pk=Wk−1zk−1+Uk−1x+bk−1p_k = W_{k-1}z_{k-1} + U_{k-1}x + b_{k-1}, zk=σ(pk)z_k = \sigma(p_k), and consider its Jacobian Dpk=Wk−1Dzk−1+Uk−1D p_k = W_{k-1}D z_{k-1} + U_{k-1} w.r.t. xx. We want to show that ∥Dpk(x)∥≤Gk\lVert Dp_k(x)\rVert\le G_k for all xx by induction on kk. Since p1=W0x+b0p_1 = W_0x + b_0 is affine in xx, the base case ∥Dp1∥=∥W0∥=G1≤G1\lVert Dp_1\rVert= \lVert W_0\rVert= G_1 \le G_1 trivially holds. Assume by induction that ∥Dpk−1(x)∥≤Gk−1\lVert Dp_{k-1}(x)\rVert\le G_{k-1}. Since zk−1=σ(pk−1)z_{k-1} = \sigma(p_{k-1}) is applied entrywise, Dzk−1=diag⁡(σ′(pk−1))Dpk−1Dz_{k-1} = \operatorname{diag}(\sigma'(p_{k-1}))Dp_{k-1} and, as σ′(t)∈(0,1)\sigma'(t) \in(0,1) for every tt, ∥Dzk−1(x)∥≤∥Dpk−1(x)∥≤Gk−1\lVert Dz_{k-1}(x)\rVert\le\lVert Dp_{k-1}(x)\rVert\le G_{k-1} for all xx. The triangle inequality and submultiplicativity of the spectral norm then give

∥Dpk(x)∥≤∥Wk−1Dzk−1(x)∥+∥Uk−1∥≤∥Wk−1∥∥Dzk−1(x)∥+∥Uk−1∥≤∥Wk−1∥Gk−1+∥Uk−1∥=Gk\begin{aligned} \lVert Dp_k(x)\rVert\le\lVert W_{k-1}Dz_{k-1}(x)\rVert+ \lVert U_{k-1}\rVert\le\lVert W_{k-1}\rVert\lVert Dz_{k-1}(x)\rVert+ \lVert U_{k-1}\rVert\\ &\le\lVert W_{k-1}\rVert G_{k-1} + \lVert U_{k-1}\rVert= G_k \end{aligned}

for all xx, which closes the induction.

Let us now compute a bound on the second derivative of one ICNN layer. Consider two arbitrary unit vectors uu, vv and let D2zk(x)[u,v]∈Rdim⁡zkD^2z_k(x)[u,v] \in\mathbb{R}^{\dim z_k} denote the vector with entries u⊤∇2(zk(x)i)vu^\top\nabla^2(z_k(x)_i)v. It is easy to show that

D2zk(x)[u,v]=σ′′(pk)⊙(Dpku)⊙(Dpkv)+σ′(pk)⊙(Wk−1D2zk−1(x)[u,v]).D^2z_k(x)[u,v] = \sigma''(p_k) \odot(Dp_ku) \odot(Dp_kv) + \sigma'(p_k) \odot(W_{k-1}D^2z_{k-1}(x)[u,v]).

Bounding σ′′≤14\sigma'' \le\frac{1}{4}, σ′≤1\sigma' \le1, and using ∥a⊙b∥2≤∥a∥2∥b∥2\lVert a \odot b\rVert_2 \le\lVert a\rVert_2\lVert b\rVert_2 and submultiplicativity of the spectral norm,

∥D2zk(x)[u,v]∥2≤14∥Dpku∥2∥Dpkv∥2+∥Wk−1∥∥D2zk−1(x)[u,v]∥2≤14Gk2+∥Wk−1∥Hk−1=Hk\begin{aligned} \lVert D^2z_k(x)[u,v]\rVert_2 \le\frac{1}{4}\lVert Dp_ku\rVert_2\lVert Dp_kv\rVert_2 + \lVert W_{k-1}\rVert\lVert D^2z_{k-1}(x)[u,v]\rVert_2 \\ &\le\frac{1}{4}G_k^2 + \lVert W_{k-1}\rVert H_{k-1} = H_k \end{aligned}

which is the claimed induction (H1H_1 is the base case, z1z_1 having no incoming WW-term). Since Ψ(x)=wY⊤zY(x)+UYx+c\Psi(x) = w_Y^\top z_Y(x) + U_Yx + c with the bypass UYxU_Yx affine and hence contributing no curvature,

∣u⊤∇2Ψ(x)v∣=∣wY⊤D2zY(x)[u,v]∣≤∥wY∥2∥D2zY(x)[u,v]∥2≤∥wY∥2HY\lvert u^\top\nabla^2\Psi(x)v\rvert= \lvert w_Y^\top D^2z_Y(x)[u,v]\rvert\le\lVert w_Y\rVert_2\lVert D^2z_Y(x)[u,v]\rVert_2 \le\lVert w_Y\rVert_2H_Y

for all unit vectors uu, vv and all xx, so ∥∇2Ψ(x)∥≤∥wY∥2HY\lVert\nabla^2\Psi(x)\rVert\le\lVert w_Y\rVert_2H_Y.

Finally, a bound on the Lipschitz constant LL of the pseudogradient FF for a given surrogate game instance follows from the triangle inequality:

L≤∥wY∥2HY+∥A∥.(29)L \le\lVert w_Y\rVert_2H_Y + \lVert A\rVert. \tag*{(29)}

Numerical examples

In all the experiments reported below, the exact equilibrium x⋆(p)x^\star(p) of the true game at each test value of pp is computed by the KKT-residual method implemented in the NashOpt package [?] that, for unconstrained games, reduces to finding a zero of the pseudogradient.

All numerical tests were run in Python 3.11 on a MacBook Pro with Apple M5 Max (18 CPU cores). Models are trained using the jax-sysid package [?], by running 1000 Adam iterations followed by at most 5000 L-BFGS iterations from 18 random initializations in parallel, keeping the model with the smallest loss on a separate validation dataset of KvalK_{\mathrm{val}} samples. Input-convexity of neural networks is enforced by applying the softplus function both to the weights of the layers that are required to be nonnegative and to the hidden layers. Unless otherwise specified, γ=10\gamma= 10 and ρ=10−8\rho= 10^{-8}.

To verify the quality of approximate solutions x^(p)\hat{x}(p) for a given pp, we evaluate each best response (BR) by fixing x−i=x^−i(p)x_{-i} = \hat{x}_{-i}(p) and optimizing the underlying agents costs J~i\tilde{J}_i, possibly subject to shared constraints (unless specified otherwise), NE of the underlying true game {J~i}i=1N\{\tilde{J}_i\}_{i=1}^{N} are evaluated via the minimization of the squared pseudogradient norm ∥∇F~(x,p)∥2\lVert\nabla\tilde{F}(x,p)\rVert^2 or, in the case of shared constraints, a variational GNE is evaluated by minimizing the KKT residuals as described in [?]. Both the BR and NE errors reported in the tables are evaluated as 1NKtest∑k=1Ktest∑i=1N∥x^i(pk)−xˉi(pk)∥2\frac{1}{N K_{\mathrm{test}}}\sum_{k=1}^{K_{\mathrm{test}}}\sum_{i=1}^{N}\lVert\hat{x}_i(p_k)-\bar{x}_i(p_k)\rVert^2 over the test samples pkp_k, where xˉi(pk)\bar{x}_i(p_k) are either the ground truth BR to x^−i(p)\hat{x}_{-i}(p) or NE, respectively.

The code to reproduce the examples reported in this section is available at https://github.com/bemporad/learn_monotone_games.

Convex quadratic games

We consider a randomly generated parametric quadratic game (17) with N=4N = 4 agents, ni=2n_i = 2 decision variables each, and a vector parameter p∈[−1,1]2p \in[-1,1]^2 entering only the linear terms, qi(p)=c1ip+c2iq_i(p) = c_{1i}p + c_{2i}, while AiiA_{ii}, Ai,−iA_{i,-i} are constant. The blocks AiiA_{ii}, Ai,−iA_{i,-i}, c1ic_{1i}, c2ic_{2i} are drawn at random, and the diagonal blocks are shifted so that the symmetric part of the pseudogradient Jacobian AA has minimum eigenvalue exactly μ=0\mu= 0, i.e., the game is monotone but not strongly monotone.

We first fit a monotone quadratic cost model of the form eq:12 with μ=0\mu= 0, each nonzero entry in CC, DD constant with respect to pp, and qq affine in pp. We use K=500K = 500 cost samples (xk,pk,{J~i(xk,pk)}i=1N)(x_k,p_k,\{\tilde{J}_i(x_k,p_k)\}_{i=1}^{N}), k=1,…,Kk = 1,\ldots,K, with xk∈[−2,2]8x_k \in[-2,2]^8, by minimizing LDJ(θ)+ρ2∥θ∥2L_{DJ}(\theta) + \frac{\rho}{2}\lVert\theta\rVert^2, θ∈R572\theta\in\mathbb{R}^{572}. No NE-sample data is used (KNE=0K_{\mathrm{NE}} = 0) and Kval=100K_{\mathrm{val}} = 100, Ktest=200K_{\mathrm{test}} = 200 are generated similarly as held-out validation and test samples, respectively. The learned model is validated by computing its Nash equilibria at 50 different random test values of pp by solving the linear system F(x,p)=0F(x,p) = 0, and comparing it against the true NE of the underlying game generating the data, obtained similarly for each test pp. The results are shown in the first row of Table 1, which reports the mean BR and NE errors on test data.

methoddatatime (s)BR errorNE error
NLSJi,kJ_{i,k}8.72632.62⋅10−72.62 \cdot10^{-7}6.05⋅10−76.05 \cdot10^{-7}
SDPxˉi,k\bar{x}_{i,k}1.50162.79⋅10−82.79 \cdot10^{-8}6.58⋅10−86.58 \cdot10^{-8}
LS+SDPxˉi,k\bar{x}_{i,k}0.00651.70⋅10−81.70 \cdot10^{-8}3.30⋅10−83.30 \cdot10^{-8}
NLSxˉi,k\bar{x}_{i,k}8.34261.14⋅10−81.14 \cdot10^{-8}3.02⋅10−83.02 \cdot10^{-8}

Table 1. Comparison of learning approaches on randomly-generated parametric quadratic games.

Then, we address the inverse-learning problem described in Section 5, generating the same number KK, KvalK_{\mathrm{val}}, and KtestK_{\mathrm{test}} of best-response data (x−i,k,pk,x~i,k)(x_{-i,k},p_k,\tilde{x}_{i,k}). We compare three approaches: (i) the SDP (20) solved directly (“SDP”); (ii) the least-squares/SDP cascade (22)–(24) (“LS+SDP”); (iii) the nonlinear least-squares problem (19) with a small regularization ρ=10−12\rho= 10^{-12} (“NLS”), all imposing μ=0\mu= 0.

The results are also summarized in Table 1. The LS+SDP cascade is three orders of magnitude faster than solving the SDP directly, since it only requires an unconstrained linear least-squares fit followed by a small SDP. The NLS approach is the best in solving the inverse learning problem, but only marginally.

Monotone counterexample

Consider the following parametric version of the monotone game of Remark 4.3

J1(x,p)=12(x1−p1)2+(x1−p1)sin⁡(x2−p2)J2(x,p)=12(x2−p2)2−(x2−p2)sin⁡(x1−p1)(30)\begin{aligned} J_1(x,p) &= \frac{1}{2}(x_1-p_1)^2 + (x_1-p_1)\sin(x_2-p_2) \\ J_2(x,p) &= \frac{1}{2}(x_2-p_2)^2 - (x_2-p_2)\sin(x_1-p_1) \tag*{(30)} \end{aligned}

that does not admit the exact parameterization of Section 4. Its unconstrained NE is x∗(p)=px^*(p) = p. We learn the costs from K=2000K = 2000 samples of DJD_J, drawn uniformly from x∈[−π2,π2]2x \in[-\frac{\pi}{2}, \frac{\pi}{2}]^2 and p∈[−π4,π4]2p \in[-\frac{\pi}{4}, \frac{\pi}{4}]^2, by minimizing (8) with LD=LDJ\mathcal{L}_D = \mathcal{L}_{DJ} as in (4) with μ=0.2\mu= 0.2.

We compare four approaches: (i) monotonicity by construction, with costs parameterized as in (10), A(p)A(p) as in (12a), Ψ\Psi given by an input-convex neural network, and C(p)C(p), D(p)D(p), q(p)q(p), ϕi\phi_i by neural networks (LM=0\mathcal{L}_M = 0); (ii)–(iv) input-convex neural-network costs JiJ_i with the monotonicity penalties LM1\mathcal{L}_{M_1} (7a), LM2\mathcal{L}_{M_2} (7b), and LM3\mathcal{L}_{M_3} (7c), respectively, with γ=103\gamma= 10^3 and M=2000M = 2000 unlabeled samples in DMD_M (M=50M = 50 for LM1\mathcal{L}_{M_1}, whose evaluation cost grows quadratically with MM). All networks have two hidden layers of 4 neurons each and Kval=1000K_{\mathrm{val}} = 1000 validation samples are used to select the best model. The learned NE is computed by solving F(x,p;θ)=0F(x,p;\theta) = 0 at 50 random test values of pp and compared with the exact NE x∗(p)=px^*(p) = p. Average fitting of the agents’ costs is evaluated over Ktest=2000K_{\mathrm{test}} = 2000 test samples.

As the penalty methods do not guarantee monotonicity, we also compute the minimum eigenvalue of the symmetric part of the learned pseudogradient Jacobian at the test samples and over the whole box by global optimization, using the algorithm DIRECT [?, ?] for global optimization (absolute tolerance 10−810^{-8}, relative tolerance 10−510^{-5}, max 2000 evaluations).

The obtained results are summarized in Table 2. The best fit of the costs is obtained by the penalty methods LM1\mathcal{L}_{M_1} and LM2\mathcal{L}_{M_2}, which also achieve the smallest NE error. However, they do not guarantee the imposed strong monotonicity μ=0.2\mu= 0.2. The monotonicity-by-construction approach achieves a slightly worse fit of the costs and NE error, but satisfies the imposed monotonicity requirement. The penalty method LM3\mathcal{L}_{M_3} achieves a worse fit of the costs and NE error and a larger monotonicity constant. We report that lower values of μ\mu, such as μ=0\mu= 0, may lead the penalty-based methods to learn non-monotone games, due to the limited density of samples in the training set and the value of the penalty γ\gamma.

methodtime (s)λmin⁡\lambda_{\min} (test/global)R2R^2 (%)NE error
monotonic (10)39.290.3087 / 0.274198.780.0424
ICNN + LM1\mathcal{L}_{M_1} (7a)50.930.0662 / 0.021799.990.0039
ICNN + LM2\mathcal{L}_{M_2} (7b)108.380.1154 / 0.091099.980.0053
ICNN + LM3\mathcal{L}_{M_3} (7c)128.440.5105 / 0.485696.750.0528

Table 2. Comparison of learning approaches on example (25).

Convex nonlinear game

We consider the parametric variant of the internet switching model described in [?], Ex. A.1:

Ji(x,q)=−xix1+⋯+xN(1−(x1+⋯+xN)q)J_i(x,q)=-\frac{x_i}{x_1+\cdots+x_N}\left(1-(x_1+\cdots+x_N)q\right)
∑i=1Nxi≤1/q,xi≥0.01(31)\sum_{i=1}^{N}x_i\leq1/q,\qquad x_i\geq0.01 \tag*{(31)}

where ℓ=0.01\ell= 0.01 and q∈[0.5,1/(Nℓ)]q \in[0.5,1/(N\ell)] is treated as the parameter of the game. This variant, with parameter p=1/qp = 1/q, was suggested in [?], showing the convexity of costs JiJ_i and the analytical expression of the best response xˉi(x−i,q)\bar{x}_i(x_{-i},q). We generate random feasible K=Kval=Ktest=4000K = K_{\mathrm{val}} = K_{\mathrm{test}} = 4000 training, validation, and test samples, respectively, as described in [?]. We test both a pure quadratic monotone model (12) with C(p)C(p), D(p)D(p), q(p)q(p) given by (input-convex) neural networks, and a nonlinear monotone model given by adding an input-convex neural network potential term Ψ\Psi with 2 hidden layers of 20 neurons each. No additional term ϕi\phi_i is introduced and we set LM=0\mathcal{L}_M = 0.

We evaluate and compare the best responses of the learned models against the exact best responses on a further 200 random test values of pp, and solve both the GNEP (26) and the GNEP with the learned models, under the same constraints, on 50 random test values of pp. The results are summarized in Table 3. The learned models achieve a good fit of the costs, measured by the R2R^2-score on the test set averaged on all agents’ costs, BR and NE errors.

potentialtime (s)R2R^2 (%)BR errorNE error
none72.586194.621.79×10−21.79 \times10^{-2}3.60×10−33.60 \times10^{-3}
NN300.666495.401.43×10−21.43 \times10^{-2}4.69×10−34.69 \times10^{-3}

Table 3. Learned generalized Nash equilibrium models for the internet switching game with N=5N = 5 players.

Comparison with approximate explicit GNE method

We compare the approach of Section 4 against the explicit-solution approach of [?], which learns a neural-network approximation x^(p)\hat{x}(p) of the parametric map p↦x∗(p)p \mapsto x^*(p) from best-response samples and knowledge of the true agents’ costs JiJ_i.

Parametric convex quadratic GNEP with shared linear constraints

We first consider a randomly generated parametric monotone linear-quadratic GNEP (LQ-GNEP) (12b) with N=3N = 3 agents, ni=2n_i = 2 decision variables each, m=16m = 16 shared inequality and q=2q = 2 shared equality constraints (both known), and strong-monotonicity constant μ=0.1\mu= 0.1. Two parameters p∈[−1,1]2p \in[-1,1]^2 enter both the linear cost terms, ci(p)=ci0+Fipc_i(p) = c_{i0} + F_i p, and the shared constraint right-hand side, b(p)=b0+Spb(p) = b_0 + Sp with S>0S > 0.

Using K=2000K = 2000 best-response training samples, Kval=1000K_{\mathrm{val}} = 1000 validation, and Ktest=1000K_{\mathrm{test}} = 1000 test samples generated as in [?] by projecting randomly-generated vectors vk∈[−10,10]6v_k \in[-10,10]^6 on the feasible set, we train the explicit map x^(p)\hat{x}(p) of [?] using a NN with two hidden layers (30,20) neurons with swish activation per agent to approximate its associated value function, and a NN with (30,20)(30,20) neurons and ReLU activation with linear bypass for the solution x^(p)∈R6\hat{x}(p) \in\mathbb{R}^{6} (the latter has 888 weights to learn). We then fit a quadratic surrogate (12), with constant AA and μ=0\mu= 0, on the same (xk,pk)(x_k,p_k) samples and the corresponding costs J~i(xk,pk)\tilde{J}_i(x_k,p_k), by minimizing LDJ(θ)+ρ2∥θ∥2\mathcal{L}_{DJ}(\theta) + \frac{\rho}{2}\lVert\theta\rVert^2. Note that only mere monotonicity is imposed on the surrogate, as the true μ\mu is assumed unknown. At test time, the surrogate GNE is recovered online for each pp by solving the QP-GNEP with the same shared constraints Ax≤b(p)Ax \le b(p), Ex=hEx = h via the proximal-QP method of [?] (using the daqp solver [2]).

Table 4 compares the solutions obtained against the ground-truth GNE, computed by the same proximal-QP method, over the 1000 test parameters. The surrogate is superior on every metric except online evaluation time (a forward pass through the solution NN x^(p)\hat{x}(p) vs. solving a QP to evaluate the GNE for each tested pp). In particular, solving the surrogate GNE online always returns a feasible equilibrium, whereas the explicit map of [?], being an unconstrained function approximator of a constrained map, slightly violates the shared constraints. Note also that the approach of [?] requires fitting convex piecewise-quadratic value functions, while the approach of Section 4 has the easier task of fitting the agent’s convex quadratic costs. On the other hand, the former approach is more general, as it can be applied to any parametric nonconvex GNEP, while the latter is limited to fitting parametric convex monotone GNEPs.

explicit [?]surrogate
best-response error (mean)3.4646⋅10−13.4646 \cdot10^{-1}5.2079⋅10−145.2079 \cdot10^{-14}
constraint violation (mean)3.4241⋅10−43.4241 \cdot10^{-4}6.3303⋅10−156.3303 \cdot10^{-15}
constraint violation (max)1.1252⋅10−11.1252 \cdot10^{-1}2.5821⋅10−132.5821 \cdot10^{-13}
opt.cost/cost fit (average R2\mathrm{R}^{2} score)0.99630.99631.00001.0000
fitting time (s)68.9368.9311.9211.92
per-sample solve time (μ\mus)22.8222.82297.99297.99

Table 4. Approximate explicit GNE solution [?] vs. LQ-GNE surrogates on a random strongly-monotone LQ-GNEP.

Parametric nonlinear convex GNEP with shared linear constraints

We repeat the comparison on a parametric nonlinear convex underlying game defined by

fi(x,p)=log⁡(∑r=13eairTxi+birTx−i+γirTp)+(1+p1+p2)∑i=1N∑j=1ni(110(xi)j)4(32)f_i(x,p) = \log\left(\sum_{r=1}^{3} e^{a_{ir}^{\mathsf{T}}x_i+b_{ir}^{\mathsf{T}}x_{-i}+\gamma_{ir}^{\mathsf{T}}p}\right) + (1+p_1+p_2)\sum_{i=1}^{N}\sum_{j=1}^{n_i}\left(\frac{1}{10}(x_i)_j\right)^4 \tag*{(32)}

with N=2N = 2 agents, ni=2n_i = 2 decision variables each, 2 parameters p∈[.5,1]2p \in[.5,1]^2, aira_{ir}, birb_{ir}, γir\gamma_{ir} drawn at random, m=10m = 10 shared inequality constraints Ax≤b(p)Ax \le b(p), b(p)=b0+Spb(p) = b_0 + Sp with S≥0S \ge0, and box constraints −2≤x≤2-2 \le x \le2. The game defined by (27) is not monotone for the selected values of vectors birb_{ir}.

Both the training data for [?]’s explicit map and the ground-truth best responses used to score all methods are computed by a generic penalty-constrained L-BFGS-B solve of each agent’s subproblem (via nashopt.GNEP [?]). We fit [?]’s explicit map x^(p)\hat{x}(p) as in the previous section, using K=2000K = 2000 training, Kval=1000K_{\mathrm{val}} = 1000 validation, and Ktest=1000K_{\mathrm{test}} = 1000 test samples, and a monotone surrogate (12) whose matrices C(p)C(p), D(p)D(p) and offset q(p)q(p) are emitted by a hypernetwork (two hidden layers of 5 neurons each, ReLU activation), augmented with an input-convex potential Ψ(x,p)\Psi(x,p) (two hidden layers of 5 neurons each, softplus activation) common to all agents’ costs.

At test time, a v-GNE of the surrogate monotone game is recovered by running Korpelevich’s extragradient method [?] with step size 0.99/L(p)0.99/L(p), where the Lipschitz constant L(p)L(p) of the pseudogradient of the learned surrogate game is computed as described in Proposition 6.1. To properly initialize the method, we fit a second explicit map x^s(p)\hat{x}_s(p) on value-function samples of the surrogate game, and use x^s(p)\hat{x}_s(p) to initialize the extragradient method, which is then run for 50 iterations.

Table 5 compares the two solutions on the test parameters. The surrogate attains a much more accurate best-response, near-zero constraint violation, and a higher cost-fit R2R^2 than the explicit map, at the cost of a more expensive online evaluation via Korpelevich’s method rather than a single forward NN pass.

explicit [?]surrogate
best-response error (mean)4.2598⋅10−24.2598 \cdot10^{-2}1.2969⋅10−51.2969 \cdot10^{-5}
constraint violation (mean)6.7551⋅10−66.7551 \cdot10^{-6}9.3644⋅10−99.3644 \cdot10^{-9}
constraint violation (max)3.5215⋅10−33.5215 \cdot10^{-3}9.5764⋅10−99.5764 \cdot10^{-9}
opt.cost/cost fit (average R2R^2 score)0.98340.9970
fitting time (s)10.5644.52
per-sample solve time (s)1.92⋅10−51.92 \cdot10^{-5}1.74⋅10−11.74 \cdot10^{-1}

Table 5. Approximate explicit GNE solution [?] vs. monotone surrogate (with potential term) on the nonlinear convex game (27).

Inverse learning of a monotone game-theoretic controller

We consider the three-input stirred tank depicted in Figure 1. The tank is fed by a pure-water stream q1q_1 and two reactant-feed streams q2q_2 (species A) and q3q_3 (species B) draining through an orifice, with a second-order reaction A+B→A+B \to product. The dynamics of the states ξ=[h CA CB]T\xi= [h\ C_A\ C_B]^{\mathsf{T}} under the input

Figure 1. Three-input stirred tank reactor.

u=[q1 q2 q3]⊤u = [q_1\ q_2\ q_3]^{\top} are described by the following system of nonlinear ordinary differential equations:

h˙=1S(q1+q2+q3−cvh)C˙A=q2(CA,in−CA)−(q1+q3)CASh−kCACBC˙B=q3(CB,in−CB)−(q1+q2)CBSh−kCACB(33)\begin{aligned} \dot{h} &= \frac{1}{S}(q_1+q_2+q_3-c_v\sqrt{h}) \\ \dot{C}_A &= \frac{q_2(C_{A,\mathrm{in}}-C_A)-(q_1+q_3)C_A}{Sh}-kC_AC_B \\ \dot{C}_B &= \frac{q_3(C_{B,\mathrm{in}}-C_B)-(q_1+q_2)C_B}{Sh}-kC_AC_B \tag*{(33)} \end{aligned}

where each physical quantity is described in Table 6. We control the system by three decentralized single-input single-output PI loops regulating the three outputs hh, CAC_A, and CBC_B to the corresponding setpoints hsph_{\mathrm{sp}}, CA,spC_{A,\mathrm{sp}}, and CB,spC_{B,\mathrm{sp}} by manipulating the three flows q1q_1, q2q_2, and q3q_3, respectively. To this end, we linearize (33) and get ξ˙=Ac(ξ−ξ0)+Bc(u−u0)\dot{\xi} = A_c(\xi-\xi_0)+B_c(u-u_0), where ξ0\xi_0, u0u_0 are the nominal operating points also reported in Table 6. To have each PI loop treat the other inputs as measured disturbances, we decouple the three loops by a static feedforward matrix Dm=Bc−1diag⁡(Bc)D_m = B_c^{-1}\operatorname{diag}(B_c). The resulting PI control laws are:

DescriptionNominal value
h‾(t)\overline{h}(t)liquid level in the tank; 0.60.6 [m]
V(t)V(t)liquid volume in the tank, V=AhV = Ah; 0.60.6 [m3^3]
CA(t)C_A(t)concentration of reactant AA in the tank; 0.50.5 [mol/L]
CB(t)C_B(t)concentration of reactant BB in the tank; 0.30.3 [mol/L]
q1(t)q_1(t)flow rate of pure water (input); 0.10860.1086 [m3^3/s]
q2(t)q_2(t)flow rate of the AA-feed solution (input); 0.17920.1792 [m3^3/s]
q3(t)q_3(t)flow rate of the BB-feed solution (input); 0.17700.1770 [m3^3/s]
qout(t)q_{\mathrm{out}}(t)outlet flow rate; 0.46480.4648 [m3^3/s]
CA,inC_{A,\mathrm{in}}concentration of AA in stream 2 (parameter); 2.02.0 [mol/L]
CB,inC_{B,\mathrm{in}}concentration of BB in stream 3 (parameter); 1.51.5 [mol/L]
SStank cross-sectional area (parameter); 1.01.0 [m2^2]
cvc_vTorricelli discharge coefficient (parameter); 0.60.6 [m2.5^{2.5}/s]
kkreaction rate constant (parameter); 1.41.4 [L/(mol s)]

Table 6. Physical quantities and parameters of the stirred-tank reactor example and their nominal values.

e(t)=[hsp(t)−h(t)CA,sp(t)−CA(t)CB,sp(t)−CB(t)],v(t)=Kpe(t)+KiI(t)e(t) = \begin{bmatrix} h_{\mathrm{sp}}(t)-h(t) \\ C_{A,\mathrm{sp}}(t)-C_A(t) \\ C_{B,\mathrm{sp}}(t)-C_B(t) \end{bmatrix}, \qquad v(t)=K_p e(t)+K_i I(t)
I˙i(t)=ei(t)(34)\dot{I}_i(t)=e_i(t) \tag*{(34)}
u(t)=max⁡(u0+Dmv(t),0)(35)u(t)=\max\left(u_0+D_m v(t),0\right) \tag*{(35)}

with Kp=diag⁡(1.5492, 0.0956, 0.0737)K_p=\operatorname{diag}(1.5492,\ 0.0956,\ 0.0737), Ki=diag⁡(0.6000, 0.1142, 0.1087)K_i=\operatorname{diag}(0.6000,\ 0.1142,\ 0.1087).

We generate the training, validation, and test data by simulating the decentralized PI closed loop ((33)–eq:29) for Tsim=1999T_{\mathrm{sim}}=1999 s under piecewise-constant random setpoints hsph_{\mathrm{sp}}, CA,spC_{A,\mathrm{sp}}, CB,spC_{B,\mathrm{sp}} that change every 50 s to a new value drawn uniformly around h0h_0, CA0C_{A0}, CB0C_{B0}, sampling the state, setpoints, and PI integrator states every Ts=1T_s=1 s. Our working assumption is to consider each of the resulting Tsim/Ts+1=2000T_{\mathrm{sim}}/T_s+1=2000 input samples as a best-response x‾k=[q1 q2 q3](tk)\overline{x}_k=[q_1\ q_2\ q_3](t_k) to the parameter pk=[h, CA, CB, hsp, CA,sp, CB,sp, Ih, IA, IB](tk)p_k=[h,\ C_A,\ C_B,\ h_{\mathrm{sp}},\ C_{A,\mathrm{sp}},\ C_{B,\mathrm{sp}},\ I_h,\ I_A,\ I_B](t_k), per agent i∈{1,2,3}i\in\{1,2,3\}, for a total of $3\times2000=6000 samples, which we split randomly into 80% training, 10% validation, and 10% test sets (4800, 600, and 600 rows, respectively).

Next, we learn a monotone quadratic game-theoretic model (10) of the three agents’ best responses by solving the inverse problem (15) with μ=0\mu= 0, LM=0\mathcal{L}_{M} = 0, using the least-squares/SDP cascade (17)–(19), obtaining an average best-response error of 1.55⋅10−41.55 \cdot10^{-4}. The corresponding symmetric part of the learned constant pseudogradient matrix AA is positive semidefinite with eigenvalues 0.6135, 1.1273, and 1.2592.

Finally, we test the closed-loop system obtained by replacing the three PI loops with a game-theoretic controller that computes the GNE of the learned monotone game at each time step under the shared constraints 0.4≤q1+q2+q3≤0.50.4 \le q_{1} + q_{2} + q_{3} \le0.5 and local constraints qi≥0q_{i} \ge0, i=1,2,3i = 1, 2, 3 using the proximal-QP method proposed in [?] and the DAQP solver [2] to solve each QP instance. The results are shown in Figure 2. The learned game-theoretic controller achieves a performance very close to the original PI controller within the admissible range of total flow constraints, and is able to enforce the shared constraint on the total flow in a game-theoretic manner, which was not possible with the decentralized PI controller.

Figure 2. Closed-loop response of the stirred-tank reactor under the discrete-time GNE-based game-theoretic controller.

Conclusions

We addressed the problem of learning a parametric NE problem, directly from agents’ cost values or from their best responses, satisfying given monotonicity requirements for all parameter values. A penalty-based method promotes monotonicity on training data without certifying it elsewhere, while a structured parameterization, based on a representation of the pseudogradient as a convex potential plus a skew-symmetric affine term, guarantees monotonicity by construction and covers all monotone convex quadratic games, whose inverse learning reduces to an SDP. Numerical results confirm that, in spite of the limitations of the chosen model classes, convex monotone parametric games can be learned rather accurately.

Future work includes extending the representation to other classes of learnable monotone games that include state-dependent skew-symmetric terms, and to applications of the proposed methods to learn monotone game-theoretic model predictive control laws from observed input/state trajectories.

References

  1. [1]A. Agrawal, B. Amos, S. Barratt, S. Boyd, S. Diamond, and J.Z. Kolter. Differentiable convex optimization layers. Advances in neural information processing systems, 32, 2019.arxiv.org/abs/1910.12430
  2. [2]D. Arnström, A. Bemporad, and D. Axehill. A dual active-set solver for embedded quadratic programming using recursive LDLᵀ updates. 67(8):4362–4369, 2022.
  3. [3]D. Bauso. Game Theory with Engineering Applications. SIAM, 2016.DOI
  4. [4]G. Belgioioso, A. Nedić, and S. Grammatico. Distributed generalized Nash equilibrium seeking in aggregative games on time-varying networks. IEEE Transactions on Automatic Control, 66(6):2582–2597, 2021.DOI
  5. [5]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, 2022.DOI

Paper details

vlnc:W_wz53h4bb
Version
v1 · latest
Published
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