Distributed Nash equilibrium seeking for aggregative games
with coupled constraints ?
Shu Liang a , Peng Yi b , Yiguang Hong a

arXiv:1609.02253v2 [math.OC] 23 Feb 2017

a

Key Laboratory of Systems and Control, Academy of Mathematics and Systems Science, Chinese Academy of Sciences,
Beijing, 100190, China
b

Department of Electrical & Computer Engineering, University of Toronto, Canada

Abstract
In this paper, we study a distributed continuous-time design for aggregative games with coupled constraints in order to seek the
generalized Nash equilibrium by a group of agents via simple local information exchange. To solve the problem, we propose a
distributed algorithm based on projected dynamics and non-smooth tracking dynamics, even for the case when the interaction
topology of the multi-agent network is time-varying. Moreover, we prove the convergence of the non-smooth algorithm for the
distributed game by taking advantage of its special structure and also combining the techniques of the variational inequality
and Lyapunov function.
Key words: Distributed algorithms; aggregative games; generalized Nash equilibrum; projected dynamics; coupled constraints.

1

Introduction

The seek of generalized Nash equilibrium for noncooperative games with coupled constraints has been
widely investigated due to various applications in natural/social science and engineering (such as telecommunication power allocation and cloud computation
(Pang, Scutari, Facchinei & Wang 2008, Ardagna, Panicucci & Passacantando 2013)). Significant theoretic
and algorithmic achievement has been done, referring
to (Pavel 2007, Altman & Solan 2009, Arslan, Demirkol
& Yueksel 2015) and (Facchinei & Kanzow 2010).
Distributed equilibrium seeking algorithms guide a
group of players or agents to cooperatively achieve
the Nash equilibrium (NE), based on players’ local
information and information exchange between their
neighbors in a network. The NE seeking may be viewed
as an extension of distributed optimization problems,
which have been widely studied recently (see (Nedić &
Ozdaglar 2009, Shi, Johansson & Hong 2013, Kia, Cortés
& Martı́nez 2015)), and on the other hand, distributed
? This paper was not presented at any IFAC meeting. Corresponding author Y. Hong. Tel. +86-10-82541824. Fax +8610-82541832.
Email addresses: sliang@amss.ac.cn (Shu Liang),
peng.yi@utoronto.ca (Peng Yi), yghong@iss.ac.cn
(Yiguang Hong).

Preprint submitted to Automatica

optimization problems can be handled with a gametheoretic approach (Li & Marden 2013). In fact, in the
study of complicated behaviors of strategic-interacted
players in large-scale networks, it is quite natural to
investigate game theory in a distributed way. For example, distributed convergence to NE of zero-sum games
over two subnetworks was obtained in (Lou, Hong, Xie,
Shi & Johansson 2016). Moreover, a distributed fictitious play algorithm was proposed in (Swenson, Kar &
Xavier 2015), while a gossip-based approach was employed for seeking an NE of noncooperative games in
(Salehisadaghiani & Pavel 2016).
Aggregative games have become an important type of
games since the well-known Cournot model was proposed, and have recently been studied in the literature,
referring to (Jensen 2010, Cornes & Hartley 2012), for
its broad application in public environmental models (Cornes 2016), congestion control of communication networks (Barrera & Garcia 2015), and demand response management of power systems (Ye &
Hu 2017). Usually, linear aggregation functions and
quadratic cost functions in such games were considered, for example, in (Parise, Gentile, Grammatico &
Lygeros 2015, Paccagnan, Gentile, Parise, Kamgarpour
& Lygeros 2016, Ye & Hu 2017). Also, a recent result
was given for distributed discrete-time algorithms to
seek the NE of an aggregative game with time-varying
topologies in (Koshal, Nedić & Shanbhag 2016).

24 February 2017

Minkowski sum/minus of sets C1 and C2 , and rint(C)
be the relative interior of a convex set C (Rockafellar &
Wets 1998, page 25 and page 64).

The objective of this paper is to develop a novel distributed continuous-time algorithm for nonlinear aggregative games with linear coupled constraints and
time-varying topologies. In recent years, continuoustime algorithms for distributed optimization become more and more popular (Shi et al. 2013, Kia
et al. 2015, Yi, Hong & Liu 2016), partially because they
may be easily implemented in continuous-time or hybrid
physical systems. However, ideas and approaches for
continuous-time design may not be the same as those for
the discrete-time one. Thanks to various well-developed
continuous-time methods, distributed continuous-time
algorithms or protocols keep being constructed, but the
(convergence) conditions may be different from those in
discrete-time cases.

2

Preliminaries

