Projected-gradient algorithms for Generalized Equilibrium seeking in
Aggregative Games are preconditioned Forward-Backward methods

arXiv:1803.10441v1 [math.OC] 28 Mar 2018

Giuseppe Belgioioso
Abstract— We show that projected-gradient methods for the
distributed computation of generalized Nash equilibria in aggregative games are preconditioned forward-backward splitting
methods applied to the KKT operator of the game. Specifically,
we adopt the preconditioned forward-backward design, recently
conceived by Yi and Pavel in the manuscript “A distributed
primal-dual algorithm for computation of generalized Nash
equilibria via operator splitting methods” for generalized Nash
equilibrium seeking in aggregative games. Consequently, we
notice that two projected-gradient methods recently proposed
in the literature are preconditioned forward-backward methods. More generally, we provide a unifying operator-theoretic
ground to design projected-gradient methods for generalized
equilibrium seeking in aggregative games.

I. I NTRODUCTION
Aggregative game theory [1] is a mathematical framework to model the interdependent optimal decision making
problems for a set of noncooperative agents, whenever the
decision of each agent is affected by some aggregate effect
of all the agents. This feature emerges in several application
areas, such as demand side management in the smart grid
[2], e.g. for electric vehicles [3], [4] and thermostatically
controlled loads [5], [6], demand response in competitive
markets [7] and network congestion control [8].
Existence and uniqueness of Nash equilibria in (aggregative) noncooperative games is well established in the literature of operation research [9], [10, §12], and automatic
control [11], [12]. For the computation of a game equilibrium, several algorithms are available, both distributed
protocols [13], [14] and semi-decentralized schemes [15],
[16], [17], [18]. Among these, an elegant approach is to
characterize the desired equilibrium solutions as the zeros
of an operator, possibly monotone, e.g. the concatenation of
interdependent Karush–Kuhn–Tucker operators, and in turn
formulate an equivalent fixed-point problem, which is solved
via appropriate fixed-point iterations. Overall, the available
methods can ensure global convergence to an equilibrium if
the coupling among the cost functions of the agents is “well
behaved”, e.g. if the problem data are convex and the socalled pseudo-gradient game mapping is (strictly, strongly)
monotone [19].
G. Belgioioso is with the Control Systems group, TU Eindhoven,
The Netherlands. S. Grammatico is with the Delft Center for Systems
and Control (DCSC), TU Delft, The Netherlands. E-mail addresses:
g.belgioioso@tue.nl, s.grammatico@tudelft.nl. This work
was partially supported by the Netherlands Organisation for Scientific
Research (NWO) under research projects OMEGA (grant n. 613.001.702)
and P2P-TALES (grant n. 647.003.003).

Sergio Grammatico
A popular class of algorithms for Nash equilibrium seeking is that of projected-gradient algorithms [20, §12], [14],
[16], [19]. Whenever the pseudo-gradient game mapping is
strongly monotone, projected-gradient algorithms can ensure
fast convergence to a Nash equilibrium, possibly via distributed computation and information exchange. It follows
that projected-gradient methods have the potential to be fast,
simple and scalable with respect to the population size. At
the same time, in the context of Nash equilibrium seeking,
the convergence analyses for the available projected-gradient
methods are quite diverse in nature.
In this paper, we aim at a unifying convergence analysis
for projected-gradient algorithms that are adopted for the
computation of generalized Nash equilibria in aggregative
games. Specifically, we adopt a general perspective based
on monotone operator theory [21] to show that projectedgradient algorithms with sequential updates belong to the
class of preconditioned forward-backward splitting methods,
introduced in [22] for multi-agent network games.
The main technical contribution of the paper is to conceive
a design procedure for the preconditioned forward-backward
splitting method. The proposed design is based not only
on the splitting of the monotone operator whose zeros are
the game equilibria, but also on the choice of the socalled preconditioning matrix, which induces the quadratic
norm adopted to show global convergence of the resulting
algorithm. Since the convergence characterization of the
forward-backward splitting method is well established, the
advantage of the proposed design is that global convergence
follows provided that some mild monotonicity assumptions
on the problem data are satisfied.
Remarkably, we discover that two recent projectedgradient algorithms for Nash equilibrium seeking in aggregative games, [16] and [14], can be equivalently written
as preconditioned forward-backward splitting methods with
symmetric preconditioning matrix, despite their algorithmic
formulation is “asymmetric”.
Basic notation
R denotes the set of real numbers, and R := R ∪ {∞} the
set of extended real numbers. 0 (1) denotes a matrix/vector
with all elements equal to 0 (1); to improve clarity, we may
add the dimension of these matrices/vectors as subscript.
A ⊗ B denotes the Kronecker product between matrices
A and B; kAk denotes the maximum singular value of A;
eig(A) denotes the set of eigenvalues of A. Given N vectors


⊤ ⊤
x1 , . . . , xN ∈ Rn , x := col (x1 , . . . , xN ) = x⊤
.
1 , . . . , xN

