1

A distributed algorithm for average aggregative games
with coupling constraints

arXiv:1706.04634v2 [] 17 Oct 2017

Francesca Parise, Basilio Gentile and John Lygeros

Abstract—We consider the framework of average aggregative
games, where the cost function of each agent depends on his
own strategy and on the average population strategy. We focus
on the case in which the agents are coupled not only via their
cost functions, but also via constraints coupling their strategies.
We propose a distributed algorithm that achieves an almostNash equilibrium by requiring only local communications of the
agents, as specified by a sparse communication network. The
proof of convergence of the algorithm relies on the auxiliary
class of network aggregative games and exploits a novel result
of parametric convergence of variational inequalities, which is
applicable beyond the context of games. We apply our theoretical
findings to a multi-market Cournot game with transportation
costs and maximum market capacity.

I. I NTRODUCTION
VERAGE aggregative games are used to describe populations of non-cooperative agents where each agent is not
subject to one-to-one interactions with the others, but is rather
influenced by the average strategy of the entire population.
These games are gaining more and more attention in the
control community for their ability to model a vast number of
technological applications ranging from traffic [1] and wireless
systems [2] to electricity [3] and commodity markets [4].
Applying game theoretical concepts to engineering systems
becomes challenging in presence of a large number of agents
with private cost functions and constraints, willing to exchange
information only with a (small) subset of the population.
Moreover, often the agents’ strategies must collectively satisfy
some physical coupling constraints, as in electricity markets [5], where the overall energy demand should not exceed
the grid capacity, or in communication networks [6], where
the package traffic should not exceed the congestion level.

A

Main contributions
To overcome the difficulties described above, in this paper
we present a distributed algorithm that guarantees convergence to an almost Nash equilibrium of a population average
aggregative game with affine coupling constraints by using
only local communications over a sparse network. Our method
works for populations of heterogeneous agents with generic
local convex constraints and generic convex cost functions
(i.e. we do not need to assume that the cost functions are
quadratic, as in [7]). To prove algorithmic convergence we rely
The first two authors contributed equally. F. Parise is with the Laboratory for Information and Decision Systems, MIT, Cambridge, MA, USA.
Email: parisef@mit.edu. B. Gentile and J. Lygeros are with the Automatic Control Laboratory, ETH Zurich, Switzerland. Email: {gentileb,
lygeros}@control.ee.ethz.ch. Research partially supported by the
European Commission under project DYMASOS (FP7-ICT 611281) and by
the Swiss National Science Foundation (grant P2EZP2 168812).

on two key steps: i) we show that the Nash equilibrium of the
average aggregative game of interest can be approximated to
any desired precision by the Nash equilibrium of an auxiliary
network aggregative game (as defined in [8]); ii) we propose a
distributed algorithm to compute the Nash equilibrium of the
auxiliary game.
As a side contribution, to tackle i) we prove a result
on convergence of parametric variational inequalities (VIs)
which is applicable beyond the context of games. A detailed
explanation of how our result improves the existing literature
on convergence of parametric VIs is given in Appendix B.
Moreover, to tackle ii), we derive a distributed algorithm to
find a Nash equilibrium of any network aggregative game.
Both these results can find application beyond the specific
context of this paper and are thus of interest on their own.
To illustrate our theoretical findings, we study in detail a
Cournot game with transportation costs, as introduced in [9,
Section 1.4.3]. We note that such setup extends the Cournot
game [10, Section 2] and the multi-market Cournot game [11,
Section 7.1] by introducing transportation costs. Our novel
contributions consist in introducing coupling constraints, performing a specific study of the properties of a fundamental
operator associated with the game, and focusing on distributed
convergence.
Comparison with the literature
The problem of coordinating the agents to a Nash equilibrium is of great importance for control purposes and it
has consequently been addressed by many authors in the last
few years. In the following we review such rapidly growing
literature by distinguishing whether the proposed algorithms 1)
can only be applied when the agent strategy sets are decoupled
or allow for constraints coupling the agents’ strategies and
2) require a central coordinator (decentralized algorithms) or
employ only local communications (distributed algorithms).
We note that in some applications distributed algorithms
are preferable to decentralized ones, for reasons of privacy,
security or for the lack of a central operator.
A vast literature focused on the case of decoupled strategy
sets, where the feasible strategy set of each agent is not
affected by the strategies of the other agents. Decentralized
algorithms relying on the presence of a central operator that
can gather and broadcast information to the agents are suggested in [7], [12]. On the other hand, distributed algorithms
relying only on local communications among the agents are
suggested in [13], [14], [15], [16].
All the previously mentioned algorithms cannot be applied
to the case of coupling constraints, because they build on the
core assumption that the strategy sets are decoupled. Consequently, including coupling constraints requires a fundamental

2

rethinking of the algorithms suggested in the literature, as we
highlight in detail in Section IV-C. A decentralized algorithm
overcoming this issue for average aggregative games has
been recently suggested in [17], [18], by exploiting a primaldual reformulation of the Nash equilibrium problem originally
introduced for generic games in [19] and [20, Theorem 3.1].
To the best of our knowledge, the only distributed algorithm
available in the literature for average aggregative games with
coupling constraints is [21]. However such algorithm is only
applicable if the coupling constraints can be expressed as the
solution set of a system of linear equations [21, eq. (5)]. This
is a very restrictive assumption that prevents the applicability
of the algorithm suggested in [21] to any of the practical cases
discussed before.
We finally note that our work has some affinity with the
distributed algorithms suggested in [11], [22], [23] to compute
a Nash equilibrium of generic games (i.e., games that do not
have the aggregative structure considered here) with coupling
constraints. The term “distributed” in all these references,
however, refers to the fact that any specific agent is only
allowed to communicate with the agents that affect his cost
function. In average aggregative games the cost function of
each agent is affected by the strategy of all the other agents,
because it is affected by the average population strategy.
Consequently, the schemes proposed in [22], [23], [11] can
theoretically be applied to average aggregative games, but they
would require communications among all the agents.
The average aggregative game (AAG) considered in this
paper also relates to the class of mean field games (MFGs),
since both in AAGs and in MFGs the agents are influenced
only by an aggregate of the population strategies [24], [25],
[26], [27], [28]. There are however some fundamental differences that make results derived for MFGs not applicable
in our context. Firstly, in MFGs the strategies of the agents
are unconstrained: the coupling constraints that we consider
here cannot be handled with the mean field approach based
on partial differential equations. Secondly, MFG results are
derived for the limit of infinite population size: we here
instead consider populations of any size. Thirdly, in MFGs
agents are typically homogeneous or have prior (probabilistic)
information of the parameters of the other agents: we instead
assume that the agents have no information on the rest of the
population and rely on local communications over a network.
Finally, MFGs are stochastic dynamic games while AAGs are
deterministic static games.
Organization: In Section II we formulate the game setup,
we present our main algorithm and we state our main result.
In Section III we present some preliminary results, needed to
prove our main theorem. The main result, stated in Section II,
is proven in Sections IV-A and IV-B. Specifically, in Section IV-A we study the relation between the Nash equilibrium
of the auxiliary game (which is parametrized by ν ∈ N) and
the Nash equilibrium of the original average aggregative game,
which can be seen as the limiting game when ν → ∞. In
Section IV-B we prove convergence of our algorithm to the
Nash equilibrium of the auxiliary game. Section V focuses
on the application, while Section VI presents some some
generalizations of the previous theory, which were omitted