In this section, we give some preliminary knowledge
related to convex analysis, variational inequality, and
graph theory.
A set C ⊆ Rn is convex if λz1 + (1 − λ)z2 ∈ C for any
z1 , z2 ∈ C and 0 ≤ λ ≤ 1. For a closed convex set C, the
projection map PC : Rn → C is defined as
PC (x) , argminy∈C kx − yk.
The following two basic properties hold:

In our problem setup, every player tries to optimize its
local cost function by updating its local decision variable. The cost function depends on not only the local
variable but also a nonlinear aggregation. Moreover, feasible decision variables of players are coupled by linear
constraints. Existing distributed algorithms for aggregative games (Koshal et al. 2016, Ye & Hu 2017) cannot
solve our problems since they did not consider coupled
constraints. The contribution of this paper can be summarized as follows:

(x − PC (x))T (PC (x) − y) ≥ 0, ∀ y ∈ C,
kPC (x) − PC (y)k ≤ kx − yk, ∀ x, y ∈ Rn .

(1)
(2)

For x ∈ C, the tangent cone to C at x is
xk − x
| xk ∈ C, tk > 0,
k→∞
tk
and xk → x, tk → 0}.

TC (x) , { lim

• The aggregative game model in this paper generalizes the previous ones in (Paccagnan et al. 2016, Ye
& Hu 2017) by allowing nonlinear aggregation term
and non-quadratic cost functions, and also those
in (Koshal et al. 2016) by considering coupled constraints. In addition, the considered game can be
non-potential.
• Inspired from distributed average tracking dynamics
and projected primal-dual dynamics, we take advantage of continuous-time techniques to solve the distributed problem. With the new idea, our algorithm
is described as a non-smooth multi-agent system with
two interconnected dynamics: a projected gradient
one for the equilibrium seeking, and a consensus one
for the synchronization of the aggregation and the
dual variables. In addition, our algorithm need not
solve the best response subproblems, different from
those in (Parise et al. 2015), and can keep private some
information about the cost functions, local decisions,
and constraint coefficients.
• We provide a method to prove the correctness and convergence of the continuous-time algorithm by combining the techniques from variational inequality theory
and Lyapunov stability theory.

and the normal cone to C at x is
NC (x) , {v ∈ Rn | v T (y − x) ≤ 0, for all y ∈ C}.
Lemma 1 (Rockafellar & Wets 1998, Theorem 6.42)
Let C1 and C2 be two closed convex subsets of Rn . If
0 ∈ rint(C1 − C2 ), then
TC1 ∩C2 (x) = TC1 (x) ∩ TC2 (x), ∀ x ∈ C1 ∩ C2 .
A function f : Rn → R is convex if f (λz1 + (1 − λ)z2 ) ≤
λf (z1 ) + (1 − λ)f (z2 ) for any z1 , z2 ∈ C and 0 ≤ λ ≤ 1.
A map F : Rn → Rn is said to be monotone (strictly
monotone) on a set Ω if (x − y)T (F (x) − F (y)) ≥ 0 (> 0)
for all x, y ∈ Ω and x 6= y. A differentiable map F is
monotone if and only if the Jacobian matrix J F (x) (not
necessarily symmetric) is positive semidefinite for each
x (Rockafellar & Wets 1998, Theorem 12.3).
Given a subset Ω ⊆ Rn and a map F : Ω → Rn , the
variational inequality, denoted by VI(Ω, F ), is to find a
vector x ∈ Ω such that

Notations: Denote Rn as the n-dimensional real vector space; denote 1n = (1, ..., 1)T ∈ Rn , and 0n =
(0, ..., 0)T ∈ Rn . Denote col(x1 , ..., xn ) = (xT1 , ..., xTn )T
as the column vector stacked with column vectors
x1 , ..., xn , k · k as the Euclidean norm, and In ∈ Rn×n as
the identity matrix. Denote ∇f as the gradient vector
of a function f and J F as the Jacobian matrix of a map
F . Let C1 ± C2 = {z1 ± z2 | z1 ∈ C1 , z2 ∈ C2 } be the

(y − x)T F (x) ≥ 0,

∀ y ∈ Ω,

and the set of solutions to this problem is denoted by
SOL(Ω, F ) (Facchinei & Pang 2003). When Ω is closed
and convex, the solution of VI(Ω, F ) can be equivalently
reformulated via projection as follows:
x ∈ SOL(Ω, F ) ⇔ x = PΩ (x − F (x)).

2

(3)

Lemma 2 (Facchinei & Pang 2003, Corollary 2.2.5, and
Theorem 2.2.3) Consider VI(Ω, F ), where the set Ω ⊂ Rn
is convex and the map F : Ω → Rn is continuous. The
following two statements hold:

for linear coupled constraints, defined as
X , {x ∈ Rn |

X
i∈V

1) if Ω is compact, then SOL(Ω, F ) is nonempty and
compact;
2) if Ω is closed and F (x) is strictly monotone, then
VI(Ω, F ) has at most one solution.