Operator theoretic definitions
Id(·) denotes the identity operator. The mapping ιS :
Rn → {0, ∞} denotes the indicator function for the set
S ⊆ Rn , i.e., ιS (x) = 0 if x ∈ S, ∞ otherwise. For a
closed set S ⊆ Rn , the mapping projS : Rn → S denotes
the projection onto S, i.e., projS (x) = argminy∈S ky − xk.
The set-valued mapping NS : Rn ⇒ Rn denotes the normal
cone operator
for the the set S ⊆ Rn , i.e., NS (x) = ∅ if

x∈
/ S, v ∈ Rn | supz∈S v ⊤ (z − x) ≤ 0 otherwise. For a
function ψ : Rn → R, dom(ψ) := {x ∈ Rn | ψ(x) < ∞};
∂ψ : dom(ψ) ⇒ Rn denotes its subdifferential set-valued
mapping, defined as ∂ψ(x) := {v ∈ Rn | ψ(z) ≥ ψ(x) +
v ⊤ (z − x) for all z ∈ dom(ψ)}; A set-valued mapping
F : Rn ⇒ Rn is ℓ-Lipschitz continuous, with ℓ > 0, if
ku − vk ≤ ℓkx − yk for all x, y ∈ Rn , u ∈ F (x), v ∈ F (y);
F is (strictly) monotone if (u − v)⊤ (x − y) ≥ (>) 0 for
all x 6= y ∈ Rn , u ∈ F (x), v ∈ F (y); F is η-strongly
monotone, with η > 0, if (u − v)⊤ (x − y) ≥ η kx − yk2
for all x, y ∈ Rn , u ∈ F (x), v ∈ F (y); F is η2
2
averaged, with η ∈ (0, 1), if kF (x) − F (y)k ≤ kx − yk −
2
1−η
n
η k(Id − F ) (x) − (Id − F ) (y)k , for all x, y ∈ R ; F
1
is β-cocoercive, with β > 0, if βF is 2 -averaged. With
JF := (Id + F )−1 , we denote the resolvent operator of F ,
which is 21 -averaged if and only if F is monotone; fix (F ) :=
{x ∈ Rn | x ∈ F (x)} and zer (F ) := {x ∈ Rn | 0 ∈ A(x)}
denote the set of fixed points and of zeros, respectively.
II. G ENERALIZED AGGREGATIVE

GAMES

A. Mathematical formulation
We consider a set of N noncooperative agents, where
each agent i ∈ N := {1, · · · , N } shall choose its decision variable (i.e., strategy) xi from the local decision
set Ωi ⊆ Rn with the aim of minimizing its local cost
function (xi , x−i ) 7→ Ji (xi , x−i ) : Rn × Rn(N −1) → R,
which depends on both the local variable xi (first argument)
and on the decision variables of the other agents, x−i =
col ({xj }j6=i ) (second argument).
We focus on the class of aggregative games, where the
cost function of each agent depends on the local decision
variable and
of the aggregation function σ :
PNon the value
n
Ω
⊆
R
,
with Ω := Ω1 × . . . × ΩN . In
Ω → N1
j
j=1
particular, we consider average aggregative games, where the
aggregation function is the average function, i.e.,
PN
1 ⊤
σ(x) := M x = N1
i=1 xi , hence M := N 1N ⊗ In . (1)
Thus, for each i ∈ N , there is a function fi : Rn ×Rn → R
such that the local cost function J i can be written as
Ji (xi , x−i ) =: fi (xi , σ(x)) .

(2)

Furthermore, we consider generalized games, where the
coupling among the agents arises not only via the cost
functions, but also via their feasible decision sets. In our
setup, the coupling constraints are described by an affine
function, x 7→ Ax − b, where A ∈ Rm×nN and b ∈ Rm .
Thus, the collective feasible set, X ⊆ RnN , reads as

(3)
X = Ω ∩ y ∈ RnN | Ay − b ≤ 0m ;

while the feasible decision set of each agent i ∈ N
is characterized
 by the set-valued mapping
PN Xi , defined as
Xi (x−i ) := yi ∈ Ωi | Ai yi ≤ b − j6=i Aj xj , where
Ai ∈ Rm×n and A = [A1 , . . . , AN ]. The set Ωi represents
the local decision set for agent i, while the matrix Ai defines
how agent i is involved in the coupling constraints. For
instance, the shared constraints in (3) may contain a sparsity
pattern that can be defined via a graph, where each agent has
a set of “neighbors” with whom to share some constraints.
Remark 1 (Affine coupling constraint): Affine coupling
constraints as considered in this paper are very common in
the literature of noncooperative games, see [16], [17], [22],
[23]. Moreover, we recall that the more general case with
separable convex coupling constraints can be reformulated
as game via affine coupling constraints [24, Remark 2]. 
Next, let us postulate standard convexity and compactness
assumptions for the constraint sets, convexity and differentiability assumptions for the local cost functions.
Standing Assumption 1 (Convex differentiable functions):
For each i ∈ N and y ∈ X −i the function Ji ( · , y) is
convex and continuously differentiable.