to keep the exposition simple, and future research directions.
Appendix B is a standalone section containing the result on
convergence of parametric VIs. Appendices A and C contain
some auxiliary definitions and results, respectively. We report
our main results as theorems, our auxiliary results as lemmas
and auxiliary results that already exist in the literature as
propositions.
Notation: ||x|| is the 2-norm of x ∈ Rn . In ∈ Rn×n is
the identity matrix, 1n ∈ Rn is the vector of unit entries,
0n ∈ Rn is the vector of zero entries, ei ∈ Rn is the ith
canonical basis vector. Given A ∈ Rn×n , A  0 ( 0) ⇔
x> Ax > 0 (≥ 0), ∀x 6= 0; kAk is the induced 2-norm of A.
diag(A) is the diagonal matrix which has the same diagonal
of A. blkdiag(A1 , . . . , AN ) is the block diagonal matrix whose
blocks are the matrices A1 , . . . , AN . Given N vectors each
>
1>
in Rn , [x1 ; . . . ; xN ] := [xi ]N
, . . . , xN ]> ∈ RN n
i=1 := [x
−i :=
(N −1)n
and x
[x1 ; . . . ; xi−1 ; xi+1 ; . . . ; xN ] ∈ R
. Given
g(x) : Rn → Rm we define ∇x g(x) ∈ Rn×m with
∂gj (x)
[∇x g(x)]i,j := ∂x
i . Given g(x) : R → R, we denote
∂g(x)
0
g (x) := ∂x . Given sets X 1 , . . . , X N ⊆ Rn , we denote
PN
PN i
1
1
i
n
i
i
i=1 X := {z ∈ R |z = N
i=1 x , for some x ∈ X },
N
1
N
1
N
the convex hull of X , . . . , X as conv(X , . . . , X ) and
X −i := X 1 × . . . X i−1 × X i+1 × . . . X N . ΠX [x] is the
projection of the vector x onto the set X . For a, b ∈ Z, a ≤ b,
Z[a, b] := [a, b] ∩ Z.

II. P ROBLEM FORMULATION AND MAIN RESULT
A. Average aggregative games
Consider a population of N ∈ N agents, where agent i ∈
Z[1, N ] chooses his decision variable xi in his individual constraint set X i ⊆ Rn , and interacts with the other agents via the
average of their strategies. The
 aim of agent i is to minimize his
cost function J i xi , σ∞ (x) = J i (z1 , z2 ) |z1 =xi ,z2 =σ∞ (x) ,
where J i (z1 , z2 ) : X i × conv(X 1 , . . . , X N ) → R and1
σ∞ (x) :=

N
1 X j
x .
N j=1

We denote by x := [x1 ; . . . ; xN ] ∈ X := X 1 × · · · × X N ⊂
RN n and we assume that, besides the individual constraints, the
agents have to satisfy a linear coupling constraint expressed on
the average strategy
x ∈ C∞ := {x ∈ RN n | Âσ∞ (x) ≤ b̂},

(1)

with Â ∈ Rm×n , b̂ ∈ Rm , for some m > 0. The coupling
constraints in (1) can model the fact that the usage level for
a certain commodity cannot exceed a fixed capacity, as in [5]
and in [17, Fig. 4]. The strong modeling flexibility of linear
coupling constraints is further discussed in [11, Remark 3.1].
1 The subscript ∞ does not refer to an infinite population, but to the fact
1 PN
j
that the agents interact through the exact average N
j=1 x , see also the
organization section.

3

The cost and constraints just introduced give rise to the
average aggregative game (AAG)

agents :
(1, . . . , N )



 cost of agent i :
J i (xi , σ∞ (x))
G∞ :=
(2)

individual constraint : X i



coupling constraint :
C∞ .
The following conditions on cost functions and constraints of
G∞ are assumed to hold throughout the rest of the paper.
Standing assumption. For each agent i, the individual constraint set X i ⊂ Rn is convex, compact and has non-empty
interior. The cost function J i (xi , σ∞ (x)) is convex in xi for
all x−i ∈ X −i and J i (z1 , z2 ) is continuously differentiable in
z1 , z2 .

Let us denote Q∞ := X ∩ C∞ , and
Qi∞ (x−i ) := {xi ∈ X i | x ∈ C∞ }
= {xi ∈ X i | Âσ∞ (x) ≤ b̂}.
The well-known concept of Nash equilibrium for games with
coupling constraints [29] can be specialized to G∞ as follows.
Definition 1 (Nash Equilibrium). A set of strategies x̄ =
[x̄1 ; . . . ; x̄N ] ∈ Q∞ is an ε-Nash equilibrium of G∞ if for
all i ∈ Z[1, N ] and all xi ∈ Qi∞ (x̄−i )


P
(3)
J i (x̄i , σ∞ (x̄)) ≤ J i xi , N1 xi + j6=i N1 x̄j + ε .
If (3) holds with ε = 0 then x̄ is a Nash equilibrium.

 i N
In words, a feasible set of strategies x̄ i=1 is a Nash
equilibrium if no agent can improve his cost by changing his
strategy, if the strategies of the other agents are fixed. A Nash
equilibrium for a game with coupling constraints is usually
called a generalized Nash equilibrium to denote the fact that
the set of feasible strategies Qi∞ for each agent i depends on
the strategies x−i of the other agents [29]; in the following we
omit the word generalized for brevity.

The definitions of primitive and doubly-stochastic can be
found in [30], where graph theoretical conditions guaranteeing
Assumption 1 are also presented. Loosely speaking, Assumption 1 ensures that if the agents communicate a sufficiently large
number of times over T , they are able to recover the average
of the strategies across the entire population.
C. Main result: A distributed algorithm for G∞
To compute an almost Nash equilibrium in a distributed
fashion, we propose the following Algorithm 1, where at
iteration k each agent i updates four variables:
- his strategy xi(k) ,
- a dual variable λi(k) relative to the coupling constraint C∞ ,
i
- a local average of his in-neighbors’ strategies σν,(k)
,
- a local average of his out-neighbors’ dual variables µiν,(k) .
To overcome the fact that the communication network is
i
sparse we assume that to compute σν,(k)
and µiν,(k) the agents
communicate not once but multiple times over the network T .
The number of communications per update is denoted by ν ∈ N
and is a tuning parameter of the algorithm. The personal strategy
(or primal variable) and the dual variable, in turn, are updated by
a gradient-like step that depends on a second tuning parameter
τ > 0. In particular, the strategy update step is similar to that
of the standard projection algorithm [9, Algorithm 12.1.1]. We
finally note that both tuning parameters ν and τ are decided a
priori and do not change during the algorithm execution.
Algorithm 1: Distributed algorithm for G∞
Initialize: Agent i with state xi(0) ∈ X i and dual variable
i
i
λi(0) ∈ Rm
≥0 . Set τ > 0, ν ∈ N, k = 0, σν,(0) = x(0) .
Iterate until convergence:
Communication: Dual
 i
 µν,(k) ← λi(k) , ∀ i

 repeat ν times
P
µiν,(k) ← j∈N i Tji µjν,(k) , ∀ i
out

Update: Primal
$ i
i
i
Fν,(k) ← ∇z1J i (xi(k) , σν,(k)
) + [T ν ]ii ∇z2 J i (xi(k) , σν,(k)
), ∀ i
>

i
xi(k+1) ← ΠX i [xi(k) −τ (Fν,(k)
+ Â µiν,(k) )], ∀ i

B. Communication limitations
Our main objective is to coordinate the agents’ strategies to
a Nash equilibrium by using a distributed algorithm that only
requires communications over a pre-specified (sparse) communication network. We model such network by its adjacency
matrix T ∈ [0, 1]N ×N , where the element Tij ∈ [0, 1] is the
weight that agent i assigns to communications received from
agent j, with Tij = 0 representing no communication. For
brevity, we refer to T as communication network, even though it
is the adjacency matrix of the communication network. Agent j
is an in-neighbor of i if Tij > 0 and an out-neighbor if Tji > 0.
We denote the sets of in- and out-neighbors of agent i as Nini
i
and Nout
, respectively.
We introduce the following assumption on the communication network T .
Assumption 1 (Communication network). The communication
matrix T is primitive and doubly stochastic.


Communication: Primal
 i
 σν,(k+1) ← xi(k+1) , ∀ i

 repeat ν times
P
j
i
σν,(k+1)
← j∈N i Tij σν,(k+1)
,∀i
in

Update: Dual
j
i
i
λi(k+1) ← ΠRm
[λi(k) − τ (b̂ − 2Âσν,(k+1)
+ Âσν,(k)
)], ∀ i
≥0
k ←k+1

The main objective of the paper is to prove convergence of
Algorithm 1 to an εν -Nash equilibrium of G∞ , where εν → 0
as ν → ∞. To this end, we make use of the following additional
assumptions.
Assumption 2 (Coupling constraints). The matrix Â and the
vector b̂ in (1) are such that the following implication holds.
{Â> ŝ = 0,

b̂> ŝ ≤ 0,

ŝ ≥ 0}

⇒

ŝ = 0.



4

It can be shown that if the coupling constraint (1) consists
of an upper and a lower bound for σ∞ (x), i.e. it is of the
form b1 ≤ σ∞ (x) ≤ b2 , with b1 < b2 , then Assumption 2 is
satisfied. We show in the application Section V another example
of coupling constraint satisfying Assumption 2.
Assumption 3 (Regularity of cost functions). The operator
F∞ : X → RN n , defined as
x 7→ F∞ (x) := [∇xi J i (xi , σ∞ (x))]N
i=1

(5)
i

is strongly monotone. Further, the cost function J (z1 , z2 ) is
twice continuously differentiable for all i ∈ Z[1, N ].


the local average σνi (x) instead of the global average σ∞ (x).
Specifically, upon defining
Cν := {x ∈ RN n | Âσνj (x) ≤ b̂, ∀j ∈ Z[1, N ]}
we formally introduce the multi-communication network aggregative game as

agents :
(1, . . . , N )



 cost of agent i :
J i (xi , σνi (x))
Gν :=

individual constraint : X i



coupling constraint :
Cν .

We recall in the following the definition of strong monotonicity.
Definition 2 (Strong monotonicity). An operator H : K ⊆
Rn → Rn is said to be strongly monotone if there exists αH >
0 such that for all x, y ∈ K
(H(x) − H(y))> (x − y) ≥ αH kx − yk2 .

The definition of Nash equilibrium for Gν is the analogous of
Definition 1 for G∞ . To analyze the relation between G∞ and
Gν we use the framework of variational inequalities introduced
next.



We note that sufficient conditions for Assumption 3 to hold
have been discussed in [18, Lemmas 3 and 4, Corollaries 1 and
2] for specific instances of average aggregative games.
Our main result is stated in the following theorem.
Theorem 1. If Assumptions 1, 2 and 3 hold, then for every
precision ε > 0, there exists a minimum number of communications νε > 0 such that, for every ν > νε and for every initial
m
∞
condition (x(0) , λ(0) ) ∈ X × RN
≥0 , the sequence (x(k) )k=1
produced by Algorithm 1 converges to an ε-Nash equilibrium
of G∞ for τ small enough.


B. Basics of variational inequalities
A fundamental fact used throughout the rest of the paper is
that a specific class of Nash equilibria of any convex game,
called variational Nash equilibria, can be obtained by solving
a variational inequality constructed from the game primitives.
Definition 3 (Variational inequality). Given a set K ⊆ Rn and
an operator H : K → Rn , the point x̄ ∈ Rn is a solution of
VI(K, H) if it satisfies
H(x̄)> (x − x̄) ≥ 0, ∀ x ∈ K.

A precise bound on τ is given in Theorem 3 in Section IV-B.
III. AUXILIARY RESULTS
In this section we present some preliminary results needed for
the proof of Theorem 1, whose main idea consists in defining an
auxiliary game Gν parametric in the number of communications
ν and showing that
1) Algorithm 1 converges to a specific Nash equilibrium of
Gν , called variational equilibrium;
2) the variational Nash equilibrium of Gν is an εν -Nash
equilibrium of G∞ , with εν → 0 as ν → ∞.
To prep the field for these two results, which are proven in
Section IV, we here define the game Gν , introduce some basic
results from the theory of variational inequalities (VI) and study
the relation between the VI operators associated with the two
games G∞ and Gν .



A discussion on how variational inequalities generalize convex
optimization programs can be found in [9, Section 1.3.1]. In
the following we report a sufficient condition for existence and
uniqueness of the solution of a variational inequality.
Proposition 1 ([9, Theorem 2.3.3.b]). Consider a closed and
convex set K and a strongly monotone operator H : K → Rn .
Then VI(K,H) admits a unique solution.

The following lemma gives a more intuitive characterization
of the strong monotonicity property.
Proposition 2 ([9, Proposition 2.3.2]). A continuously differentiable operator H : K ⊆ Rn → Rn is strongly monotone
with monotonicity constant α if and only if ∇x H(x)  αIn
for all x ∈ K.


A. Multi-communication network aggregative games

C. Variational Nash equilibria

In each iteration of Algorithm 1 the agents need to communicate ν times over T ; mathematically this is equivalent to
communicating once over a fictitious network with adjacency
matrix T ν . Based on T ν , we introduce the local averages

To draw the connection between VIs and Nash equilibria, let
us introduce the following quantities relative to Gν

σνi (x) :=

N
X

[T ν ]ij xj .

j=1

We define Gν as a game with same constraints and cost
functions as in G∞ except for the fact that each agent reacts to

Fν (x) := [∇xi J i (xi , σνi (x))]N
i=1 ,
Qν := {x ∈ X |Aν x ≤ b},
Qiν (x−i ) := {xi ∈ X i |Aν x ≤ b},
ν

(6a)
(6b)
(6c)