Ai x i =

X

bi }

i∈V

= {x ∈ Rn | Ax − b = 0l },

(5)

l×ni
for some
, bi ∈ Rl , A = [A1 , ..., AN ], and
P Ai ∈ R
b = i∈V bi .

The following lemma about a regularized gap function
is important for our results.

For such games with coupled constraints, the following
concept of generalized Nash equilibrium is considered.

Lemma 3 (Fukushima 1992) Let F : Rn → Rn be a
differentiable map and H(x) = PΩ (x − F (x)). Define
g : Rn → R as

Definition 1 A strategy profile x∗ is said to be a generalized Nash equilibrium (GNE) of the game if
Ji (x∗i , x∗−i ) ≤ Ji (y, x∗−i ), ∀ y : (y, x∗−i ) ∈ K, i ∈ V. (6)

1
g(x) = (x − H(x))T F (x) − kx − H(x)k2 .
2

Condition (6) means that all players simultaneously take
their own best (feasible) responses at x∗ , where no player
can further decrease its cost function by changing its
decision variable unilaterally.

Then g(x) ≥ 0 is differentiable and its gradient is

Moreover, a strategy profile is said to be a variational
equilibrium, or variational GNE, if it is a solution of
VI(K, F ), where the map F (x) : Rn → Rn is defined as

∇g(x) = F (x) + (J F (x) − In )(x − H(x)).
Furthermore, it is known that the information exchange
among agents can be described by a graph. A graph
with node set V and edge set E is written as G = (V, E)
(Godsil & Royle 2001). If agent i ∈ V can receive information from agent j ∈ V, then (j, i) ∈ E and agent j
belongs to agent i’s neighbor set Ni = {j | (j, i) ∈ E}. G
is said to be undirected if (i, j) ∈ E ⇔ (j, i) ∈ E, and
G is said to be connected if any two nodes in V are connected by a path (a sequence of distinct nodes in which
any consecutive pair of nodes share an edge).

F (x) , col{∇x1 J1 (·, x−1 ), ..., ∇xN JN (·, x−N )}.

(7)

The variational GNEs are well-defined due to the following result.
Lemma 4 (Facchinei & Kanzow 2010, Theorem 3.9) If
K is convex, every solution of the VI(K, F ) is also a GNE.
The following assumption and theorem are associated
with the game and the variational GNEs.
Assumption 1

3

• Smoothness: ∀ i ∈ V, the cost function Ji (xi , x−i ) is
twice continuously differentiable.
• Monotonicity: F (x) in (7) is strictly monotone.
• Feasibility: Ω is compact and convex.
• Constraint qualification: 0 ∈ rint(Ω − X ).

Problem Formulation

Consider an N -player aggregative game with coupled constraints as follows. For i ∈ V , {1, ..., N },
the ith player aims to minimize its cost function
Ji (xi , x−i ) : Ω → R by choosing the local decision variable xi from a local strategy set Ωi ⊂ Rni ,
where x−i , col(x1 , ..., xi−1P
, xi+1 , ..., xN ), Ω ,
Ω1 × · · · × ΩN ⊂ Rn and n =
i∈V ni . The strategy
profile of this game is x , col(x1 , ..., xN ) ∈ Ω. The
aggregation map σ : Rn → Rm , to specify the cost
function as Ji (xi , x−i ) = ϑi (xi , σ(x)) with a function
ϑi : Rni +m → R, is defined as

Theorem 1 Under Assumption 1, the considered game
admits a unique variational GNE.
Proof. According to Lemma 2, the smoothness and feasibility in Assumption 1 guarantee the existence of a
variational GNE, and the monotonicity in Assumption
1 guarantees the uniqueness.

The constraint qualification in Assumption 1 is quite
mild and can be easily verified. In fact, it suffices to check
whether the set K has nonempty relative interior, i.e.,
rint(K) 6= ∅, because in this case,

N

σ(x) ,

1 X
ϕi (xi ),
N i=1

(4)
0 ∈ rint(K − K) ⊆ rint(Ω − X ).

where ϕi : Rni → Rm is a (nonlinear) map for the local
contribution to the aggregation. In addition, the feasible
strategy set of this game is K = Ω ∩ X , where X is a set

In the distributed design for our aggregative game, the
communication topology for each player to exchange information is assumed as follows.

3

where sgn(·) is the sign function, λi (t) ∈ Rl , ζi (t) ∈ Rm .
The initial conditions of algorithm (11) are provided as
follows:

Assumption 2 The (time-varying) graph G(t) is undirected and connected.
Then we formulate our problem.
Problem 1: Design a distributed algorithm to seek the
variational GNE for the considered aggregative game
with coupled constraints.

xi (0) ∈ Ωi ,