Standing Assumption 2 (Compact convex constraints):
For each i ∈ N , the set Ωi is nonempty, compact and convex.
The set X satisfies the Slater’s constraint qualification. 
In summary, the aim of each agent i, given the decision
variables of the other agents, x−i , is to choose a strategy,
xi , that solves its local optimization problem according to
the game setup previously described, i.e.,

(
min
Ji xi , x−i
xi ∈ Ωi
∀i ∈ N .
(4)
PN
s.t.
Ai xi ≤ b − j6=i Aj xj
From the game-theoretic perspective, we consider the problem to compute a Nash equilibrium, as formalized next.
Definition 1 (Generalized Nash equilibrium): The collective strategy x∗ is a generalized Nash equilibrium (GNE) of
the game in (4) if x∗ ∈ X and for all i ∈ N


Ji x∗i , x∗−i ≤ inf Ji (y, x∗−i ) | y ∈ Xi (x∗−i ) .


In other words, a set of strategies is a Nash equilibrium if
no agent can improve its objective function by unilaterally
changing its strategy to another feasible one.
Under Assumptions 1−2, the existence of a GNE of the
game in (4) follows from Brouwer’s fixed-point theorem [10,
Proposition 12.7], while uniqueness does not hold in general.
B. Variational equilibria and pseudo-gradient of the game

Within all the possible Nash equilibria, we focus on
an important subclass of equilibria, with some relevant
structural properties, such as “larger social stability” and
“economic fairness” [9, Theorem 4.8], that corresponds to
the solution set of an appropriate variational inequality. Let
us first formalize the notion of variational inequality problem.
Definition 2 (Generalized variational inequality):
Consider a closed convex set S ⊆ Rn , a set-valued mapping
Ψ : S ⇒ Rn , and a single-valued mapping ψ : S → Rn .

The generalized variational inequality problem GVI(S, Ψ),
is the problem to find x∗ ∈ S and g ∗ ∈ Ψ(x∗ ) such that
(x − x∗ )⊤ g ∗ ≥ 0 for all x ∈ S.
If Ψ(x) = {ψ(x)} for all x ∈ S, then GVI(S, Ψ) reduces to
the variational inequality problem VI(S, ψ).
A fundamental mapping in a noncooperative game is the
so-called pseudo-gradient, F : X ⇒ RnN , defined as

F (x) := col {∂xi Ji (xi , x−i )}i∈N .
(5)

Namely, the mapping F is obtained by stacking together
the subdifferentials of the agents’ objective functions with
respect to their local decision variables.
Under Assumptions 1−2, it follows by [10, Proposition
12.4] that any solution of GVI(X , F ) is a Nash equilibrium
of the game in (4). The inverse implication is not true in
general, and actually in passing from the Nash equilibrium
problem to the GVI problem most solutions are lost [10,
§12.2.2]; indeed, a game may have a Nash equilibrium while
the corresponding GVI has no solution. Note that, since the
cost functions are differentiable (by Assumption 2), then
GVI(X , F ) reduces to VI(X , F ), which is commonly addressed in the context of game theory via projected gradient
algorithms [14], [16], [19], [20, §12].
Under the postulated standing assumptions, it is shown
in [10, Proposition 12.11] that a sufficient condition for the
existence (and uniqueness) of a variational GNE of the game
in (4) is the (strict) monotonicity of the pseudo-gradient F
in (5). Thus, let us assume strongly monotonicity of F .
Standing Assumption 3 (Strong monotonicity): The
pseudo-gradient F in (5) is η-strongly monotone and
ℓF -Lipschitz continuous, for some constants η, ℓF > 0. 
III. G ENERALIZED NASH

EQUILIBRIUM AS ZERO OF THE

SUM OF TWO MONOTONE OPERATORS

In this section, we exploit operator theory to recast the
Nash equilibrium seeking problem into a monotone inclusion, namely, the problem of finding a zero of a set-valued
monotone operator. As first step, we characterize a GNE
of the game in terms of KKT conditions of the coupled
optimization problems in (4). For each agent i ∈ N , let
us introduce the Lagrangian function Li , defined as
Li (x, λi ) := Ji (xi , x−i ) + ιΩi (xi ) + λ⊤
i (Ax − b),
where λi ∈ Rm
≥0 is the Lagrangian multiplier associated with
the coupling constraints. It follows from [10, §12.2.3] that
the set of strategies x∗ is a GNE of the game in (4) if and
only if the following coupled KKT conditions are satisfied:
(
0 ∈ ∂xi Ji (x∗i , x∗−i ) + NΩi (x∗i ) + A⊤
i λi
∀i ∈ N (6)
∗
0 ≤ λi ⊥ −(Ax − b) ≥ 0
The constraint qualification in Assumption 2 is needed at
this stage to ensures boundedness of the dual variables λi ’s.
In a similar fashion, we characterize a variational GNE in
term of KKT conditions by exploiting the Lagrangian duality
scheme for the corresponding VI problem, see [25, §3.2].

Specifically, x∗ is a solution of VI(X , F ) if and only if
x∗ ∈ argminy∈X (y − x∗ )⊤ F (x∗ ). Then, the associated
KKT optimality conditions read as
(
0 ∈ ∂xi Ji (x∗i , x∗−i ) + NΩi (x∗i ) + A⊤
i µ, ∀i ∈ N
(7)
0 ≤ µ ⊥ −(Ax∗ − b) ≥ 0.
To cast (7) in compact form, we introduce the set-valued
nN
mapping T : X × Rm
× Rm , defined as
≥0 ⇒ R
 


NΩ (x) + F (x) + A⊤ µ
x
T :
,
(8)
7→
(µ) − (Ax − b)
NRm
µ
≥0
Essentially, the role of the mapping T is that its zeros
correspond to the variational generalized Nash equilibria of
the game in (4), as formalized in the next statement.
Proposition 1 ([18, Th. 1]): The collective strategy x∗ is
a variational GNE of the game in (4) if and only if there ex∗
∗
ists µ∗ ∈ Rm
≥0 such that col(x , µ ) ∈ zer (T ). Moreover, if
∗
∗
∗
col(x , µ ) ∈ zer (T ), then x satisfies the KKT conditions
in (6) with Lagrangian multipliers λi = µ∗ for all i ∈ N . 
To conclude this section, we note that the mapping T can
be written as the sum of two operators, defined as
 


x
F (x)
A:
7→
,
(9)
λ
b
 
 




NΩ (x)
x
0
A⊤ x
B:
+
7→
.
(10)
(µ)
NRm
λ
−A 0
λ
≥0
The formulation T = A + B is called splitting of T , and
will be exploited in different ways later on. We show next
that the mappings A and B are both monotone, which paves
the way for splitting algorithms.
Lemma 1: The mapping B in (10) is maximally monotone
and A in (9) is (η/ℓ2F )-cocoercive.

Proof: First, consider B = B1 + B2 in (10). The
first term B1 is maximally monotone, since normal cones
of closed convex sets are maximally monotone and the
concatenation preserves maximality [21, Prop. 20.23]; the
second term B2 is linear and skew symmetric, i.e., B2⊤ =
−B2 , thus maximally monotone [21, Ex. 20.30]. Then, the
maximal monotonicity of B follows from [21, Cor. 24.4],
since domB2 = RnN +m . To prove that A is (η/ℓ2F )cocoercive, we note that for all ω 1 = col(x1 , λ2 ), ω2 =
col(x2 , λ2 ) ∈ RnN +m , it holds that
hA(ω 1 ) − A(ω), ω 1 − ω2 i = hF (x1 ) − F (x2 ), x1 − x2 i
≥ η kx1 − x2 k2 ≥

η
ℓ2F

kF (x1 ) − F (x2 )k2
=

η
ℓ2F

2

kA(ω 1 ) − A(ω 2 )k .

The first and second inequalities follow from the η-strong
monotonicity and ℓF -Lipschitz continuity, respectively, of the
mapping F , postulated in Assumption 3.
IV. P RECONDITIONED F ORWARD -BACKWARD

SPLITTING

In light of Lemma 1, the forward-backward (FB) splitting
[21, §25.3] guarantees convergence to a zero of A + B.
In this section, we discuss a design procedure for FB
algorithms, which is particularly useful when the resolvent

of the operator B cannot be computed explicitly. Moreover,
we show that two existing algorithms for GNE seeking in
aggregative games belong to this class of algorithms.

Lemma 3: The matrix Φs in (15) is positive definite if
2

γ < (kAk αi,max )−1 ,

γ, αi,min > 0,

(16)

A. Preconditioned Forward-Backward: Design Procedure

where αi,max := maxi∈N αi and αi,min := mini∈N αi .

The main idea of the FB splitting is that the zeros of the
mapping T in (8) correspond to the fixed points of a certain
operator which depends on the chosen splitting (10)−(9), as
formalized next.
Lemma 2: For any matrix Φ ≻ 0, the following equivalence holds:

Proof: The conditions in (16) directly follow by applying the the Schur’s complement on Φs in (15).

ω ∈ zer(A + B) ⇔ ω ∈ fix (VΦ ◦ UΦ ),

Now, we present the preconditioned Forward-Backward
(pFB) algorithm associated with Φs , which is the Banach–
Picard iteration in (12) for Φ = Φs .
Algorithm 1: Preconditioned Forward Backward (pFB)

(11)

where UΦ := (Id − Φ−1 A) and VΦ := (Id + Φ−1 B)−1 . 
Proof: Consider a vector ω ∈ RnN +m , then
0 ∈ (A + B)(ω) ⇔ 0 ∈ Φ−1 (A + B)(ω)



xk+1 = projΩ xk − α(F (xk ) + A⊤ λk ]
 k

λ + γ(2Axk+1 − Axk − b)
λk+1 = projRm
≥0

⇔ ω = VΦ ◦ UΦ (ω),

Remark 2: The iterations of Algorithm 1 are sequential
(guideline 4), namely, the multiplier update, λk+1 , exploits
the most recent value of the agents’ strategies, xk+1 .


where the first equivalence holds since Φ−1 ≻ 0.
The FB algorithm is the Banach–Picard iteration [21,
(1.67)] applied to the mappings VΦ ◦ UΦ in (11), i.e.,

In the next statement, we show the convergence of Algorithm 1 to a variational generalized Nash equilibrium, under
suitable choices of the step sizes.

⇔ (Id − Φ−1 A)(ω) ∈ (Id + Φ−1 B)(ω)

ω k+1 = (Id + Φ−1 B)−1 ◦ (Id − Φ−1 A)(ω k ).

(12)

In numerical analysis, UΦ represents a forward step with size
and direction defined by Φ, while VΦ represents a backward
step. Directly from the iteration in (12), we have that
(Id − Φ−1 A)(ω k ) ∈ (Id + Φ−1 B)(ωk+1 ) ⇔
k

−A(ω ) ∈ B(ω

k+1

) + Φ(ω

k+1

Proof: See Section V.
k

− ω ).

(13)

The choice of the preconditioning matrix Φ in (13) plays
a key role in the algorithm design. Next, we provide some
general guidelines to design Φ.
Design guidelines for the preconditioning matrix Φ:
1.
2.
3.
4.

Theorem 1 (Global convergence of pFB): The sequence
∞
col(xk , λk ) k=0 defined by Algorithm 1, with step sizes
αi ∈ (0, 2η/ℓ2F ), for all i ∈ N , and γ ∈ (0, γmax ), with
1
1
1
γmax := kAk
− 2η/ℓ
2 ), globally converges to some
2 (α
i,max
F
∗
∗
col(x , λ ) ∈ zer(T ), with T as in (8).


∀ξ ∈ eig(Φ), ℜ [ξ] > 0 (necessary);
ω k+1 in (13) explicitly computable (necessary);
Φ = Φ⊤ (convenient convergence analysis);
iterations in (12) sequential (convenient implementation).

Without loss of generality, we denote ω = col(x, λ), then
the inclusion in (13) reads in expanded form as

 
 


NΩ (xk+1 )
F (xk )
0
A⊤ xk+1
−
+
∈
(λk+1 )
NRm
b
−A 0
λk+1
≥0
  k+1


− xk
Φ11 Φ12 x
. (14)
+
Φ21 Φ22 λk+1 − λk
Consider a symmetric matrix Φs , designed accordingly to
the guidelines above, i.e.,

 −1
α
−A⊤
,
(15)
Φs : =
−A γ −1 Im
where α := diag(α1 , · · · , αN )⊗In and the coefficients (step
sizes) {αi }N
i=1 and γ are chosen such that Φs has positive
eigenvalues (guideline 1), as formalized in the next lemma.

B. The Asymmetric Projection Algorithm in [16, Alg. 1] is
a preconditioned Forward-Backward splitting
We note that Algorithm 1 (with equal step sizes) corresponds to the “asymmetric” projected algorithm (APA)
proposed in [16, Alg. 1]. Therein, the algorithm design
and its convergence analysis rely on a variational inequality
formulation of the Nash equilibrium problem. Specifically,
the authors define the convex set C := Ω × Rm
≥0 and the
monotone mapping
 

 
 
x
F (x)
0
A⊤ x
R:
7→
+
,
λ
b
λ
−A 0
and characterize the GNE as solutions of VI(C, R). Then, to
solve VI(C, R) in a semi-decentralized fashion, the authors
propose an asymmetric implementation of the projection
algorithm for variational inequalities [20, 12.5.1], in which
each iteration is computed as
ωk+1 = solution to VI(C, RkD ),
where RkD (ω) := R(ω k ) + D(ω − ω k ) and
 −1

τ I
0
D :=
.
−2A τ −1I

(17)

(18)

If the parameter τ > 0 in (18) is chosen such that
D ≻ 0, then the unique solution in (17) is projC,D ω k −


D−1 R(ω k ) , where projC,D is the projection operator characterized by the asymmetric matrix D in (18). Thus, the
iteration in (17) equivalently reads as
ω k+1 = (Id + D−1 NC )−1 ◦ (Id − D−1 R)(ω k ),

(19)

which is nothing but a pFB associated with the splitting T :=
NC + R and the preconditioning matrix Φ = D.
Remark 3: With (19), we showed that pFB algorithms
based on different splittings and preconditioning matrices
can lead to the same algorithm. From an operator-theoretic
perspective, the convergence analysis is more convenient for
the pFB with symmetric matrix Φs = 12 (D + D⊤ ) (guideline
3), since the properties that A, B have with the standard
−1
inner product h·, ·iI are preserved for Φ−1
s A, Φs B with
inner product h·, ·iΦs = hΦ·, ·i, as shown in Section V. 
C. The distributed algorithm for aggregative games on
graphs in [14, §3] is a preconditioned Forward-Backward
In this section, we show that the synchronous distributed
algorithm for NE seeking in network aggregative games
proposed in [14, §3] can be written as a pFB splitting.
In [14], the authors consider an aggregative game without
coupling constraints, i.e., Xi (·) = Ωi for all i ∈ N , and
wherein the agents have no access to the aggregate decision
(1), but build an estimate of it by communicating over an
undirected network with their neighboring agents.
Specifically, let E be the set of underlying undirected
edges between agents; let Ni := {j ∈ N | (i, j) ∈ E }
denote the set of neighbors of agent i, with the convention
that i 6∈ Ni ; let D := diag(d1 , · · · , dN ) be the degree matrix,
where di := |Ni |; let E be the adjacency matrix, such that
[E]ij := 1 if j ∈ Ni , 0 otherwise. let L := D − E be
the Laplacian matrix and let us define the matrix W :=
JD (I + E), with JD = (I + D)−1 , such that, given a vector
v = col(v1 , · · · , vN ), with vi ∈ Rn , then
[(W ⊗ In )v]i =

1
|Ni |+1

P

j∈Ni ∪{i} vj ,

for all i ∈ N .

Let Fσ : X × RnN ⇒ RnN be the extension of F in (5) to
the augmented space of actions and estimates, defined as

Fσ (x, z) := col {∂xi fi (xi , zi )}i∈N
(20)

Note that Fσ (x, 1N ⊗ (M x)) = F (x). Next, we present a
static version of the algorithm in [14, §3], whose convergence
to a NE is established in [14, Prop. 2].
Algorithm 2: Koshal–Nedić–Shanbhag algorithm


xk+1 = projX xk − αFσ x, (W ⊗ In )v k


v k+1 = projRnN (W ⊗ In )v k + xk+1 − xk

In the following statement, we show that Algorithm 2 is
a pFB splitting with symmetric preconditioning matrix.

Proposition 2: Let the mappings A, B and the preconditioning matrix Φ be defined as
 

 


x
−P x
Fσ (x, σ)
1 0
A:
→
,
(21)
+2
σ
P
0
σ
0

 
 


0
P x
x
NΩ (x)
,
(22)
B:
→
+ 12
−P 0 σ
σ
Ln σ

 −1
α I − 12 P
,
(23)
Φ :=
− 21 P
P
where Ln := L ⊗ In and P := (I + E ⊗ In ). Then, the
∞
sequence col(xk , σ k ) k=0 generated by the pFB in (12),
with A, B, Φ as in (21)−(23),
corresponds to the sequence
∞
col(xk , (W ⊗ In )v k ) k=0 generated by Algorithm 2. 
Proof: The iteration in Alg. 2 can be derived by solving
the inclusion (13) with A, B, Φ as in (21)−(23), for xk+1
and σ k+1 and noticing that σ k = (W ⊗ In )v k .
V. C ONVERGENCE A NALYSIS
First, we show that the properties the mappings A, B have
with the standard inner product are preserved for Φ−1
s A,
=
hΦ·,
·i.
Φ−1
B
with
the
inner
product
h·,
·i
Φ
s
s
−1
Lemma 4: The mappings Φ−1
s A, Φs B, UΦs , VΦs satisfy
the following properties in the Φs -induced norm:
1
(i) Φ−1
s A is β-cocoercive and UΦs is 2β -averaged, where
η
−1
⊤
β := λmin (α − γA A) ℓF .
1
(ii) Φ−1
s B is maximally monotone and VΦs is 2 -averaged.
Proof: (i): We need to show that for all ω 1 , ω2 ∈
Ω × Rm
≥0 the following condition holds:
−1
hΦ−1
s A(ω 1 ) − Φs A(ω 2 ), ω 1 − ω 2 iΦs
−1
≥ β Φ−1
s A(ω 1 ) − Φs A(ω 2 )

2
Φs

. (24)

We first provide an upper bound for the right hand side of
(24). Let us denote ω i = col(xi , µi ) for i = 1, 2, then
−1
Φ−1
s A(ω 1 ) − Φs A(ω 2 )

2
Φs



= h Φs Φs−1 (A ω 1 ) − A(ω 2 ) , Φ−1
s (A ω 1 ) − A(ω 2 ) i =
⊤ 



F (x1 ) − F (x2 )

0

[Φ−1 ]11
 s
[Φ−1
s ]21

[Φ−1
s ]12 F (x1 ) − F (x2 )
0
[Φ−1
s ]22




= kF (x1 ) − F (x2 )k[Φ−1
s ]11
2

≤ [Φ−1
s ]11

2

kF (x1 ) − F (x2 )k

= [Φs−1 ]11

2

kA(ω 1 ) − A(ω 2 )k2 ,

(25)

−1
where [Φ−1
− γA⊤ A)−1 is symmetric and poss ]11 := (α
itive definite if the step sizes αi , γ are chosen as in Lemma
−1 −1
3. Moreover, it holds that [Φ−1
s ]11 2 = 1/λmin ([Φs ]11 ),
−1
−1 −1
where λmin ([Φs ]11 ) is the smallest eigenvalue of [Φ−1
s ]11 .
η
Now, we exploit the ℓ2 -cocoercivity of A and the upper
F
bound in (25) to define the cocoercivity constant β in (24).
−1
hΦ−1
s A(ω 1 ) − Φs A(ω 2 ), ω 1 − ω 2 iΦs
η
2
= hA(ω 1 ) − A(ω 2 ), ω 1 − ω2 i ≥ 2 kA(ω 1 ) − A(ω 2 )k
ℓF
η
2
−1
−1
−1
≥ 2 λmin ([Φ−1
s ]11 ) Φs A(ω 1 ) − Φs A(ω 2 ) Φs .
ℓF

Thus, the mapping Φ−1
s A is cocoercive with constant β :=
η
−1 −1
λ
([Φ
]
)
w.r.t.
the Φs -induced norm. Since Φ−1
2
min
s
s A
11
ℓF
is β-cocoercive, it follows from [21, Prop. 4.33] that UΦs =
1
(Id − Φ−1
s A) is 2β -averaged. (ii): Since B is maximally
monotone by Lemma (1) and Φ−1
is positive definite, if
s
the step sizes are chosen as in Lemma 3, then the maximal
monotonicity of Φ−1
s B follows from [26, Lemma 3.7].
Next, we show that the FB operator VΦs ◦ UΦs is averaged
if the step sizes are chosen small enough.
Lemma 5: The FB operator VΦs ◦ UΦs in (11), with Φ =
1
Φs , is θ-averaged, with θ := 2−1/(2β)
∈ (0, 1), if


1
1
1
γ < kAk
αi,max < 2η
.
(26)
2
αi,max − 2η/ℓ2 ,
ℓ2
F

F

Moreover, if αi = γ for all i ∈ N , then (26) reads as
γ<

−1+

q
2
1+kAk2 (4η/ℓ2F )
kAk2 (4η/ℓ2F )

.

(27)

Proof: By Lemma 4, UΦs and VΦs are averaged with
1
constants τ1 := 2β
and τ2 := 21 , respectively. If τ1 ∈ (0, 1),
2β
2 −2τ1 τ2
then VΦs ◦UΦs is θ-averaged with θ = τ1 +τ
∈
= 4β−1
1−τ1 τ2
(0, 1), by [27, proposition 2.4]. To conclude, we note that the
following condition implies that τ1 < 1:
β=

η
λ [(α−1
ℓ2F min

− γA⊤ A)−1 ]
≥

η
( 1
ℓ2F αi,max

2

− γ kAk ) > 21 , (28)

where the second inequality in (28) holds for step sizes
chosen as in (26). Moreover, if the step sizes are equal, i.e.,
αi = γ for all i ∈ N , then (28) holds for γ as in (27).
We can now prove the convergence of Algorithm 1.
Proof of Theorem 1: The iterations in Alg. 1 are obtained
explicitly by substituting Φs into (14) and solving for xk+1 ,
λk+1 . Thus, Alg. 1 is the Banach–Picard iteration of the
mapping VΦs ◦ UΦs , which is θ-averaged, with θ ∈ (0, 1),
by Lemma 5, if the step sizes satisfy (26). The convergence
∞
of the sequence col(xk , λk ) k=0 generated by the Banach–
Picard iteration of VΦs ◦ UΦs to col(x̄, λ̄) ∈ fix(VΦs ◦ UΦs ) =
zer(A + B) 6= ∅ follows by [21, Prop. 15.5].

Remark 4: The upper bounds in Lemma 5 are increasing
functions of the cocoercivity constant η/ℓ2F of F in (5). In
particular, the upper bound for the case with equal step sizes
in (27) is tighter than that obtained in [16, Theorem 2]. 
VI. C ONCLUSION
By monotone operator theory, projected-gradient methods
for generalized Nash equilibrium seeking in aggregative
games are preconditioned forward-backward splitting methods, whose convergence has been established for problems
with strongly monotone pseudo-gradient mapping.
R EFERENCES
[1] N. S. Kukushkin, “Best response dynamics in finite games with
additive aggregation,” Games and Economic Behavior, vol. 48, no. 1,
pp. 94–10, 2004.
[2] W. Saad, Z. Han, H. Poor, and T. Başar, “Game theoretic methods for
the smart grid,” IEEE Signal Processing Magazine, pp. 86–105, 2012.

[3] F. Parise, M. Colombino, S. Grammatico, and J. Lygeros, “Mean field
constrained charging policy for large populations of plug-in electric
vehicles,” in Proc. of the IEEE Conference on Decision and Control,
Los Angeles, California, USA, 2014, pp. 5101–5106.
[4] Z. Ma, S. Zou, L. Ran, X. Shi, and I. Hiskens, “Efficient decentralized
coordination of large-scale plug-in electric vehicle charging,” Automatica, vol. 69, pp. 35–47, 2016.
[5] S. Grammatico, B. Gentile, F. Parise, and J. Lygeros, “A mean field
control approach for demand side management of large populations
of thermostatically controlled loads,” in Proc. of the IEEE European
Control Conference, Linz, Austria, 2015.
[6] S. Li, W. Zhang, J. Lian, and K. Kalsi, “Market-based coordination
of thermostatically controlled loads - Part I: A mechanism design
formulation,” IEEE Trans. on Power Systems, vol. 31, no. 2, pp. 1170–
1178, 2016.
[7] N. Li, L. Chen, and M. A. Dahleh, “Demand response using linear
supply function bidding,” IEEE Transactions on Smart Grid, vol. 6,
no. 4, pp. 1827–1838, 2015.
[8] J. Barrera and A. Garcia, “Dynamic incentives for congestion control,”
IEEE Trans. on Automatic Control, vol. 60, no. 2, pp. 299–310, 2015.
[9] F. Facchinei and C. Kanzow, “Generalized nash equilibrium problems,”
Annals of Operations Research, vol. 175, no. 1, pp. 177–211, 2010.
[10] D. P. Palomar and Y. C. Eldar, Convex optimization in signal processing and communications. Cambridge university press, 2010.
[11] L. Pavel, “An extension of duality to a game-theoretic framework,”
Automatica, vol. 43, pp. 226–237, 2007.
[12] A. A. Kulkarni and U. Shanbhag, “On the variational equilibrium as a
refinement of the generalized Nash equilibrium,” Automatica, vol. 48,
pp. 45–55, 2012.
[13] F. Salehisadaghiani and L. Pavel, “Distributed Nash equilibrium seeking: A gossip-based algorithm,” Automatica, vol. 72, pp. 209–216,
2016.
[14] J. Koshal, A. Nedić, and U. Shanbhag, “Distributed algorithms for
aggregative games on graphs,” Operations Research, vol. 64, no. 3,
pp. 680–704, 2016.
[15] S. Grammatico, F. Parise, M. Colombino, and J. Lygeros, “Decentralized convergence to Nash equilibria in constrained deterministic mean
field control,” IEEE Trans. on Automatic Control, vol. 61, no. 11, pp.
3315–3329, 2016.
[16] D. Paccagnan, B. Gentile, F. Parise, M. Kamgarpour, and J. Lygeros,
“Distributed computation of generalized Nash equilibria in quadratic
aggregative games with affine coupling constraints,” in Proc. of the
IEEE Conf. on Decision and Control, Las Vegas, USA, 2016.
[17] S. Grammatico, “Dynamic control of agents playing aggregative games
with coupling constraints,” IEEE Trans. on Automatic Control, vol. 62,
no. 9, pp. 4537 – 4548, 2017.
[18] G. Belgioioso and S. Grammatico, “Semi-decentralized Nash equilibrium seeking in aggregative games with coupling constraints and nondifferentiable cost functions,” IEEE Control Systems Letters, vol. 1,
no. 2, pp. 400–405, 2017.
[19] ——, “On convexity and monotonicity in generalized aggregative
games,” IFAC-PapersOnLine, vol. 50, no. 1, pp. 14 338–14 343, 2017.
[20] F. Facchinei and J. Pang, Finite-dimensional variational inequalities
and complementarity problems. Springer Verlag, 2003.
[21] H. H. Bauschke and P. L. Combettes, Convex analysis and monotone
operator theory in Hilbert spaces. Springer, 2011.
[22] P. Yi and L. Pavel, “A distributed primal-dual algorithm for computation of generalized nash equilibria via operator splitting methods,” in
56th IEEE Annual Conference on Decision and Control, CDC 2017,
Melbourne, Australia, December 12-15, 2017, 2017, pp. 3841–3846.
[23] S. Liang, P. Yi, and Y. Hong, “Distributed nash equilibrium seeking
for aggregative games with coupled constraints,” Automatica, vol. 85,
pp. 179–185, 2017.
[24] S. Grammatico, “Proximal dynamics in multi-agent network games,”
IEEE Transactions on Control of Network Systems, 2017.
[25] A. Auslender and M. Teboulle, “Lagrangian duality and related
multiplier methods for variational inequality problems,” SIAM Journal
on Optimization, vol. 10, no. 4, pp. 1097–1115, 2000.
[26] P. L. Combettes and B. C. Vũ, “Variable metric forward–backward
splitting with applications to monotone inclusions in duality,” Optimization, vol. 63, no. 9, pp. 1289–1318, 2014.
[27] P. L. Combettes and I. Yamada, “Compositions and convex combinations of averaged nonexpansive operators,” Journal of Mathematical
Analysis and Applications, pp. 55–70, 2015.