Aν := T ⊗ Â,

(6d)

b := 1N ⊗ b̂

(6e)

5

and recall the corresponding quantities relative to G∞
F∞ (x) := [∇xi J i (xi , σ∞ (x))]N
i=1 ,
Q∞ := {x ∈ X |A∞ x ≤ b},
Qi∞ (x−i ) := {xi ∈ X i |A∞ x ≤ b},
A∞ :=

>
1
N 1N 1N

⊗ Â.

(7a)
(7b)
(7c)
(7d)

The operator in (7a) is the same as (5) in Assumption 3 and
in (7) the coupling constraint C∞ is expressed in the redundant
form A∞ x ≤ b (consisting of N repetitions of the constraint
Âσ∞ (x) ≤ b̂) to match the structure of Aν x ≤ b in (6).
In the following we specialize a well-known result of [20,
Theorem 2.1] to the two games G∞ and Gν .
Proposition 3 (Variational Nash equilibrium [20, Theorem
2.1]). Every solution x̄∞ of VI(Q∞ ,F∞ ) is a Nash equilibrium
of G∞ , called a variational Nash equilibrium of G∞ . Moreover,
if J i (xi , σνi (x)) is convex in xi for all x−i ∈ X −i , every
solution x̄ν of VI(Qν ,Fν ) is a Nash equilibrium of Gν , called
a variational Nash equilibrium of Gν .

Due to the presence of the coupling constraints the converse
of Proposition 3 does not hold. In other words, there can be
Nash equilibria of G∞ (resp. Gν ) that cannot be obtained as
solutions of VI(Q∞ ,F∞ ) (resp. VI(Qν ,Fν )). Within the class
of Nash equilibria, variational Nash equilibria enjoy special
stability and sensitivity properties [29]. Variational equilibria
are also a subset of the normalized equilibria defined in [19],
which are in most cases the only Nash equilibria that can
be computed. Variational equilibria can be interpreted as the
most fair within the class of normalized equilibria, because the
burden of meeting the coupling constraints is divided equally
among all the agents [20, Theorem 3.1].
We conclude by stating convergence of the operator Fν to
F∞ as ν tends to infinity.
Lemma 1. Under Assumption 1,
lim T ν =

ν→∞

lim Aν = A∞ ,

ν→∞

and
lim Fν (x) = F∞ (x)

ν→∞

uniformly in x. The operators Fν are bounded on X , uniformly
in ν.

fact that limν→∞ T = N1 1N 1N > is proven
2]. Convergence of Aν to A∞ follows immeν

Proof: The
in [30, Theorem
diately from the definitions (6d), (7d) and the properties of the
Kronecker product. Note that
i

Fν (x) = [∇z1 J (x

i

, σνi (x))

N
X
k∇z1J i (xi, σνi (x))+[T ν ]ii ∇z2 J i (xi, σνi (x))k2
N
i=1
X
≤
(M 2 + M 2 + 2M 2 ) = 4N M 2 ,

kFν (x)k2 =

i=1

which proves that Fν is bounded, uniformly in ν.
IV. P ROOF OF T HEOREM 1
We divide the proof of Theorem 1 into two parts.
1) In subsection IV-A we show that x̄ν → x̄∞ as ν → ∞ and
that x̄ν is an εν -Nash equilibrium for G∞ , with εν → 0 as
ν → ∞. To this end we exploit a novel result on parametric
convergence of variational inequalities, which is derived
in Appendix B.
2) In subsection IV-B we show that Algorithm 1 converges
to x̄ν .
From these two results it follows that, for any desired ε one can
guarantee that the limit point x̄ν of Algorithm 1 is an ε-Nash
equilibrium of G∞ , by setting a number ν of communications
large enough. This proves Theorem 1.
A. Convergence of the variational Nash equilibrium of Gν to
the variational Nash equilibrium of G∞
The next lemma provides a sufficient condition for Fν to be
strongly monotone, which is then used in Theorem 2.
Lemma 2. If Assumptions 1 and 3 hold, there exists νSMON
such that Fν is strongly monotone for all ν > νSMON .

We report the proof of Lemma 2 in Appendix C.
Theorem 2. Suppose that Assumptions 1, 2 and 3 hold. Then

1
1N 1N >,
N

F∞ (x) = [∇z1 J i (xi , σ∞ (x)) +

k∇z2 J i (z1 , z2 )k < M . Note that [T ν ]ii ≤ 1 for all i ∈ Z[1, N ]
and for all ν > 0, since T and thus T ν are non-negative and
doubly stochastic. Then for all x ∈ X

1
N
ν

∇z2 J i (xi , σ∞ (x))]N
i=1 ,

+ [T ]ii ∇z2 J i (xi , σνi (x))]N
i=1 .

Uniform convergence of Fν to F∞ follows by continuity of
∇z1 J i (z1 , z2 ) and ∇z2 J i (z1 , z2 ) in z1 , z2 for all i (ensured
by the Standing Assumption), by [T ν ]ii → N1 , since T ν →
1
>
i
N 1N 1N , and by σν (x) → σ∞ (x) uniformly in x.
Finally, as k∇z1 J i (z1 , z2 )k and k∇z2 J i (z1 , z2 )k are continuous functions over the compact set X i × conv{X 1 , . . . , X N },
there exists M > 0 such that k∇z1 J i (z1 , z2 )k < M and

1) The game G∞ has a unique variational Nash equilibrium
x̄∞ and for any ν > νSMON , Gν has a unique variational
Nash equilibrium x̄ν . Moreover,
lim x̄ν = x̄∞ .

ν→∞

(8)

2) For every ε > 0, there exists a νε > νSMON such that, for
every ν > νε , the variational Nash equilibrium x̄ν of Gν
is an ε-Nash equilibrium of G∞ .

Proof: 1) Existence and uniqueness of x̄∞ and x̄ν solutions to VI(Q∞ ,F∞ ) and VI(Qν ,Fν ) respectively is guaranteed
by Proposition 1, because the operator F∞ is strongly monotone
by Assumption 3 and the operator Fν (for ν > νSMON ) is
strongly monotone by Lemma 2. By Proposition 2, strong
monotonicity of Fν implies convexity of J i (xi , σνi (x)) in xi .
Consequently, Proposition 3 guarantees that x̄∞ and x̄ν are the
unique variational Nash equilibrium of G∞ and Gν , respectively.
To show (8), we use Theorem B.1 in Appendix B, which
is a general result on convergence of parametric variational
inequalities. The theorem is based on Assumption B.1 in
Appendix B.

6

To verify such assumption note that by Lemma 1 Aν → A∞
and, for each x ∈ X , Fν (x) → F∞ (x); bν = b = b∞ for all ν.
Moreover, in our setup (27) reads as
{A>
∞ s = 0,

b> s ≤ 0,

s ≥ 0}

⇒

s = 0.

(9)

To prove (9) take s := [s1 ; . . . ; sN ] ∈P
RN n such that A>
∞ s = 0,
N
>
b s ≤ 0 and s ≥ 0 and define ŝ := j=1 sj ∈ Rn . Then


1
>
>
s = 0 ⇒ Â> ŝ = 0,
A>
⇔
∞s = 0
N 1N 1N ⊗ Â
b> s ≤ 0

⇔

>
(1>
N ⊗ b̂ )s ≤ 0

s≥0

⇒

ŝ ≥ 0.

⇒

b̂> ŝ ≤ 0,

By Assumption 2, we conclude ŝ = 0. Since s ≥ 0, it must be
s = 0 thus proving (9).
2) We divide the proof of this statement into two parts: i)
we prove that x̄ν ∈ Q∞ for any ν > 0, and ii) we prove that
condition (3) is satisfied.
i) Being x̄ν a Nash equilibrium for Gν , x̄ν ∈ Qν , hence x̄ν ∈ X
and Âσνi (x̄ν ) ≤ b̂ for all i. By summing over all i and dividing
by N , we obtain

 P
N
(10)
Â N1 i=1 σνi (x̄ν ) ≤ b̂.
However,
PN i
PN PN
ν
j
i=1 σν (x̄ν ) =
i=1
j=1 [T ]ij x̄ν


(11)
PN
PN
PN
ν
j
j
= j=1
i=1 [T ]ij x̄ν =
j=1 x̄ν = N σ∞ (x̄ν ),
where the second to last equality holds because, by Assumption 1, T is doubly stochastic and so is T ν . By substituting (11)
into (10) we obtain Âσ∞ (x̄ν ) ≤ b̂, thus x̄ν ∈ Q∞ for any ν.
ii) Since x̄ν is a Nash equilibrium for Gν , for all i ∈ Z[1, N ]
and for all xiν ∈ Qiν (x̄−i
ν ) it holds
X
X
J i (x̄iν ,
[T ν ]ij x̄jν ) ≤ J i (xiν , [T ν ]ii xiν +
[T ν ]ij x̄jν ). (12)
j

j6=i
i

For all i, J (z1 , z2 ) is continuously differentiable hence Lipschitz. Then there exists a common Lipschitz constant L
such that for all i, all z1 , z1a , z1b ∈ X i , and all z2 , z2a , z2b ∈
conv(X 1 , . . . , X N )
i

kJ (z1a , z2 )
kJ i (z1 , z2a )

−
−

i

J (z1b , z2 )k
J i (z1 , z2b )k

≤
≤

Lkz1a
Lkz2a

−
−

z1b k,
z2b k.

Let D := maxz∈conv{X 1 ,...,X N } {kzk} and δ(ν) :=
k N1 1N 1N > − T ν k∞ . Set ε1 := ε/(4LD). By Lemma 1, there
exists ν1 > 0 such that for all ν > ν1 , δ(ν) < ε1 . Moreover,
P
J i (x̄iν , σ∞ (x̄ν )) = J i (x̄iν , j N1 x̄jν )
P
P
≤ J i (x̄iν , j [T ν ]ij x̄jν ) + Lk j (1/N − [T ν ]ij )x̄jν k
P
P
≤ J i (x̄iν , j [T ν ]ij x̄jν ) + L j |1/N − [T ν ]ij |kx̄jν k
P
P
≤ J i (x̄iν , j [T ν ]ij x̄jν ) + LD maxi { j |1/N − [T ν ]ij |}
P
= J i (x̄iν , j [T ν ]ij x̄jν ) + LDδ(ν)
(12)
P
≤ J i (xiν , [T ν ]ii xiν + j6=i [T ν ]ij x̄jν ) + LDε1
P
≤ J i (xiν , N1 xiν + j6=i N1 x̄jν ) + 2LDε1 ,
(13)
for all xiν ∈ Qiν (x̄−i
),
for
all
ν
>
ν
.
The
last
inequality
in
1
ν
(13) can be proven with a chain of inequalities similar to the