• Our formulation is quite similar to that in (Koshal
et al. 2016), but we further consider linear coupled
constraints and study its distributed continuous-time
GNE seeking algorithm.
• Players may not measure the values of the aggregation
directly, in contrast to (Parise et al. 2015).
• Our aggregation function can be nonlinear and the
cost functions can be non-quadratic, which are different from (Paccagnan et al. 2016) and (Ye & Hu 2017).
In addition, J F (x) can be asymmetric 1 , which was
also discussed in (Paccagnan et al. 2016).

Remark 1 The design idea for this continuous-time
algorithm (11) is totally different from that given in
(Koshal et al. 2016) for discrete-time algorithms. Note
that ηi in our algorithm is to estimate the value of aggregation σ(x), while λi is to estimate a dual variable
associated with the coupled constraints. Moreover, our
algorithm is fully distributed and also preserves some
privacy because the information, such as the local cost
functions, decision variables, and coefficients of the
coupled constraints, need not be shared.

Main Results

In this section, we first propose our distributed algorithm
and then analyze its correctness and convergence.
4.1

The solution of (11) (with a discontinuous righthand
side) can be well defined in the Filippov sense, which is
unique and absolutely continuous. For convenience, we
will not mention “in the Filippov sense” in the sequel
when there is no confusion.

Distributed Algorithm

Let α, β, γ > 0 be some constants satisfying α > (N −
1)f¯1 and β > γ(N − 1)f¯2 , where
f¯1 = sup


sup k∇ϕi (xi )k sup ky − zk ,
i∈V xi ∈Ωi
y,z∈Ω

f¯2 = sup sup kAi xi − bi k .
i∈V

ζi (0) = 0m . (12)

To set the parameters α, β, γ in algorithm (11) needs the
values of f¯1 , f¯2 in (8) and (9), which involves additional
distributed calculation as follows: take variables zi with
zi (0) = wi for i ∈ V, and update them by zi (k + 1) =
sup{zi (k), zj (k), j ∈ Ni }; in this way, one can obtain
sup{wi , i ∈ V} within N − 1 steps.

Here are some remarks about our formulation.

4

λi (0) = Ai xi (0) − bi ,

4.2
(8)

Convergence Analysis

Here we give some correctness and convergence analysis
for our proposed algorithm.

(9)

xi ∈Ωi

First of all, we get the following result by extending
(Chen, Cao & Ren 2012, Theorem 3).

For i ∈ V, define the map Gi (·) : Rni +m → Rni as

Lemma 5 Under Assumption 2, if

Gi (xi , yi ) , ∇xi Ji (·, x−i )|σ(x)=yi
(10)
1
= (∇xi ϑi (·, σ) + ∇σ ϑi (xi , ·)T ∇ϕi )|σ=yi .
N

α > (N − 1)f¯,

f¯ ≥ sup kṙi (t)k, ∀ i ∈ V
t∈[0,∞)

then the following system
Then the distributed continuous-time algorithm to solve
Problem 1 is designed as follows:

X

sgn[νj (t) − νi (t)]
 µ̇i (t) = α
j∈Ni (t)


γ T

 ẋi = PΩi (xi − Gi (xi , ηi ) − N Ai λi ) − xi


X



sgn(λj − λi ) + γ(Ai xi − bi )

 λ̇i = β
j∈Ni
X



ζ̇i = α
sgn(ηj − ηi )




j∈Ni


ηi = ζi + ϕi (xi )



νi (t) = µi (t) + ri (t),

(13)

µi (0) = 0

(11)

PN
can make limt→+∞ νi (t) − N1 k=1 rk (t) = 0 for any
i ∈ V with an exponential convergence rate.

A game is a potential game if there is a function P (x)
such that ∇P (x) = F (x) (Ye & Hu 2017). This equation
holds if and only if the Jacobian matrix J F (x) is symmetric
(Facchinei & Pang 2003, Theorem 1.3.1).

Proof. Since G(t) is connected and µi (t) is absolutely
PN
continuous, i=1 µ̇i (t) = 0 for almost all t ≥ 0, which
PN
PN
implies
µi (t) =
i=1
i=1 µi (0) = 0. Therefore,
PN
PN
i=1 νi (t) =
i=1 ri (t). Moreover, it is not hard to
obtain
PN
P
P
1
•
i=1 νi
j∈Ni sgn(νj − νi ) = 2
(i,j)∈E(t) |νi − νj |;
P
1
• for any 1 ≤ k, l ≤ N , |µk −µl | ≤ 2 (i,j)∈E(t) |νi −νj |;

1

4

•

PN

1 T
1
i=1 |νi − N 1 ν| ≤ N
P
N −1
(i,j)∈E(t) |νi − νj |.
2

PN PN
i=1