previous ones in (13). Condition (13) implies that (3) holds
for all xiν ∈ Qiν (x̄−i
ν ), as we used the fact that x̄ν is a Nash
equilibrium for Gν . Since we however want to prove that x̄ν
is an ε-Nash for G∞ , we need to prove that (3) holds for all
xi ∈ Qi∞ (x̄−i
ν ).
To this end, take any such xi ∈ Qi∞ (x̄−i
ν ). Set ε2 := ε/(2L +
2L
).
Since
we
showed
in
the
first
statement
that x̄ν → x̄∞ , by
N
Lemma C.1 in Appendix C, there exists2 ν2 > νSMON such that
for all ν > ν2 and all i ∈ Z[1, N ] there exists x̃iν ∈ Qiν (x̄−i
ν )
such that kxi − x̃iν k ≤ ε2 . From (13) we know that since x̃iν ∈
Qiν (x̄−i
ν ) then
P
i i
J (x̄ν , σ∞ (x̄ν )) ≤ J i (x̃iν , N1 x̃iν + j6=i N1 x̄jν ) + 2LDε1
P
L
≤ J i (xi , N1 xi + j6=i N1 x̄jν ) + (L + N
)ε2 + 2LDε1
P
1 j
i i 1 i
≤ J (x , N x + j6=i N x̄ν ) + ε.
(14)
Since (14) holds for all i ∈ Z[1, N ] and for all xi ∈ Qi∞ (x̄−i
ν )
and given part i), we have proven that x̄ν is an ε-Nash
equilibrium for G∞ , for all ν > νε := max{ν1 , ν2 }.
B. Convergence of Algorithm 1
Theorem 3. Suppose that for the value of ν used in Algorithm 1 the operator Fν in (6a) is strongly monotone with
constant αν > 0 and Lipschitz with constant Lν > 0. Set
√
−L2ν + L4ν +4α2ν kAν k2
.
(15)
τ<
2αν kAν k2
m
Then for every initial condition (x(0) , λ(0) ) ∈ X × RN
≥0 the
∞
sequence (x(k) )k=1 produced by Algorithm 1 converges to the
unique variational Nash equilibrium of Gν .


:=
Proof: Let us define x(k) := [xi(k) ]N
i=1 , λ(k)
i
N
i
N
:= [σν,(k) ]i=1 , µν,(k) := [µν,(k) ]i=1 . Then the
communication steps are equivalent to
[λi(k) ]N
i=1 , σν,(k)

σν,(k) ← (T ν ⊗ In ) x(k) ,
µν,(k) ← (T ν ⊗ Im )> λ(k) .
Consequently, the update steps can be rewritten as
>PN
j
i
ν
+ Â
xi(k+1) ← ΠX i [xi(k) − τ (Fν,(k)
j=1 [T ]ji λ(k) )],
λi(k+1) ← ΠRm
[λi(k) − τ ·
≥0
PN
PN
· (b̂ − 2Â j=1 [T ν ]ij xj(k+1) + Â j=1 [T ν ]ij xj(k) )],
for all i ∈ Z[1, N ] or, in compact form,


x(k+1) ← ΠX [x(k) −τ Fν (x(k) ) +Aν > λ(k) ],
m [λ(k) − τ (b − 2Aν x(k+1) + Aν x(k) )].
λ(k+1) ← ΠRN
≥0

(16)

As (16) coincides with one iteration of the asymmetric
projection algorithm given in [18, Algorithm 2] applied to
VI(Qν , Fν ). Then [18, Theorem 3] shows that, by choosing
τ as in (15), which also implies τ < 1/kAν k, Algorithm 1 is
guaranteed to converge to the unique solution of VI(Qν , Fν ).
2 As Lemma C.1 requires uniqueness of x̄ , we take ν > ν
ν
2
SMON . Note
than ν2 is independent from i.

7

Remark 1. Note that Aν = T ν ⊗ Â, hence kAν k = kT ν kkÂk.
Under Assumption 1, kT ν k = 1 since T is doubly stochastic.
Hence in this case, one can use kÂk instead of kAν k in (15).
Moreover, Lemma 2 guarantees that strong monotonicity of
Fν assumed in Theorem 3 is met for ν > νSMON .

C. Relation of Theorems 2 and 3 with the literature on
distributed convergence in AAG without coupling constraints
As anticipated in the introduction, distributed algorithms for
AAGs without coupling constraints have already been derived
in the literature, for example in [13], [14], [15], [16]. We
highlight here how the proofs of Theorems 2 and 3 and the
steps of Algorithm 1 greatly simplify in the absence of coupling
constraints (i.e. when C∞ = RN n ).
Regarding the first statement of Theorem 2, in the absence
of coupling constraints the VIs of Gν and G∞ feature the same
set X , which is not affected by the parameter ν. Convergence
of x̄ν to x̄∞ can thus be proven by using standard sensitivity
analysis results for VI, as explained in details at the beginning
of Appendix B. In this case one can even prove Lipschitz
continuity of the solution, so it is possible to derive bounds on
the minimum number of communications ν needed to achieve
any desired precision in (8).
Regarding the second statement of Theorem 2, in the absence
of coupling constraints the fact that x̄ν is an ε-Nash equilibrium
of G∞ is a trivial consequence of (8) and of the fact that the
cost functions are Lipschitz. The difficulty when introducing
the coupling constraints are that i) the feasibility of x̄ν in
Gν does not imply automatically feasibility of x̄ν in G∞ and
ii) in the definition of Nash equilibrium, the set of feasible
deviations Qiν (x̄−i
ν ) in Gν is different from the set of feasible
deviations Qi∞ (x̄−i
ν ) in G∞ (without coupling constraints both
these sets would instead be simply X i ). This is why to prove the
second statement of Theorem 2 one needs to show Hausdorff
−i
i
convergence of Qiν (x̄−i
ν ) to Q∞ (x̄ν ) as ν → ∞, as done in
Lemma B.1 in the Appendix.
Regarding Algorithm 1 and Theorem 3, in the absence of
coupling constraints one needs to solve the VI(X , Fν ) in a
distributed fashion. Since the constraint set X can be decoupled
among the agents, the standard projection algorithm [9, Algorithm 12.1.1] is distributed and it is guaranteed to converge,
because Fν is strongly monotone. In other words, one can run
Algorithm 1 performing only the primal steps, with simplified
i
strategy update xi(k+1) ← ΠX i [xi(k) −τ Fν,(k)
].
V. A PPLICATION : C OURNOT GAME WITH
TRANSPORTATION COSTS

where the V nodes represent market locations and a directed
edge connecting two nodes represents a road connecting two
markets. We characterize the network by its incidence matrix
B ∈ {0, 1, −1}V ×E , where E is the number of edges and
Bv,e = −1 if edge e leaves node v, Bv,e = 1 if edge e enters
node v and Bv,e = 0 otherwise. Denote by ri ∈ R≥0 the
total amount
of commodity produced and sold by firm i (i.e.,
P
ri = v∈V yvi ) and by tie ∈ R≥0 the amount of commodity
transported by firm i over edge e, with ti = [tie ]E
e=1 . Define
the strategy vector of firm i as xi := [ti ; ri ] ∈ RE+1
≥0 , which
uniquely determines y i := [yvi ]Vv=1 , due to the balance equation
y i = Bti + e`i ri = H i xi ,
with H i := [B, e`i ] ∈ RV×(E+1) and ej the j th canonical vector.
1) Cost function: We assume that at each market the
commodity is sold at a price that depends on the total commodity sold by the N firms. We allow for intermarket effects and use the inverse demand function4 p :
RV≥0 → RV≥0 that maps the normalized vector σ∞ (x) =
PN j
PN
1
1
j j
j=1 y = N
j=1 H x to the vector of prices of each
N
market p(σ∞ (x)) := [pv (σ∞ (x))]Vv=1 . Then the revenue of
firm i is p(σ∞ (x))> y i . Moreover, for firm i transporting tie
commodity over an edge comes with a cost equal to
cie (tie ) := βei tie − γei (tie ),

(17)

where, for all i, γei is a strongly concave, increasing function
with maximum derivative smaller than βei . The transportation
cost in (17) can be thought of as the sum of two terms: the first
is a cost proportional to the amount shipped, the second term is
a discount that increases as the amount of shipped commodity
increases.
The production cost function of firm i has a similar form
ai (ri ) := βai ri − γai (ri ),

(18)

where γai is a strongly concave, increasing function with maximum derivative smaller than βai . Note that the functions (17)
and (18) are strongly convex, as in [9, Section 1.4.3].
To sum up, the cost function of firm i is
PE
i i
J (x , σ∞ (x)) := ai (ri ) + e=1 cie (tie ) − p(σ∞ (x))> y i .
| {z }
|
{z
}
|
{z
}
production cost

transportation cost

revenue

2) Constraints: The strategy of firm i must satisfy the
individual constraints
i
i
i
i i
X i := {xi ∈ RE+1
≥0 |x ≤ r̄ · 1E+1 , y = H x ≥ 0},

(19)