j=1,j6=i |νi − νj |

Proof. Sufficiency. Suppose (x∗ , λ̄∗ ) ∈ X ∗ × Λ∗ . Then it
follows from the definition of projection operator that
x∗ ∈ Ω. Moreover, x∗ ∈ X since Ax∗ − b = 0. By (3),
γ T ∗
x∗ ∈ SOL(Ω, F (x) + N
A λ̄ ), i.e.,

≤

Define (t) , maxi,j∈V |νi (t) − νj (t)| and
1
1
kν(t) − 11T ν(t)k2 .
2
N
P
Clearly, (t) ≤ 12 (i,j)∈E(t) |νi (t) − νj (t)| and V (t) =
PN
PN
1
1
2
i=1 |νi (t) − N
k=1 rk (t)| ≥ 0. Since V (t) is abso2
lutely continuous, we have that, for almost all t > 0,

(x − x∗ )T (F (x∗ ) +

V (t) ,

V̇ (t) ≤ −

α − (N − 1)f¯
2

X

γ T ∗
A λ̄ ) ≥ 0, ∀ x ∈ Ω.
N

(16)

Because K ⊂ Ω and (x∗ )T AT λ̄∗ = bT λ̄∗ , we have
γ
(x − x∗ )T F (x∗ ) ≥ − (x − x∗ )T AT λ̄∗
N
γ
= − (λ̄∗ )T (Ax − b) = 0, ∀ x ∈ K.
N

|νi (t) − νj (t)|

(i,j)∈E(t)

Thus, {x∗ } = SOL(K, F ), i.e., x∗ is the variational
GNE.

≤ −(α − (N − 1)f¯)(t) ≤ 0.
Because (t) ≥ 0 is absolutely continuous and (α − (N −
R +∞
1)f¯) 0 (t) ≤ V (0) < +∞, (t) → 0 as t → +∞.
Then V (t) ≤ (t) and V̇ (t) ≤ −(α − (N − 1)f¯)V (t) for
almost all t ∈ [t̃, +∞) with a sufficient large t̃, which
implies the conclusion.


Necessity. Suppose that x∗ is the variational GNE. We
claim that there exists some λ̄∗ such that

Next, we give the following result, whose proof is quite
straightforward by Lemma 5.

Otherwise, there is a hyperplane separating the point
−F (x∗ ) and the set {AT λ̄ | λ̄ ∈ Rl } + NΩ (x∗ ). Namely,
there is a vector ω ∈ Rn such that

− F (x∗ ) ∈

Lemma 6 Consider algorithm (11) under Assumption
2. Let σ(x) be in (4) and define


Z t
γ
Ax(0) − b +
(Ax(τ ) − b)dτ . (14)
λ̄(t) =
N
0

ω T F (x∗ ) < 0,
Aω = 0,

xk − x∗
= ω.
k→∞
tk

xk → x∗ , tk → 0, and lim
Consequently,

and let X + × Λ+ be the positive limit set of (x(t), λ̄(t)),
where x(t) is in (11) and λ̄(t) is in (14).
˙
Lemma 7 If lim
ẋ(t) = 0 and lim
λ̄(t)
= 0,
t→+∞

+

+

+

+

(18c)

From (18b) and (18c), ω ∈ TΩ (x∗ ) ∩ TX (x∗ ). Moreover,
with Assumption 1, ω ∈ TΩ∩X (x∗ ) = TK (x∗ ) according
to Lemma 1. Recalling the definition of the tangent cone,
there exist xk ∈ K and tk > 0 such that

Let X ∗ × Λ∗ be the solution set of the following equation
with respect to (x, λ̄)

γ
 0 = PΩ (x − F (x) − AT λ̄) − x
N
,
(15)
 0 = γ (Ax − b)
N

t→+∞

(17)

(18a)
(18b)

dT ω ≤ 0, ∀ d ∈ NΩ (x∗ ).

Then, for any i ∈ V, kηi (t) − σ(x(t))k → 0 and kλi (t) −
λ̄(t)k → 0 exponentially.

then X + × Λ+ ⊆ X ∗ × Λ∗ .

γ T ∗
A λ̄ + NΩ (x∗ ).
N

(xk − x∗ )T F (x∗ )
≥ 0,
k→∞
tk

ω T F (x∗ ) = lim

which contradicts to (18a). It completes the proof.
∗

∗


∗

Clearly, X = {x } from Theorems 1 and 2, where x is
the unique variational GNE under Assumption 1.

+

Proof. If X × Λ 6= ∅, then, for any (x , λ̄ ) ∈ X ×
+
Λ+ , there exists {tq }+∞
q=1 such that limq→+∞ x(tq ) = x
and limq→+∞ λ̄(tq ) = λ̄+ . By taking the limit of tq to
(11) and (14), one obtains according to Lemma 6 that
(x+ , λ̄+ ) is a solution of equation (15). Thus, the conclusion follows.


Finally, it is time to give our convergence result.
Theorem 3 Under Assumptions 1 and 2, system (11)
is stable and converges to the set X ∗ × Λ∗ , that is,

 lim kλi (t) − λ̄(t)k = 0, ∀ i = 1, ..., N
t→+∞
(19)
 lim ||(x(t), λ̄(t)) − PX ∗ ×Λ∗ (x(t), λ̄(t))|| = 0

The next result reveals another property of X ∗ × Λ∗ ,
related to the variational GNE.
Theorem 2 Under Assumption 1, x∗ is the variational
GNE if and only if there exists some λ̄∗ ∈ Rl such that
(x∗ , λ̄∗ ) ∈ X ∗ × Λ∗ .

t→+∞

with λ̄(t) defined in (14).

5

Proof. Since ẋ ∈ TΩ (x), x(t) ∈ Ω for all t ≥ 0. Also, we
have
γ
ẋi (t) = PΩi (xi − Gi (xi , σ(x)) − ATi λ̄(t))
N
− xi (t) + ei (t),

where
T b
b
b
W1 (θ) = (θ∗ − H(θ))
(F (θ) + H(θ)
− θ),
∗ T b ∗
W2 (θ) = (θ − θ ) F (θ ),
∗ T

W3 (θ) = (θ − θ ) (Fb(θ) − Fb(θ∗ )),
b
b
W4 (θ) = (H(θ)
− θ)T J Fb(θ)(H(θ)
− θ).

(20)