Consider a single-commodity3 Cournot game with N firms
and V markets, which correspond to V physical locations. Firm
i ∈ Z[1, N ] chooses to sell yvi ∈ R≥0 amount of commodity at
each market v ∈ Z[1, V ]. Each firm i produces its commodity
at a given location `i ∈ Z[1, V ] and then ships its commodity to the different markets over a transportation network,

where r̄i is the production capacity of firm i. Note that (19)
implies tie ≤ r̄i for each e, which is needed to guarantee boundedness of X i and can be imposed without loss of generality, as
the transportation costs cie are increasing.
Moreover, we assume that each market v is composed by
retailers whose storage capacity imposes an upper bound Kv
on the total commodity that can be sold at market v, thus giving
rise to the coupling constraints σ∞ (x) ≤ K := [Kv ]Vv=1 .

3 The analysis applies also to a multi-commodity game as in [11, Section
7.1], but we consider a single-commodity game for ease of exposition and we
rather focus on the transportation costs.

4 The inverse demand function determines the price for which demand
equals supply at market v. This is why we can assume that all the supply is
sold.

A. Game definition

8

3) Communication network: We assume that the firms can
communicate with each other according to a sparse communication network, described by the adjacency matrix T , which we
assume satisfies Assumption 1. This network can model spatial
proximity of firms, or the fact that they may want to share their
strategies only with firms they trust.

z∈[0,r̃]

B. Theoretical guarantees
The cost, constraints and communication network introduced
above give rise to a game as in (2), with the only difference
that the aggregate σ∞ (x) depends on y i = H i xi instead of xi
directly. We next show that our theory can be easily extended
to cover such case.5
1) Extension: Set Hblkd := blkdiag(H 1 , . . . , H N ) ∈
N V ×N (E+1)
R
. The quantities in (7) relative to G∞ are
F∞ (x) := [∇xi J i (xi , σ∞ (x))]N
i=1 ,
i

i

= [∇z1 J (x , σ∞ (x)) +
1

1) p is affine, i.e., p(σ∞ (x)) = −Dσ∞ (x) + d, for some
D ∈ RV ×V , d ∈ RV and D  0.
2) pv depends only on the commodity sold at v, i.e.,
p(σ∞ (x)) =: [pv ([σ∞ (x)]v )]Vv=1 . For each v, pv is twice
continuously differentiable, strictly decreasing and satisfies


r̃
min
−p0v (z) + p00v (z) > 0, r̃ := max r̄i . (22)
8
i∈Z[1,N ]
v∈{1,...,V }

(20a)

1
i i
N
>
N Hi ∇z2 J (x , σ∞ (x))]i=1 ,

N

Q∞ := {x ∈ X × · · · × X |A∞ x ≤ b},


1
>
A∞ :=
1N 1N ⊗ Â Hblkd ,
N
b := 1N ⊗ b̂.


Lemma 3. If Assumption 4 holds then the Cournot game in
Section V-A satisfies Assumption 3.

The proof is reported in Appendix C.
Remark 2. If the function p is as in Assumption 4.1) and
D = D> , then G∞ is a potential game [31]. In other words,
there exists a function f : Q → R such that ∇x f (x) = F∞ (x)
and VI(Q∞ ,F∞ ) is equivalent to argmin f (x), as described
x∈Q∞

(20b)

in [9, Section 1.3.1]. Then a Nash equilibrium can be found by
solving the optimization program argmin f (x). We also note

(20c)

that condition (22) is satisfied if for each market v the function
pv is convex and strictly decreasing.


x∈Q∞

(20d)

Regarding the Standing Assumption, Assumption 3 implies
that
J i is continuously differentiable in its arguments and
The quantities in (6) relative to Gν are
that ∇x [∇xi J i (xi , σ∞ (x))]N
i=1  αIN (E+1) by Proposition 2,
i i
Fν (x) := [∇xi J i (xi , σνi (x))]N
,
(21a)
i
which
in
turn
implies
∇
∇
i=1
x
xi J (x , σ∞ (x))  αIE+1 , which
i
i
i i
i
ν
>
i i
i
N
implies
convexity
of
J
in
x
for
all fixed x−i . The sets X i are
= [∇z1 J (x , σν (x)) + [T ]ii Hi ∇z2 J (x , σν (x))]i=1 ,
trivially
convex,
compact
and
non-empty.
1
N
Qν := {x ∈ X × · · · × X |Aν x ≤ b},
(21b)
Finally, the next lemma shows that for the network, number
ν
:=
Aν
(T ⊗ Â)Hblkd .
(21c) of communications ν and price functions used in the numerical
The only assumption of Sections II-III that needs to be analysis of the next subsection, Fν is strongly monotone, as
modified is Assumption 2, which, due to the presence of Hblkd required by Theorem 3.
in (20c), cannot be expressed on the sole Â and b̂ and is hence Lemma 4. Under Assumption 4.1), if T is the adjacency
replaced by the following one.
matrix of an undirected network, so that T = T > , then the
Assumption 2’ (Coupling constraints). The matrix A∞ operator Fν is strongly monotone for any ν even.

in (20c) and the vector b in (20d) are such that the following
The proof is reported in Appendix C.
implication holds.
{A>
∞ s = 0,

b> s ≤ 0,

s ≥ 0}

⇒

s = 0.



The proofs of Theorems 1 and 2, which made use of Assumption 2, can be conducted in the same way using Assumption 2’.
2) Verify the assumptions: To use Theorem 1 in the numerical analysis of the next subsection, we need to verify
its assumptions. Assumption 1 holds by problem statement.
Assumption 2’ is satisfied, because the implication {(1N ⊗
K)> s ≤ 0, s ≥ 0} ⇒ s = 0 is satisfied, given that K > 0.
To guarantee that Assumption 3 holds we make the following
assumption, whose sufficiency is proven in Lemma 3.
Assumption 4 (Cournot-game regularity conditions). The cost
J i (z1 , z2 ) is twice continuously differentiable for all i, and
the inverse demand function p satisfies one of the following
conditions.
5 Defining a new game with strategies x̃i = H i xi , so that the aggregate
depends only on the x̃i , is not possible in general as the cost J i (xi , σ∞ (x))
cannot be expressed as a function of the variables x̃i s unless H i is full column
rank for all i. This is not the case in the Cournot game under consideration.

C. Numerical analysis
We consider two simulation setups. The first is a small
example to develop intuition about the problem, the second
is used to illustrate the applicability of our method for a more
realistic scenario.
1) Small network: We consider a simple chain transportation network with V = 5 markets, E = 4 roads and N = 3
firms. As illustrated in Figure 1 we assume that the firms
{1, 2, 3} are located at markets {1, 3, 5}, respectively, and are
otherwise identical, with r̄i = 5 for all i.
firm
i=2

firm
i=1
v=1

v=2

v=3

firm
i=3
v=4

v=5

Fig. 1: Small network with the 3 firms located in markets 1, 3, 5,
respectively. The transportation network is represented with a
solid line, the communication network with a dashed line.

9

3

Regarding the cost functions, for each firm i, we set

2



1



1
∀e,
cie (tie ) = ce (tie ) = tie − 1 −
1 + tie



1
i i
i
i
a (r ) = a(r ) = 2 r − 1 −
.
1 + ri

(23a)

3

(23b)

For each market v, we consider the inverse demand function
pv to be affine and independent from the commodity sold at
other markets. Specifically, for all v, pv (σ) = 10 − σv . We
assume that firm 2 bidirectionally communicates with firms 1
and 3, while 1 and 3 do not communicate, according to the
communication matrix


2/3 1/3
0
T =  1/3 1/3 1/3  ,
0
1/3 2/3
which is primitive and doubly stochastic, hence satisfies Assumption 1.
We run Algorithm 1 with τ = 0.005, ν = 10 and
initial conditions all equal to zero6 . We use max{kx(k) −
x(k−1) k∞ , kλ(k) − λ(k−1) k∞ } < 10−4 as stopping criterion.
Figure 2 (top) reports the sales y i for each firm in the 5 markets
at the variational Nash equilibrium of Gν (with ν = 10), for the
case when there are no coupling constraints (i.e., K is chosen
so large that it has no effect). Figure 2 (bottom) reports how
the equilibrium changes if we introduce the coupling constraint
[σ∞ (x)]3 ≤ 1/3, so that the total capacity of market 3 is 1. In
both cases the Gν (with ν = 10) variational equilibrium is
an εν -Nash equilibrium for G∞ , as by the second statement of
Theorem 2. The value of εν can be computed after convergence
according to Definition 1. A more descriptive quantity is the
relative maximum improvement ε̂ν , defined as7
P
J i (x̄iν , σ∞ (x̄ν )) − J i (xi , N1 xi + j6=i N1 x̄jν )
ε̂ν := max
,
J i (x̄iν , σ∞ (x̄ν ))
i,xi ∈Qi∞ (x̄−i
ν )
(24)
which equals 0.0014 (for the game without coupling constraint)
and 0.0035 (for the game with coupling constraint).
2) Large network: As a more realistic example we consider
the transportation network illustrated in Figure 4 which consists
of V = 43 possible markets and E = 51 (bidirectional) edges
connecting them. The network is taken from the data set [32],
which provides also the Cartesian coordinates of the vertexes.
We consider 5 firms that differ only for their locations `i , which
are `1 = 37, `2 = 20, `3 = 11, `4 = 6, `5 = 35 as indicated in
Figure 4. Each firm has a production capacity of r̄i = 10, while
we consider a capacity of 1.5 for each market (i.e. K = 1.5/5).
The production cost is as in (23b) while the transportation cost
for edge e is the same for each firm i and is



1
cie (tie ) = ce (tie ) = ρe tie − 1 −
,
1 + tie
6 The values in (15) can be shown to be α = 4/(1 + r̃)3 = 0.0185,
ν
> [(I ⊗ D)(T ν ⊗ I ) + diag(T ν ) ⊗ D > ]H
Lν = λmax (Hblkd
blkd ) = 9.9124
N
E
and kAν k = 1; then (15) reads τ < 1.8 · 10−4 . This is a conservative bound,
we verified by simulations that the algorithm converges also for τ = 0.005.
7 Note that for any fixed x̄ , ε̂ in (24) can be computed by solving the N
ν
ν
1 i P
1 j
optimization problems {minxi ∈Qi (x̄−i ) J i (xi , N
x + j6=i N
x̄ν )}N
i=1 .
∞

ν

0
2
1
0

market 1

market 2

market 3

market 4

market 5

Fig. 2: Production per firm and market without coupling constraints (top) and with the coupling constraint [σ i (x)]3 ≤ 1/3
(bottom). In both cases the total production at the equilibrium
is ri = r̄i = 5 for all i. Both simulations are obtained with
ν = 10 communications.

where ρe ∈]0, 1] is the normalized8 length of road e. The inverse
demand function p is affine, i.e. p(σ) = 10 · 145 − Dσ and
it encodes intra-market competition via the matrix D whose
component in position (h, k) is [D]h,k = 1 if h = k, [D]h,k =
0.3(1 − ρe ), if there is a road e = (h, k) between markets h
and k, while [D]h,k = 0 otherwise. In words, the price pv at
market v not only decreases when more commodity is sold at
v, but also when more commodity is sold at the neighboring
markets, with physically close markets being more influential.
We verified numerically that D  0. We use the communication
matrix T that corresponds to a symmetric ring, i.e.,


0 0.5 0 0 0.5
0.5 0 0.5 0 0 


T =  0 0.5 0 0.5 0  ,
 0 0 0.5 0 0.5
0.5 0 0 0.5 0
which satisfies Assumption 1. We run Algorithm 1 with
τ = 0.05, initial conditions all equal to zero and different
values of ν 9 . As for the small network, we use max{kx(k) −
x(k−1) k∞ , kλ(k) − λ(k−1) k∞ } < 10−4 as stopping criterion.
We consider even values of ν between 2 and 20. For each ν we
run Algorithm 1 and find the variational Nash equilibrium of
Gν , which is an εν -Nash equilibrium for G∞ , as by the second
statement of Theorem 2. After convergence εν can be computed
according to Definition 1 and ε̂ν according to (24). Figure 3
(top) reports the value of ε̂ν as function of ν, thus numerically
verifying the second statement of Theorem 2. Figure 3 (bottom)
reports the value of kx̄ν − x̄∞ k2 as function of ν, thus
numerically verifying the first statement (8) of Theorem 2. In
Figure 4 we illustrate the variational Nash equilibrium of G∞
obtained by setting ν = 1 and T = N1 1N 1>
N . We note that
each firm is the only seller at the location where it produces,
and more in general firms tend to sell close to their production
location, as expected.
8 The normalized length of a road is defined as the absolute length divided
by the maximum length road in the network.
9 The values in (15) can be shown to be α = 4/(1 + r̃)3 = 0.003,
ν
> [(I ⊗ D)(T ν ⊗ I ) + diag(T ν ) ⊗ D > ]H
Lν = λmax (Hblkd
blkd ) = 12.89
N
E
−5
and kAν k = 1; then (15) reads τ < 1.8 · 10 . This is a conservative bound,
we verified by simulations that the algorithm converges also for τ = 0.05.

10

2

A. Immediate generalizations

ε̂ν

1
0
6
kx̄ν − x̄∞ k2

4
2
0

2

4

6

8

10

12

14

16

18

20

number of communications ν

Fig. 3: Relative maximum cost improvement ε̂ν given in (24)
as a function of ν for the large network.
37
40
32
34
29

33
39

26

28

31

25

30

22
21
20
18

19

38
36

35

27

23

24

14
11

16

15

13

9
7

17

10

5

8

3

43

12

4 6

41

42

2
1

yv1

upper bound

2

yv2

yv3

yv4

yv5

1
0

0

5

10

15

20

25

30

35

40

v

Fig. 4: Variational Nash equilibrium of G∞ for the large network, computed by Algorithm 1 for ν = 1 and T = N1 1N 1>
N.
In the top plot, each market takes the color of the firm that sells
the most commodity in that market. The production locations
of the firms are denoted by squares. The bottom plot reports yvi
for each agent i and market v.

VI. C ONCLUSIONS AND FUTURE WORK
In this paper we derived an algorithm to steer the strategies of competitive agents to an almost Nash equilibrium for
any average aggregative game i) by using only distributed
communications and ii) in the presence of affine coupling
constraints expressed on the average population strategy. The
agents synchronously update their strategies and communicate
a fixed number ν of times with their in-neighbors and outneighbors between two strategy updates. Our findings are based
on a novel convergence result for parametric VI, which is of
independent interest.
In the following subsections, we briefly comment on some
immediate generalizations of the results above, that were omitted to keep the exposition simple, and on possible future works.

1) Distributed algorithm for network aggregative games:
Algorithm 1 is used here to find an ε-Nash of G∞ . However,
if we assume that Fν in (6a) is strongly monotone when ν =
1, then Algorithm 1 can be used to find the variational Nash
equilibrium of any network aggregative game, as defined in [8]
with network T , by setting ν = 1. Algorithm 1 thus constitutes
an alternative to the distributed algorithms derived for generic
games in [11], [22]. Moreover, note that if we set T = N1 1N 1>
N
and ν = 1 then Algorithm 1 achieves the variational Nash
equilibrium of G∞ , but communications among all agents are
required.
2) Weighted average: The above results can be immediately
generalized to aggregative games that depend P
on a weighted
N
average of the population strategies σ∞ (x) = i=1 wi xi , for
PN i
1
some wi > 0 instead of P
the average σ∞ (x) = N i=1 x used
above. We can impose i wi = 1 without loss of generality.
Then Assumption 1 can be modified to require T to be a
primitive matrix with w > 0 as left eigenvector relative to
the eigenvalue 1 (normalized such that w> 1N = 1).
3) Local strategy sets of different dimensions: In the previous sections we have assumed that the strategy set of each
agent has n components, i.e, X i ⊂ Rn . Following the same
arguments as in Section V-B1), our results can be generalized to
the case in which each agent features a strategy set of different
i
, as in [10], [11] and the aggregate
dimension, i.e, X i ⊂ RnP
N
strategy is σ i (x) = N1 j=1 [H j xj + hj ] ∈ Rn , for some
matrices H j ∈ Rn×nj and vectors hj ∈ Rn .
4) Wardrop instead of Nash equilibrium: The focus of this
paper is on Nash equilibrium, but the setup and the results
extend to another important concept in game theory, namely
the Wardrop equilibrium as defined in [18, Definition 2], often
used in transportation with the name of traffic equilibrium [33]
and economics with the name of competitive equilibrium [34].
i
If in the primal update of Algorithm 1 we use Fν,(k)
←
i i
i
∇z1J (x(k) , σν,(k) ) (neglecting thus the second summand) then
Algorithm 1 converges to a Wardrop equilibrium.

B. Future directions
There are a number of research directions that can be
investigated as future work. Firstly, in our algorithm the agents
communicate over a fixed network T . It would be valuable to
extend our results to the case of time-varying or state-varying
communication networks. It may also be interesting to relax
the assumption of synchronous updates. Moreover, the result
on convergence of parametric VI could be extended to the case
of continuous parameters and to establish Lipschitz continuity
of the solution. The latter would be valuable to derive bounds
on the number of communications ν needed to approximate the
Nash equilibrium with any desired precision. To the best of our
knowledge, the only results guaranteeing Lipschitz continuity
require the linear independence constraint qualification. Finally,
as for all distributed communication schemes, it would be
important to assess the algorithm performance in the presence
of delay and packet loss.

11

A PPENDIX
A. Definitions
Definition 4 (Kuratowski convergence of sets [35, (2.1)]). A
sequence of sets (Sν ⊆ Rn )∞
ν=1 is said to Kuratowski converge
to a set S ⊆ Rn , in symbols Sν → S, if
lim sup Sν ⊆ S ⊆ lim inf Sν
(25)
where
lim inf Sν := {x ∈ Rn |x = lim xν , xν ∈ Sν },
ν→∞

lim sup Sν := {x ∈ Rn |x = lim xνk , xνk ∈ Sνk },
k→∞

and νk is a subsequence of N.



Note that lim inf Sν ⊆ lim sup Sν by definition. Condition (25)
requires the opposite inclusion to hold.
Definition 5 (Hausdorff convergence of sets [35, p. 22]). The
Hausdorff distance between two non-empty subsets R and S
of Rn is defined as
dH (R, S) := max{sup inf kr −sk2 , sup inf kr −sk2 } . (26)
r∈R s∈S

s∈S r∈R

Rn )∞
ν=1

A sequence of sets (Sν ⊆
is said to Hausdorff
converge to S ⊆ Rn if limν→∞ dH (Sν , S) = 0.

We point out that Hausdorff set convergence (Definition 5)
is in general stronger than Kuratowski set convergence (Definition 4) as shown in Theorems 2 and 3 of [35].
B. A convergence result for parametric variational inequalities
The notation used in this section is disjoint from the rest
of the paper. We study the convergence of the solution x̄θ of
VI(Qθ , Fθ ) to the solution x̄θ̂ of VI(Qθ̂ , Fθ̂ ) when θ → θ̂ and
both the set and the operator are affected by the parameter
θ. In the literature on convergence of solutions of parametric
variational inequalities it is common to assume that Fθ̂ is
strongly monotone and that Fθ converges uniformly to Fθ̂ as
θ → θ̂. Besides that, the literature on the topic can be divided
into three classes, based on the assumptions on the sets.
1) The first class of results focuses on sets that do not change,
so that only the operator is affected by the parameter, and
studies convergence of the solution x̄θ of VI(Q, Fθ ) to the
solution x̄θ̂ of VI(Q, Fθ̂ ). If the set Q is closed and convex, Fθ
is Lipschitz in θ uniformly in x and Fθ̂ is strongly monotone,
then the solution is Lipschitz continuous [36, Theorem 1.14],
[9, Section 5.3]. Strong monotonicity of Fθ̂ can be relaxed if
the set Q is a polyhedron [37].
2) The second class of results [38], [39], [40] focuses
on parametric sets that can be described as Qθ := {x ∈
Rn | g(x, θ) ≤ 0} for a suitable parametric function g(x, θ).
Assuming that g(x, θ) converges uniformly in x to g(x, θ̂)
as θ → θ̂ and that at x̄θ̂ the linear independence constraint
qualification holds, it can be shown that the parametric solution
x̄θ is locally Lipschitz continuous around θ̂. Such results have
been applied to games, as for example in [41], [42].
3) The third class of results [40], [43] is the most general
and only assumes that Qθ converges to Qθ̂ according to the

Kuratowski set convergence definition. In this case one can
prove continuity of x̄θ around θ̂. We are not aware of results
proving local Lipschitz continuity in this case.
Here we do not assume the linear independence constraint
qualification, because this is difficult to guarantee a priori for
G∞ . Instead, we focus on a specific form of the sets and prove
convergence in Kuratowski as well as Hausdorff distance. We
then exploit the results of [40], [43] to show continuity of the
VI solution. It is important to highlight that we do not consider
a continuous parameter θ tending to θ̂, but we rather focus on
the slightly less general case of a discrete parameter ν ∈ N
that tends to infinity, since this is what is needed in Theorem 2.
Specifically, we consider sets Qν and Q∞ that take the form
Qν := {x ∈ X ⊂ Rn |Aν x ≤ bν },
Q∞ := {x ∈ X ⊂ Rn |A∞ x ≤ b∞ },
with X convex and compact, Aν , A∞ ∈ Rm×n , bν , b∞ ∈ Rm ,
and consider operators Fν : X → Rn , F∞ : X → Rn .
Our result can also be interpreted as an extension of [44],
[45] on parametric quadratic programs, and of [37], [46] on
parametric variational inequalities over polyhedral sets, in that
we consider sets that are obtained as the intersection of a
parametric polyhedron with a generic convex and compact set
X . Finally, we note that the parameter appears also in the matrix
Aν and not only in bν , as in [46], [47], [48]. The following
assumption summarizes the specifics of our setup.
Assumption B.1. Suppose that
a) The set X ⊂ Rn is convex, compact and has non-empty
interior. Moreover, limν→∞ Aν = A∞ , limν→∞ bν = b∞ and
>
{A>
∞ s = 0, b∞ s ≤ 0, s ≥ 0}

⇒

s = 0.

(27)

b) The operator F∞ : X → Rn is continuous, strongly
monotone and there exists νSMON > 0 such that Fν : X → Rn
is continuous, strongly monotone for each ν > νSMON . For
each x ∈ X , limν→∞ Fν (x) = F∞ (x).

We note here that (27) is less restrictive than the assumption
that A∞ has full row rank (i.e., A>
∞ s = 0 ⇒ s = 0), which is
usually imposed to guarantee the linear independence constraint
qualification a priori, see for example [40, Remark 2.2].
The next Lemma B.1 proves Kuratowski and Hausdorff
convergence of the sets. Kuratowski convergence of Qν → Q∞
is a key part of the proof of Theorem B.1. The fact that
dH (Qν , Q∞ ) → 0 is instead used in Lemma C.1 of Appendix C, which is needed for the proof of Theorem 2.
Lemma B.1. If Assumption B.1a holds then as ν → ∞ we
have
Qν → Q∞ and dH (Qν , Q∞ ) → 0.

Proof: We define Sν := {x ∈ Rn |Aν x ≤ bν }, S∞ :=
{x ∈ Rn |A∞ x ≤ b∞ } and start by showing that Sν → S∞ . To
show lim sup Sν ⊆ S∞ , consider an arbitrary x̂ ∈ lim sup Sν ,
a sequence (νk )∞
k=1 , νk → ∞ and points xνk ∈ Sνk such that
xνk → x̂. Since Aνk xνk ≤ bνk for all k > 0, passing to the
limit as νk → ∞ we obtain A∞ x ≤ b∞ , hence x̂ ∈ S∞ .
Conversely, we show S∞ ⊆ lim inf Sν . Consider an arbitrary
x̂ ∈ S∞ , to show that x̂ ∈ lim inf Sν one needs to construct a

12

sequence (xν )∞
ν=1 with xν ∈ Sν and such that xν → x̂. To this
end, define Ã : [0, 1] → Rm×n , b̃ : [0, 1] → Rm×1 by
(
Ab1/|t|c if t ∈ (0, 1]
Ã(t) :=
A∞
if t = 0
(
bb1/|t|c if t ∈ (0, 1]
b̃(t) :=
b∞
if t = 0.
Note that Aν = Ã(1/ν), bν = b̃(1/ν) for all ν ∈ N. By
Assumption B.1a,
Ã(t) −−−→ Ã(0) = A∞ ,
t→0

b̃(t) −−−→ b̃(0) = b∞ .
t→0

Let

x̃(t) := ΠS̃(t) [x̂] = argmin

kx − x̂k2

x∈Rn

s.t.

Ã(t)x ≤ b̃(t)

Proof: We show this statement in two steps. Specifically,
we show that for every ε > 0 there exists ν̃ > 0 such that for
all ν > ν̃ and all i ∈ Z[1, N ]
1) dH (Qi∞ (x̄−i ), Qi∞ (x̄−i
ν )) ≤ ε/2, and
2) dH (Qi∞ (x̄−i ), Qiν (x̄−i
ν )) ≤ ε/2.
The conclusion then follows by the triangular inequality of the
Hausdorff distance.
1) Note that
X
Qi∞ (x̄−i ) := {xi ∈ X i |Âxi ≤ N b̂ −
Âx̄j =: bi },
Qi∞ (x̄−i
ν )

be the projection of x̂ onto S̃(t) := {x ∈ Rn |Ã(t)x ≤ b̃(t)}.
Assumption B.1a implies that the regularity conditions required
by [44, Theorem 2.2] are met, hence x̃(t) is continuous at t = 0,
that is
x̃(t) → x̃(0) = ΠS̃(0) [x̂] = ΠS∞ [x̂] = x̂ .
Consider now the sequence (xν := x̃(1/ν))∞
ν=1 . Clearly xν ∈
S̃(1/ν) = Sν and limν→∞ xν = x̂, thus proving that x̂ ∈
lim inf Sν . We have thus shown that Sν → S∞ . Since Qν =
Sν ∩ X and Q∞ = S∞ ∩ X , X is closed and convex with
non-empty interior and Sν is closed and convex for all ν, by
[43, Lemma 1.4] we have that Qν → Q∞ .
To conclude, since Qν are closed subsets of Rn for all ν
and Q∞ is compact and non-empty, using [35, Theorem 3]
we obtain that Qν → Q∞ implies dH (Qν , Q∞ ) → 0, thus
completing the proof.
We use Lemma B.1 and [43, Theorem A(b)] to show
that the solution of VI(Qν , Fν ) converges to the solution of
VI(Q∞ , F∞ ).
Theorem B.1. If Assumption B.1 holds then VI(Q∞ , F∞ ) has
a unique solution x̄∞ and, for ν > νSMON , VI(Qν , Fν ) has a
unique solution x̄ν . Moreover
x̄ν → x̄∞ .

Lemma C.1. Consider the sequence (x̄ν ∈ RN n )∞
ν=1 , let
Assumption 2 hold and suppose that x̄ν → x̄. Then, for
every ε > 0 there exists ν̃ > 0 such that for all ν > ν̃,
all i ∈ Z[1, N ] and all xi ∈ Qi∞ (x̄−i
ν ) there exists an
i
i
i
−i
x̃iν ∈ Qiν (x̄−i
ν ) such that kx − x̃ν k ≤ ε, where Q∞ (x̄ν )
i
−i
and Qν (x̄ν ) are defined in (7c) and (6c) respectively.




Proof: The fact that VI(Q∞ , F∞ ) and VI(Qν , Fν ) (for
ν > νSMON ) have a unique solution is an immediate consequence of Proposition 1. To prove convergence we apply [43, Theorem A(b)] to the sequence (VI(Qν , Fν ))∞
ν=1
and to VI(Q∞ , F∞ ). All the assumptions of [43, Theorem
A(b)] are direct consequences of Assumption B.1, except for
Qν → Q∞ , which is proven in Lemma B.1. We can conclude
that x̄ν → x̄∞ .
C. Auxiliary result and omitted proofs
The following Lemma C.1 is used in the proof of Theorem 2,
but it is reported here for ease of readability, as it uses the
definitions of Appendix A and Lemma B.1 of Appendix B.

i

i

i

:= {x ∈ X |Âx ≤ N b̂ −

j6=i
X

Âx̄jν =: biν }.

j6=i

By assumption x̄ν → x̄. Consequently,
that the implication
{Â> ŝ = 0,

(bi )> ŝ ≤ 0,

biν

ŝ ≥ 0}

→ bi . We now show
⇒

ŝ = 0

holds. The inequalities (bi )> ŝ ≤ 0 and Â> ŝ = 0 imply
X
>
X
Âx̄j ŝ =
N b̂> ŝ ≤
(x̄j )> (Â> ŝ) = 0
j6=i

⇒

j6=i

b̂> ŝ ≤ 0.

By Assumption 2 we obtain ŝ = 0. Consequently, the sets
Qi∞ (x̄−i ), Qi∞ (x̄−i
ν ) satisfy (27) and hence Assumption B.1a,
so the conclusion follows by Lemma B.1.
2) It can be proven similarly as the previous one. Note that the
value of ν̃ used in the proof might depend on Â, b̂, x̄, but not on
x̄ν . This comes from proving the statement in two steps instead
−i
i
of applying Lemma B.1 directly to Qiν (x̄−i
ν ), Q∞ (x̄ν ).
Proof of Lemma 2
Observe that
(Fν (x) − Fν (y))> (x − y) = (F∞ (x) − F∞ (y))> (x − y)+
(Fν (x) − F∞ (x) − (Fν (y) − F∞ (y)))> (x − y) ≥
(αF∞ − `ν )kx − yk2 ,
where `ν is the Lipschitz constant of Fν − F∞ (recall that J i
are twice continuously differentiable. As J i (z1 , z2 ) is twicecontinuously differentiable in z1 , z2 and σν (x) → σ∞ (x)
uniformly in x, then ∇x (Fν (x) − F∞ (x)) → 0 uniformly in x
and hence `ν → 0, thus concluding the proof.
Proof of Lemma 3
We start by computing the operator F∞ (x).


E
X
F∞ (x) = [∇xi ai (ri ) +
cie (tie ) ]N
i=1 + P (x),
e=1

where P (x) := −[∇xi (p(σ∞ (x))> y i )]N
i=1 . Since for each i
the functions ai and cie are strongly convex and continuously

13

differentiable, by Proposition 2 and [49, equation (12)] there
exists α > 0 such that


E
X
∇x ([∇xi ai (ri ) +
cie (tie ) ]N
i=1 )  αIN (E+1) , ∀ x ∈ X .
e=1

We now prove that ∇x P (x)  0 under either of the two
conditions stated.
1) We have
hX
iN
N · P (x) :=
Hi> DHj xj + Hi> D> Hi xi −N Hi> d
j
>

= [H DH +

i=1

>
Hblkd
D> Hblkd ]x

−

N [Hi> d]N
i=1 ,

>
with H := ([Hi> ]N
and Hblkd = blkdiag(H1 , . . . , HN ).
i=1 )
Moreover, since D  0, then
1
>
D> Hblkd )  0.
(28)
∇x P (x) = (H > DH + Hblkd
N
PN
2) Let P̃ (y) := −[∇yi (p( N1 j=1 y j )> y i )]N
i=1 . It was shown
in [18, Corollary 1], that if (22) holds, then there exists α0 > 0
such that ∇y P̃ (y)  α0 INE . Moreover, from p(σ∞ (x))> y i =
PN
p( N1 j=1 H j xj )> H i xi one immediately gets that P (x) =
>
P̃ (Hblkd x). It follows that for any x and corresponding
Hblkd
y = Hblkd x,
>
∇x P (x) = (Hblkd
∇y P̃ (y)Hblkd )|y=Hblkd x  0.