γ T
where kei (t)k = kPΩi (xi − Gi (xi , σ(x)) − N
Ai λ̄(t)) −
γ T
PΩi (xi −Gi (xi , ηi )− N Ai λi (t))k ≤ kGi (xi , σ(x)−Gi (xi ,
γ T
Ai (λ̄(t) − λi (t))k ≤ k̄(kσ(x) − ηi (t)k + kλ̄(t) −
ηi )k + k N

W2 (θ) ∈ (x − x∗ )T (−NΩ (x∗ )) ⊆ R+ , ∀ θ ∈ Θ.

θ(t) ,

#

λ̄(t)

, Fb(θ) ,

l

Θ,Ω×R ,

#
"
γ T
F (x) + N
A λ̄
γ
−N
(Ax − b)

,

(25c)
(25d)

(26)

Furthermore, for any θ, θ0 ∈ Θ with x 6= x0 , we obtain

Define
x(t)

(25b)

It follows from (1) that W1 (θ) ≥ 0. Moreover,

λi (t)k), for some k̄ > 0. Let e(t) = col{e1 (t), ..., eN (t)}.
Hence, e(t) vanishes exponentially according to Lemma
6.

"

(25a)

(θ − θ0 )T (Fb(θ) − Fb(θ0 )) = (x − x0 )T (F (x) − F (x0 )) > 0,
(27)
since F (x) is strictly monotone. Then W3 (θ) ≥ 0. Also,
because J Fb(θ) is positive semidefinite, W4 (θ) ≥ 0.
Therefore,
V̇ (t) ≤ −W3 (t) + ê(t).
(28)

(21)

b
H(θ)
, PΘ (θ − Fb(θ)),

Then it follows from (24) that
and let θ∗ ∈ X ∗ × Λ∗ . Consider the following Lyapunov
function

Z +∞
0≤
0

1
1
2
T b
2
b
b
V (t) , (θ − H(θ))
F (θ) − kθ − H(θ)k
+ kθ − θ∗ k .
2
2
(22)
It follows from Lemma 3 that V (t) ≥ 0 and

W3 (t)dt ≤ V (0) − lim sup V (t)
t→+∞
Z +∞
+
ê(t)dt < +∞,
0

Consequently, W3 (t) → 0 as t → +∞, which implies
limt→+∞ x(t) = x∗ . Moreover, lim supt→+∞ V (t) <
+∞, which implies that λ̄(t) is bounded. Therefore,
the positive limit set X + × Λ+ 6= ∅. It follows from
˙
(14) that limt→+∞ λ̄(t)
= Ax∗ − b = 0. Furthermore,
ẋ(t) is uniformly continuous because the trajectory of
(11) is absolutely continuous and the righthand side of
the differential equation with respect to x(t) in (11)
is uniformly continuous in t. Since x(t) is convergent,
limt→+∞ ẋ(t) = 0 by the well-known Barbalat’s lemma.
Thus, (19) holds according to Lemmas 6 and 7.


b
V̇ (t) = (∇θ V )T θ̇(t) = (∇θ V )T (H(θ)
− θ) + ê(t), (23)
where,

γ
ê(t) = [e(t), 0l ]T ∇θ V = e(t)T F (x) + AT λ̄(t)
N
γ
+ (∇F (x) − In ) x − PΩ (x − F (x) − AT λ̄(t))
N


γ
+ AT (Ax − b) + x(t) − x∗ .
N

Remark 2 Our algorithm can be viewed as a distributed
perturbed projected dynamics with the exponentially vanishing perturbation term ei (t) in (20). Although some
projected dynamics without any perturbation was studied, e.g., in (Yi et al. 2016), the analysis for the perturbed
one is novel.

Since x(t) ∈ Ω is bounded, λ̄(t) in (14) satisfies kλ̄(t)k ≤
K1 + K2 t for t ≥ 0 with some constants K1 , K2 > 0.
Also, since e(t) is exponentially convergent, kê(t)k ≤
(K3 + tK4 )e−K5 t for some constants K3 , K4 , K5 > 0,
which further implies

5

Numerical Examples

Two numerical examples are given in this section.

Z +∞
kê(t)kdt < +∞.

(24)

5.1

0

Nash-Cournot Game

Consider a Nash-Cournot game played by N competitive firms to produce a kind of commodity. For i ∈ V =
{1, ..., N }, firm i chooses xi ∈ Ωi as the quantity of
the commodity to produce and has the cost function as
ϑi (xi , σ) = (ci −p(σ))xi , where ci is the production price

On the other hand, after calculations, we have
b
(∇θ V )T (H(θ)
− θ) = −W1 (θ) − W2 (θ) − W3 (θ) − W4 (θ),

6

Fig. 1. The trajectories of the strategy profile of Nash–
Cournot game without (the upper one) and with (the lower
one) the linear coupled constraint.

Fig. 2. The trajectories of the strategy profile of demand
response management game without (the upper one) and
with (the lower one) the linear coupled constraint.

65, [r4 , r̄4 ] = [52, 78];

of firm i, and p = d − N σ(x) is the market price
P determined by the aggregation function σ(x) = N1 j∈V x2j .
Our numerical setting is as follows.

The NE of the game has been calculated in (Ye & Hu
2017) as x∗ = [45, 46.4, 51.3, 56.2, 61.1]T . Note that the
total energy consumption at this
P5 NE∗ may
P5be too far
from the normal value because i=1 xi = i=1 χi − 40.
Here,
P5 we further
P5 impose the following linear constraint
x
=
i=1 i
i=1 χi − 25. The communication graph is
randomly generated and the parameters in our algorithm
are given as α = 30, β = 100, and γ = 2. Then the GNE
is obtained as x∗ = [45.2, 50.1, 55, 59.9, 64.8]T . Figure 2
shows the convergence to the NE (the upper one) and
GNE (the lower one), which again illustrates our algorithm.

(i) N = 20 and V = {1, ..., 20}.
(ii) For each firm i ∈ V, Ωi = [0, 20], ci = 10+20(i−1)
and d = 1200.
(iii) Firms from i = 1 to i = 10 share a scare resource
P10
as i=1 xi = 20.
(iv) the communication graph G(t) is time-varying and
randomly generated.
(v) Parameter setting of our algorithm is α = 20, β =
400 and γ = 20.
Figure 1 shows the convergence to the NE (the upper
one) and GNE (the lower one), which illustrates the effectiveness of our algorithm.
5.2

χ5 = 70, [r5 , r̄5 ] = [56, 84].

6

Conclusions

In this paper, aggregative games with linear coupled constraints were considered and a distributed continuoustime projection-based algorithm was proposed for the
GNE seeking. The correctness and convergence of the
proposed non-smooth algorithm were proved by virtue
of variational inequalities and Lyapunov functions, and
moreover, two numerical examples were given for illustration.

Demand Response Management

Consider N electricity users with the demand of energy
consumption. For each i ∈ V, xi ∈ [ri , r̄i ] is the energy
consumption of the ith user and Ci (xi , σ(x)) is the cost
function in the following form
Ci (xi , σ(x)) = ki (xi − χi )2 + P (σ(x))xi ,

References

where ki is constant and χi is the nominal value of energy
consumption for iP
= 1, ..., N , with P (σ(x)) = aN σ(x) +
p0 and σ(x) = N1 i∈V xi . We adopt the same numerical
setting as given in (Ye & Hu 2017) as follows:

Altman, E. & Solan, E. (2009). Constrained games: the impact of
the attitude to adversary’s constraints, IEEE Transactions
on Automatic Control 54(10): 2435–2440.
Ardagna, D., Panicucci, B. & Passacantando, M. (2013).
Generalized Nash equilibria for the service provisioning
problem in cloud systems, IEEE Transactions on Services
Computing 6(4): 429–442.

(i) N = 5, ki = 1, a = 0.04, p0 = 5.
(ii) χ1 = 50, [r1 , r̄1 ] = [45, 55]; χ2 = 55, [r2 , r̄2 ] =
[44, 66]; χ3 = 60, [r3 , r̄3 ] = [46, 72]; χ4 =

7

Arslan, G., Demirkol, M. F. & Yueksel, S. (2015). On games
with coupled constraints, IEEE Transactions on Automatic
Control 60(2): 358–372.

Salehisadaghiani, F. & Pavel, L. (2016). Distributed Nash
equilibrium seeking: a gossip-based algorithm, Automatica
72: 209–216.

Barrera, J. & Garcia, A. (2015).
Dynamic incentives for
congestion control, IEEE Transactions on Automatic Control
60(2): 299–310.

Shi, G., Johansson, K. H. & Hong, Y. (2013). Reaching an optimal
consensus: dynamical systems that compute intersections
of convex sets, IEEE Transactions on Automatic Control
58(3): 610–622.

Chen, F., Cao, Y. & Ren, W. (2012). Distributed average
tracking of multiple time-varying reference signals with
bounded derivatives, IEEE Transactions on Automatic
Control 57(12): 3169–3174.

Swenson, B., Kar, S. & Xavier, J. (2015). Empirical centroid
fictitious play: an approach for distributed learning in
multi-agent games, IEEE Transactions on Signal Processing
63(15): 3888–3901.

Cornes, R. (2016).
Aggregative environmental games,
Environmental & Resource Economics 63(2): 339–365.

Ye, M. & Hu, G. (2017). Game design and analysis for pricebased demand response: an aggregate game approach, IEEE
Transactions on Cybernetics 47(3): 720–730.

Cornes, R. & Hartley, R. (2012). Fully aggregative games,
Economics Letters 116(3): 631–633.

Yi, P., Hong, Y. & Liu, F. (2016). Initialization-free distributed
algorithms for optimal resource allocation with feasibility
constraints and its application to economic dispatch of power
systems, Automatica 74(12): 259–269.

Facchinei, F. & Kanzow, C. (2010). Generalized Nash equilibrium
problems, Annals of Operations Research 175(1): 177–211.
Facchinei, F. & Pang, J. (2003). Finite-Dimensional Variational
Inequalities and Complementarity Problems, SpringerVerlag, New York.
Fukushima, M. (1992). Equivalent differentiable optimization
problems and descent methods for asymmetric variational
inequality problems, Mathematical Programming 53: 99–110.
Godsil, C. & Royle, G. F. (2001). Algebraic Graph Theory, Vol.
207 of Graduate Texts in Mathematics, Springer-Verlag, New
York.
Jensen, M. K. (2010).
Aggregative games and best-reply
potentials, Economic Theory 43(1): 45–66.
Kia, S. S., Cortés, J. & Martı́nez, S. (2015). Distributed convex
optimization via continuous-time coordination algorithms
with discrete-time communication, Automatica 55: 254–264.
Koshal, J., Nedić, A. & Shanbhag, U. V. (2016). Distributed
algorithms for aggregative games on graphs, Operations
Research 63(3): 680–704.
Li, N. & Marden, J. R. (2013). Designing games for distributed
optimization, IEEE Journal of Selected Topics in Signal
Processing 7(2): 230–242.
Lou, Y., Hong, Y. H., Xie, L., Shi, G. & Johansson, K. H. (2016).
Nash equilibrium computation in subnetwork zero-sum
games with switching communications, IEEE Transactions
on Automatic Control 61(10): 2920–2935.
Nedić, A. & Ozdaglar, A. (2009). Distributed subgradient
methods for multi-agent optimization, IEEE Transactions
on Automatic Control 54(1): 48–61.
Paccagnan, D., Gentile, B., Parise, F., Kamgarpour, M. &
Lygeros, J. (2016). Distributed computation of generalized
Nash equilibria in quadratic aggregative games with affine
coupling constraints, The 55th IEEE Conference on Decision
and Control (CDC), IEEE, pp. 6123–6128.
Pang, J., Scutari, G., Facchinei, F. & Wang, C. (2008).
Distributed power allocation with rate constraints in
Gaussian parallel interference channels, IEEE Transactions
on Information Theory 54(8): 3471–3489.
Parise, F., Gentile, B., Grammatico, S. & Lygeros, J. (2015).
Network aggregative games: distributed convergence to Nash
equilibria, The 54th IEEE Conference on Decision and
Control (CDC), pp. 2295–2300.
Pavel, L. (2007). An extension of duality to a game-theoretic
framework, Automatica 43(2): 226–237.
Rockafellar, R. T. & Wets, R. J. B. (1998). Variational
Analysis, Vol. 317 of Grundlehren Der Mathematischen
Wissenschaften, Springer-Verlag.

8