(29)

We have proven that ∇x F∞ (x)  αIN (E+1) for all x.
Consequently, F∞ is strongly monotone by Proposition 2 and
the first statement of Assumption 3 holds. The second statement
in Assumption 3 can be proven by using Lemma 2.
Proof of Lemma 4
The expression of Fν (x) is very similar to F∞ (x) in
Lemma 3


E
X
Fν (x) = [∇xi ai (ri ) +
cie (tie ) ]N
(30)
i=1 + Pν (x),
e=1

where Pν (x) := −[∇xi (p(σνi (x))> y i )]N
i=1 . Since Fν is continuously differentiable, we can prove its strong monotonicity
by showing that there exists α > 0 such that ∇x Fν (x) 
αIN (E+1) , thanks to Proposition
3, there
 2. As in Lemma 
P
E
exists α > 0 such that ∇x [∇xi ai (ri ) + e=1 cie (tie ) ]N
i=1 
αIN (E+1) for all x, hence the proof is concluded upon showing
that for all ν even, ∇x Pν (x)  0. If we denote P̃ν (y) :=
−[∇yi (p(σνi (y))> y i )]N
i=1 then simple algebraic computations
show that
∇y P̃ν (y) = blkdiag([T ν ]11 D, . . . , [T ν ]N N D) + T ν ⊗ D.
(31)
Note that [T ν ]ii ≥ 0 for all i and for all ν, hence the first
summand in (31) is positive semidefinite. Note that, as the
matrix T is symmetric, T ν  0 for all ν even and thus
T ν ⊗D  0 since it is the Kronecker product of two symmetric
positive semidefinite matrices. Overall, we have ∇y P̃ν (y)  0
for all ν even. Finally, as in (29), we have
>
∇x Pν (x) = (Hblkd
∇y P̃ν (y)Hblkd )|y=Hblkd x  0.

R EFERENCES
[1] J. R. Correa, A. S. Schulz, and N. E. Stier-Moses, “Selfish routing in
capacitated networks,” Mathematics of Operations Research, vol. 29,
no. 4, pp. 961–976, 2004.
[2] T. Alpcan, T. Başar, R. Srikant, and E. Altman, “CDMA uplink power
control as a noncooperative game,” Wireless Networks, vol. 8, no. 6, pp.
659–670, 2002.
[3] Z. Ma, D. S. Callaway, and I. A. Hiskens, “Decentralized charging control of large populations of plug-in electric vehicles,” IEEE Transactions
on Control Systems Technology, vol. 21, no. 1, pp. 67–78, 2013.
[4] R. Johari and J. N. Tsitsiklis, “Efficiency loss in a network resource
allocation game,” Mathematics of Operations Research, vol. 29, no. 3,
pp. 407–435, 2004.
[5] S. Kar and G. Hug, “Distributed robust economic dispatch in power
systems: A consensus + innovations approach,” in IEEE Power and
Energy Society General Meeting, 2012.
[6] Y. Pan and L. Pavel, “Games with coupled propagated constraints in
optical networks with multi-link topologies,” Automatica, vol. 45, no. 4,
pp. 871–880, 2009.
[7] S. Grammatico, F. Parise, M. Colombino, and J. Lygeros, “Decentralized
convergence to Nash equilibria in constrained deterministic mean field
control,” IEEE Transactions on Automatic Control, vol. 61, no. 11, pp.
3315–3329, 2016.
[8] F. Parise, B. Gentile, S. Grammatico, and J. Lygeros, “Network aggregative games: Distributed convergence to Nash equilibria,” in Proceedings
of the IEEE Conference on Decision and Control, 2015, pp. 2295–2300.
[9] F. Facchinei and J. Pang, Finite-dimensional variational inequalities and
complementarity problems. Springer Science & Business Media, 2007.
[10] M. K. Jensen, “Aggregative games and best-reply potentials,” Economic
theory, vol. 43, no. 1, pp. 45–66, 2010.
[11] P. Yi and L. Pavel, “A distributed primal-dual algorithm for computation
of generalized Nash equilibria with shared affine coupling constraints via
operator splitting methods,” arXiv preprint arXiv:1703.05388, 2017.
[12] D. Paccagnan, M. Kamgarpour, and J. Lygeros, “On aggregative and
mean field games with applications to electricity markets,” in Proceedings of the IEEE European Control Conference, 2016, pp. 196–201.
[13] J. Koshal, A. Nedić, and U. V. Shanbhag, “A gossip algorithm for
aggregative games on graphs,” in Proceedings of the IEEE Conference
on Decision and Control, 2012, pp. 4840–4845.
[14] H. Chen, Y. Li, R. H. Louie, and B. Vucetic, “Autonomous demand side
management based on energy consumption scheduling and instantaneous
load billing: An aggregative game approach,” IEEE Transactions on
Smart Grid, vol. 5, no. 4, pp. 1744–1754, 2014.
[15] F. Parise, S. Grammatico, B. Gentile, and J. Lygeros, “Network aggregative games and distributed mean field control via consensus theory,”
arXiv preprint arXiv:1506.07719, 2015.
[16] J. Koshal, A. Nedić, and U. V. Shanbhag, “Distributed algorithms for
aggregative games on graphs,” Operations Research, vol. 64, no. 3, pp.
680–704, 2016.
[17] 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 Proceedings of
the IEEE Conference on Decision and Control, 2016, pp. 6123–6128.
[18] B. Gentile, F. Parise, D. Paccagnan, M. Kamgarpour, and J. Lygeros,
“Nash and Wardrop equilibria in aggregative games with coupling
constraints,” arXiv preprint arXiv:1702.08789, 2017.
[19] J. B. Rosen, “Existence and uniqueness of equilibrium points for concave
N-person games,” Econometrica: Journal of the Econometric Society,
pp. 520–534, 1965.
[20] F. Facchinei, A. Fischer, and V. Piccialli, “On generalized Nash games
and variational inequalities,” Operations Research Letters, vol. 35, no. 2,
pp. 159–164, 2007.
[21] S. Liang, P. Yi, and Y. Hong, “Distributed Nash equilibrium seeking for aggregative games with coupled constraints,” arXiv preprint
arXiv:1609.02253, 2016.
[22] M. Zhua and E. Frazzoli, “Distributed robust adaptive equilibrium
computation for generalized convex games,” Automatica, vol. 63, pp.
82–91, 2016.
[23] H. Yin, U. V. Shanbhag, and P. G. Mehta, “Nash equilibrium problems
with scaled congestion costs and shared constraints,” IEEE Transactions
on Automatic Control, vol. 56, no. 7, pp. 1702–1708, 2011.
[24] M. Huang, P. E. Caines, and R. P. Malhamé, “Large-population costcoupled LQG problems with nonuniform agents: Individual-mass behavior and decentralized ε-Nash equilibria,” IEEE Transactions on
Automatic Control, vol. 52, no. 9, pp. 1560–1571, 2007.

14

[25] J.-M. Lasry and P.-L. Lions, “Mean field games,” Japanese Journal of
Mathematics, vol. 2, no. 1, pp. 229–260, 2007.
[26] A. Bensoussan, K. Sung, S. C. P. Yam, and S.-P. Yung, “Linear-quadratic
mean field games,” Journal of Optimization Theory and Applications,
vol. 169, no. 2, pp. 496–529, 2016.
[27] M. Huang, P. E. Caines, and R. P. Malhamé, “Social optima in mean
field LQG control: Centralized and decentralized strategies,” IEEE
Transactions on Automatic Control, vol. 57, no. 7, pp. 1736–1751, 2012.
[28] A. Bensoussan, J. Frehse, and P. Yam, Mean field games and mean field
type control theory. Springer, 2013, vol. 101.
[29] F. Facchinei and C. Kanzow, “Generalized Nash equilibrium problems,”
4OR, vol. 5, no. 3, pp. 173–210, 2007.
[30] R. Olfati-Saber, J. A. Fax, and R. M. Murray, “Consensus and cooperation in networked multi-agent systems,” Proceedings of the IEEE,
vol. 95, no. 1, pp. 215–233, 2007.
[31] D. Monderer and L. S. Shapley, “Potential games,” Games and Economic
Behavior, vol. 14, pp. 124–143, 1996.
[32] T. Brinkhoff, “A framework for generating network-based moving objects,” GeoInformatica, vol. 6, no. 2, pp. 153–180, 2002.
[33] S. Dafermos, “Traffic equilibrium and variational inequalities,” Transportation science, vol. 14, no. 1, pp. 42–54, 1980.
[34] S. Dafermos and A. Nagurney, “Oligopolistic and competitive behavior
of spatially separated markets,” Regional science and urban economics,
vol. 17, no. 2, pp. 245–254, 1987.
[35] R. W. G. Salinetti, “On the convergence of sequences of convex sets in
finite dimensions.” SIAM Review, vol. 22, no. 4, pp. 18–33, 980.
[36] A. Nagurney, Network economics: A variational inequality approach.
Springer Science & Business Media, 2013, vol. 10.
[37] Y. Qiu and T. L. Magnanti, “Sensitivity analysis for variational inequalities defined on polyhedral sets,” Mathematics of Operations Research,
vol. 14, no. 3, pp. 410–432, 1989.
[38] R. Tobin, “Sensitivity analysis for variational inequalities,” Journal of
Optimization Theory and Applications, vol. 48, no. 1, pp. 191–204, 1986.
[39] J. Kyparisis, “Sensitivity analysis framework for variational inequalities,” Mathematical Programming, vol. 38, no. 2, pp. 203–213, 1987.
[40] S. Dafermos, “Sensitivity analysis in variational inequalities,” Mathematics of Operations Research, vol. 13, no. 3, pp. 421–434, 1988.
[41] M. Patriksson and R. T. Rockafellar, “Sensitivity analysis of aggregated
variational inequality problems, with application to traffic equilibria,”
Transportation Science, vol. 37, no. 1, pp. 56–68, 2003.
[42] R. Tobin, “Sensitivity analysis for a Cournot equilibrium,” Operations
research letters, vol. 9, no. 5, pp. 345–351, 1990.
[43] U. Mosco, “Convergence of variational of convex sets and of solutions
inequalities,” Advances in Mathematics, vol. 3, no. 4, pp. 510–585, 1969.
[44] M. J. Best and B. Ding, “On the continuity of the minimum in parametric
quadratic programs,” Journal of Optimization Theory and Applications,
vol. 86, no. 1, pp. 245–250, 1995.
[45] J. C. Boot, “On sensitivity analysis in convex quadratic programming
problems,” Operations Research, vol. 11, no. 5, pp. 771–786, 1963.
[46] N. D. Yen, “Lipschitz continuity of solutions of variational inequalities
with a parametric polyhedral constraint,” Mathematics of Operations
Research, vol. 20, no. 3, pp. 695–708, 1995.
[47] A. G. Hadigheh, O. Romanko, and T. Terlaky, “Sensitivity analysis in
convex quadratic optimization: Simultaneous perturbation of the objective and right-hand-side vectors,” Algorithmic Operations Research,
vol. 2, no. 2, p. 94, 2007.
[48] A. Bemporad, M. Morari, V. Dua, and E. N. Pistikopoulos, “The explicit
linear quadratic regulator for constrained systems,” Automatica, vol. 38,
no. 1, pp. 3–20, 2002.
[49] G. Scutari, D. P. Palomar, F. Facchinei, and J. Pang, “Convex optimization, game theory, and variational inequality theory,” Signal Processing
Magazine, IEEE, vol. 27, no. 3, pp. 35–49, 2010.

