A Passivity-Based Approach to Nash Equilibrium
Seeking over Networks

arXiv:1705.02424v1 [math.OC] 6 May 2017

Dian Gadjov and Lacra Pavel

Abstract—In this paper we consider the problem of distributed
Nash equilibrium (NE) seeking over networks, a setting in
which players have limited local information. We start from a
continuous-time gradient-play dynamics that converges to an NE
under strict monotonicity of the pseudo-gradient and assumes
perfect information, i.e., instantaneous all-to-all player communication. We consider how to modify this gradient-play dynamics in
the case of partial, or networked information between players. We
propose an augmented gradient-play dynamics with correction
in which players communicate locally only with their neighbours
to compute an estimate of the other players’ actions. We derive
the new dynamics based on the reformulation as a multi-agent
coordination problem over an undirected graph. We exploit
incremental passivity properties and show that a synchronizing,
distributed Laplacian feedback can be designed using relative
estimates of the neighbours. Under a strict monotonicity property
of the pseudo-gradient, we show that the augmented gradientplay dynamics converges to consensus on the NE of the game.
We further discuss two cases that highlight the tradeoff between
properties of the game and the communication graph.

I. I NTRODUCTION
We consider distributed Nash equilibrium (NE) seeking over
networks, where players have limited local information, over a
communication network. This is a research topic of recent interest, [1], [2], [3], due to many networked scenarios in which
such problems arise such as in wireless communication [4],
[5], [6], optical networks [7], [8], [9], distributed constrained
convex optimization [10], [11], noncooperative flow control
problems [12], [13], etc.
We propose a new continuous-time dynamics for a general
class of N-player games and prove its convergence to NE
over a connected graph. Our scheme is derived based on
reformulating the problem as a multi-agent coordination problem between the players and leveraging passivity properties.
Specifically, we endow each player (agent) with an auxiliary
state variable that provides an estimate of all other players’
actions. For each agent we combine its own gradient-type
dynamics with an integrator-type auxiliary dynamics, driven
by some control signal. We design the control signal for each
individual player, based on the relative output feedback from
its neighbours, such that these auxiliary state variables agree
one with another. The resulting player’s dynamics has two
components: the action component composed of a gradient
term (enforcing the move towards minimizing its own cost)
and a consensus term, and the estimate component with a
This work was supported by an NSERC Discovery Grant.
D. Gadjov and L. Pavel are with the Department of Electrical
and Computer Engineering, University of Toronto, Toronto, ON,
M5S
3G4,
Canada
dian.gadjov@mail.utoronto.ca,

pavel@control.utoronto.ca

consensus term. We call this new dynamics an augmented
gradient-play dynamics with correction and estimation. We
prove it converges to consensus on the NE of the game, under
a monotonicity property of the extended pseudo-gradient.
Literature review. Our work is related to the literature of
NE seeking in games over networks. Existing results are
almost exclusively developed in discrete-time. The problem
of NE seeking under networked communication is considered
in [14], [15], specifically for the special class of aggregative
games, where each agent’s cost function is coupled to other
players’ actions through a single, aggregative variable. In
[16], this approach is generalized to a larger class of coupled
games: a gossip-based discrete-time algorithm is proposed
and convergence was shown for diminishing step-sizes. Very
recently, discrete-time ADMM-type algorithms with constant
step-sizes have been proposed and convergence proved under
co-coercivity of the extended pseudo-gradient, [17], [18].
In continuous-time, gradient-based dynamics for NE computation have been used since the work Arrow, [19], [20], [21],
[22]. Over networks, gradient-based algorithms are designed in
[11] based on information from only a set of local neighbouring agents for games with local utility functions (proved to be
state-based potential games). Continuous-time distributed NE
seeking dynamics are proposed for a two-network zero-sum
game in [23]. Key assumptions are the additive decomposition
of the common objective function as well as other structural
assumptions. Based on the max-min formulation, the dynamics
takes the form of a saddle-point dynamics, [19], distributed
over the agents of each of the two networks, inspired by the
optimization framework of [10].
In this paper we consider a general class of N-player
games, where players have limited local information about the
others’ actions over a communication network. Our work is
also related to the distributed optimization framework in [10].
However there are several differences between [10] or [23]
and our work. Beside the summable structure of the common
cost function, in [10] a critical structural assumption is the fact
that each agent optimizes its cost function over the full argument. Then, when an augmented (lifted) space of actions and
estimates is considered in the networked communication case,
a lifted cost function is obtained which can be decomposed
as a sum of separable cost functions, individually convex in
their full argument. This leads to distributed algorithms, under
strict convexity of the individual cost functions with respect to
the full argument. In a strategic game context, the individual
convexity properties with respect to the full argument are too
restrictive unless the game is separable to start with. While the
game setting has an inherent distributed structure (since each

player optimizes its own cost function), individual (playerby-player) optimization) is over its own action. In contrast to
distributed optimization, each player’s individual action is only
part of the full action profile and its cost function is coupled to
its opponents’ actions, which are under their decision. This key
differentiating structural aspect between games and distributed
optimization presents technical challenges.
In this work, we also consider an augmented space to
deal with the networked communication case, of actions
and estimates of others’ actions. However, the difficulty is
that we do not have an additive decomposition to exploit,
and each player only controls/optimizes a part of the full
argument on which its own cost function depends on. Our main
approach is to highlight and exploit passivity properties of the
game (pseudo-gradient), gradient-based algorithm/dynamics
and network (Laplacian). A typical assumption in games is
not individual gradient monotonicity with respect to the full
argument, but rather monotonicity of the pseudo-gradient. The
corresponding game assumption we use in the networked
communication case, is monotonicity of the extended pseudogradient, which is equivalent to incremental passivity.
Contributions. We consider a general class of N-player
games and develop of a new continuous-time dynamics for
NE seeking dynamics under networked information. Our approach is based on reformulating the problem as a multiagent coordination problem and exploiting basic incremental
passivity properties of the pseudo-gradient map. To the best
of our knowledge such an approach has not been proposed
before. Our contributions are three-fold. First, we show that
under strict monotonicity of the extended pseudo-gradient,
the proposed new dynamics converges over any connected
graph, unlike [17], [18]. Our scheme is different from [16],
due to an extra correction term on the actions’ dynamics
that arises naturally from the passivity-based design. This
term is in fact critical to prove convergence on a single
timescale. Essentially, players perform simultaneous consensus
of estimates and player-by-player optimization.
Secondly, our passivity-based approach highlights the tradeoff between properties of the game and those of the communication graph. Under a weaker Lipschitz continuity assumption
of the extended pseudo-gradient, we show that the new dynamics converges over any sufficiently connected graph. Key
is the fact that the Laplacian contribution (or excess passivity)
can be used to balance the other terms that are dependent on
the game properties. Thirdly, we relax the connectivity bound
on the graph, based on a time-scale separation argument. This
is achieved by modifying the dynamics of the estimates such
that the system approaches quickly the consensus subspace.
The paper is organized as follows. Section II gives the
preliminary background. Section III formulates the noncooperative game and basic assumptions. Section IV presents the
distributed NE seeking dynamics and analyzes its equilibrium
points. Section V analyzes the convergence of the proposed
dynamics over a connected graph under various assumptions.
Section VI considers the case of compact action spaces, where
projection dynamics are proposed and analyzed. Numerical
examples are given in Section VII and conclusions in Section
VIII.

II. P RELIMINARIES
Notations. Given a vector x ∈ Rn , xT denotes its transpose.
Let xT y denote the Euclidean inner product of x, y ∈ Rn
and kxk the Euclidean norm. Let A ⊗ B denote the Kronecker product of matrices A and B. The all ones vector
is 1n = [1, . . . , 1]T ∈ Rn , and the all zeros vector is
0n = [0, . . . , 0]T ∈ Rn . diag(A1 , . . . , An ) denotes the blockdiagonal matrix with Ai on its diagonal. Given a matrix
M ∈ Rp×q , N ull(M ) = {x ∈ Rq |M x = 0} and
Range(M ) = {y ∈ Rp |(∃x ∈ Rq ) y = M x}. A function
Φ : Rn → Rn is monotone if (x − y)T (Φ(x) − Φ(y)) ≥ 0,
for all x, y ∈ Rn , and strictly monotone if the inequality is
strict when x 6= y. Φ is strongly monotone if there exists
µ > 0 such that (x − y)T (Φ(x) − Φ(y)) ≥ µkx − yk2 , for
all x, y ∈ Rn . For a differentiable function V : Rn → R,
n
∇V (x) = ∂V
∂x (x) ∈ R denotes its gradient. V is convex,
strictly, strongly convex if and only if its gradient ∇V is monotone, strictly, strongly monotone. Monotonicity properties play
in variational inequalities the same role as convexity plays in
optimization.

A. Projections
Given a closed, convex set Ω ⊂ Rn , let the interior,
boundary and closure of Ω be denoted by intΩ, ∂Ω and Ω,
respectively. The normal cone of Ω at a point x ∈ Ω is defined
as NΩ (x) = {y ∈ Rn |y T (x0 − x) ≤ 0, ∀x0 ∈ Ω}. The tangent
S
cone of Ω at x ∈ Ω is given as TΩ (x) = δ>0 1δ (Ω − x). The
projection operator of a point x ∈ Rn to the set Ω is given by
the point PΩ (x) ∈ Ω such that kx − PΩ (x)k ≤ kx − x0 k, for
all x0 ∈ Ω, or PΩ (x) = argminx0 ∈Ω kx − x0 k. The projection
operator of a vector v ∈ Rn at a point x ∈ Ω with respect to Ω
is ΠΩ (x, v) = lim PΩ (x+δv)−x
. Note that kΠΩ (x, v)k ≤ kvk.
δ
δ→0+

Given x ∈ ∂Ω let n(x) denote the set of outward unit normals
to Ω at x, n(x) = {y | y ∈ NΩ (x), kyk = 1}. By Lemma 2.1
in [24], if x ∈ intΩ, then ΠΩ (x, v) = v, while if x ∈ ∂Ω, then
ΠΩ (x, v) = v − β(x) n∗ (x)

(1)

where n∗ (x) = argmax v T n and β(x) = max{0, v T n∗ (x)}.
n∈n(x)

Note that if v ∈ TΩ (x) for some x ∈ ∂Ω, then sup v T n ≤ 0
n∈n(x)

hence β(x) = 0 and no projection needs to be performed. The
operator ΠΩ (x, v) is equivalent to the projection of the vector
v onto the tangent cone TΩ (x) at x, ΠΩ (x, v) = PTΩ (x) (v).
A set C ⊆ Rn is a cone if for any c ∈ C, γc ∈ C for
every γ > 0. The polar cone of a convex cone C is given by
C ◦ = {y ∈ Rn | y T c ≤ 0, ∀c ∈ C}.
Lemma 1 (Moreau’s Decomposition Theorem III.3.2.5, [25]).
Let C ⊆ Rn and C ◦ ⊆ Rn be a closed convex cone and its
polar cone, and let v ∈ Rn . Then the following are equivalent:
(i) vC = PC (v) and vC ◦ = PC ◦ (v).
T
(ii) vC ∈ C, vC ◦ ∈ C ◦ , v = vC + vC ◦ , and vC
vC ◦ = 0.
Notice that NΩ (x) is a convex cone and the tangent cone is
its polar cone, i.e., NΩ (x) = (TΩ (x))◦ , (NΩ (x))◦ = TΩ (x).

By Lemma 1, for any x ∈ Ω, any vector v ∈ Rn can be decomposed into tangent vTΩ ∈ TΩ (x) and normal components,
vNΩ ∈ NΩ (x),
v = vTΩ + vNΩ

(2)

with vTΩ = PTΩ (x) (v) = ΠΩ (x, v), vNΩ = PNΩ (x) (v).
B. Graph theory

in comparing any two trajectories of Σ, the property is called
incremental passivity, [30].
Definition 2. System Σ (3) is incrementally passive if there
exists a C 1 , regular, positive semi-definite storage function
V : Rn × Rn → R such that for any two inputs u, u0 and
any two solutions x, x0 corresponding to these inputs, the
respective outputs y, y 0 satisfy
V̇ (x, x0 ) ≤ (y − y 0 )T (u − u0 )

The following are from [26]. An undirected graph Gc is
a pair Gc = (I, E) with I = {1, . . . , N } the vertex set and
E ⊆ I×I the edge set such that for i, j ∈ I, if (i, j) ∈ E, then
(j, i) ∈ E. The degree of vertex i, deg(i), is the number of
edges connected to i. A path in a graph is a sequence of edges
which connects a sequence of vertices. A graph is connected
if there is a path between every pair of vertices. In this paper
we associate a vertex with a player/agent. An edge between
agents i, j ∈ I exists if agents i and j exchange information.
Let Ni ⊂ I denote the set of neighbours of player i. The
Laplacian matrix L ∈ RN ×N describes the connectivity of the
graph Gc , with [L]ij = |Ni |, if i = j, [L]ij = −1, if j ∈ Ni
and 0 otherwise. When Gc is an undirected and connected
graph, 0 is a simple eigenvalue of L, L1N = 0N , and all other
eigenvalues positive. Let the eigenvalues of L in ascending
order be 0 < λ2 ≤ . . . ≤ λN , then
min
xT Lx =
λ2 kxk22 , max xT Lx = λN kxk22 .

x6=0, 1T
N x=0

x6=0

C. Equilibrium Independent and Incremental Passivity
The following are from [27], [28], [29], [30]. Consider Σ
(
ẋ = f (x, u),
Σ:
(3)
y = h(x, u),
with x ∈ Rn , u ∈ Rq and y ∈ Rq , f locally Lipschitz and h
continuous. Consider a differentiable function V : Rn → R.
The time derivative of V along solutions of (3) is denoted
as V̇ (x) = ∇T V (x) f (x, u) or just V̇ . Let u, x, y be an
equilibrium condition, such that 0 = f (x, u), y = h(x, u).
Assume ∃U ⊂ R and a continuous function kx (u) such that
for any constant u ∈ U , f (kx (u), u) = 0. The continuous
function ky (u) = h(kx (u), u) is the equilibrium input-output
map. Equilibrium independent passivity (EIP) requires Σ to
be passive independent of the equilibrium point.
Definition 1. System Σ (3) is Equilibrium Independent Passive
(EIP) if it is passive with respect to u and y; that is for
every u ∈ U there exists a differentiable, positive semi-definite
storage function V : Rn → R such that V (x) = 0 and, for all
u ∈ R q , x ∈ Rn ,
V̇ (x) ≤ (y − y)T (u − u)
A slight refinement to the EIP definition can be made to
handle the case where ky (u) is not a function but is a map. An
EIP system with a map ky (u) is called maximal EIP (MEIP)
when ky (u) is maximally monotone, e.g. an integrator, [28].
The parallel interconnection and the feedback interconnection
of EIP systems results in a EIP system. When passivity holds

where V̇ = ∇Tx V (x, x0 )f (x, u) + ∇Tx0 V (x, x0 )f (x0 , u0 ).
When u0 , x0 , y 0 are constant (equilibrium conditions), this
recovers EIP definition. When system Σ is just a static
map, incrementally passivity reduces to monotonicity. A static
function y = Φ(u) is EIP if and only if it is incrementally
passive, or equivalently, it is monotone. Monotonicity plays
an important role in optimization and variational inequalities
while passivity plays as critical a role in dynamical systems.
III. P ROBLEM S TATEMENT
A. Game Formulation
Consider a set I = {1, . . . , N } of N players (agents)
involved in a game. The information sharing between them
is described by an undirected graph Gc = (I, E) or Gc .
Assumption 1. The communication graph Gc is connected.
Each player i ∈ I controls its action xiQ∈ Ωi , where
ni
n
Ωi ⊆ R
P . The action set of all players is Ω = i∈I Ωi ⊆ R ,
n =
i∈I ni . Let x = (xi , x−i ) ∈ Ω denoteQall agents’
action profile or N -tuple, where x−i ∈ Ω−i = j∈I\{i} Ωj
is the (N − 1)-tuple of all agents’ actions except agent
i’s. Alternatively, x is represented as a stacked vector x =
[xT1 . . . xTN ]T ∈ Ω ⊆ Rn . Each player (agent) i aims to
minimize its own cost function Ji (xi , x−i ), Ji : Ω → R,
which depends on possibly all other players’ actions. Let the
game thus defined be denoted by G(I, Ji , Ωi ).
Definition 3. Given a game G(I, Ji , Ωi ), an action profile
x∗ = (x∗i , x∗−i ) ∈ Ω is a Nash Equilibrium (NE) of G if
(∀i ∈ I)(∀yi ∈ Ωi ) Ji (x∗i , x∗−i ) ≤ Ji (yi , x∗−i )
At a Nash Equilibrium no agent has any incentive to
unilaterally deviate from its action. In the following we use
one of the following two basic convexity and smoothness
assumptions, which ensure the existence of a pure NE.
Assumption 2. (i) For every i ∈ I, Ωi = Rni , the cost
function Ji : Ω → R is C 2 in its arguments, strictly
convex and radially unbounded in xi , for every x−i ∈
Ω−i .
(ii) For every i ∈ I, Ωi is a non empty, convex and compact
subset of Rni and the cost function Ji : Ω → R is C 1
in its arguments and (strictly) convex in xi , for every
x−i ∈ Ω−i .
Under Assumption 2(i) from Corollary 4.2 in [31] it follows
that a pure NE x∗ exists. Moreover, an NE satisfies
∇i Ji (x∗i , x∗−i ) = 0, (∀i ∈ I) or F (x∗ ) = 0

(4)

∂Ji
(xi , x−i ) ∈ Rni , is the gradient
where ∇i Ji (xi , x−i ) = ∂x
i
of agent i’s cost function Ji (xi , x−i ) with respect to its own
action xi and F : Ω → Rn is the pseudo-gradient defined by
stacking all agents’ partial gradients,
T
F (x) = [∇1 J1T (x), . . . , ∇N JN
(x)]T

(5)

Under Assumption 2(ii) it follows from Theorem 4.3 in [31]
that a pure NE exists, based on Brower’s fixed point theorem.
Under just convexity of Ji with respect to xi , existence of
an NE follows based on a Kakutani’s fixed point theorem.
Moreover a Nash equilibrium (NE) x∗ ∈ Ω satisfies the
variational inequality (VI) (cf. Proposition 1.4.2, [32]),
(x − x∗ )T F (x∗ ) ≥ 0

∀x ∈ Ω

(6)

and projected gradient methods need be used, [32]. Additionally (6) can be written as −F (x∗ )T (x − x∗ ) ≤ 0 and from the
definition of the normal cone,
−F (x∗ ) ∈ NΩ (x∗ )

B. Gradient Dynamics with Perfect information
In a game of perfect information, under Assumption 2(i), a
typical gradient-based dynamics, [20], [21], [22], [32], can be
used for each player i
Pi : ẋi = −∇i Ji (xi , x−i ),

∀i ∈ I

(8)

or, P : ẋ = −F (x), the overall system of all the agents’
dynamics stacked together. Assumption 2(i) ensures existence
and uniqueness of solutions of (8). Note that (8) requires
all-to-all instantaneous information exchange between players
or over a complete communication graph. Convergence of
(8) is typically shown under strict (strong) monotonicity on
the pseudo-gradient F , [32], [21], or under strict diagonal
dominance of its Jacobian evaluated at x∗ , [1]. We provide
a passivity interpretation. The gradient dynamics P (8) is the
feedback interconnection between a bank of N integrators
Σ and the static pseudo-gradient map F (·), Figure 1. Σ is
u
−

(
ẋ = u
Σ:
y=x

y

(7)

Next we state typical assumptions on the pseudo-gradient.

F (·)

n

Assumption 3. (i) The pseudo-gradient F : Ω → R is
strictly monotone, (x−x0 )T (F (x)−F (x0 )) > 0, ∀x 6= x0 .
(ii) The pseudo-gradient F : Ω → Rn is strongly monotone,
(x − x0 )T (F (x) − F (x0 )) ≥ µkx − x0 k2 , ∀x, x0 ∈ Ω,
for µ > 0, and Lipschitz continuous, kF (x) − F (x0 )k ≤
θkx − x0 k, ∀x, x0 ∈ Ω, where θ > 0.
Under Assumption 3(i) or 3(ii), the game has a unique NE,
(cf. Theorem 3 in [33]).
The above setting refers to players’ strategic interactions,
but it does not specify what knowledge or information each
player has. Since Ji depends on all players’ actions, an introspective calculation of an NE requires complete information
where each player knows the cost functions and strategies
of all other players, see Definition 3 and (4). A game with
incomplete information refers to players not fully knowing the
cost functions or strategies of the others, [34]. Throughout
the paper, we assume Ji is known by player i only. In a
game with incomplete but perfect information, each agent has
knowledge of the actions of all other players, x−i . We refer
to the case when players are not able to observe the actions of
all the other players, as a game with incomplete and imperfect
or partial information. This is the setting we consider in
this paper: we assume players can communicate only locally,
with their neighbours. Our goal is to derive a dynamics for
seeking an NE in the incomplete, partial information case,
over a communication graph Gc . We review first the case of
perfect information, and treat the case of partial or networked
information in the following sections. In the first part of the
paper, for simplicity of the arguments, we consider Ωi = Rni
and Assumption 2(i). We consider compact action sets and
treat the case of projected dynamics, under Assumption 2(ii),
in Section VI.

Fig. 1. Gradient Dynamics (8) as Feedback Interconnection of two EIP

MEIP with storage function V (x) = 12 kx − xk2 , while F (·)
is static and under Assumption 3(i) is incrementally passive
(EIP). Hence their interconnection is also EIP and asymptotic
stability can be shown using the same storage function.
Lemma 2. Consider a game G(I, Ji , Ωi ) in the perfect information case, under Assumptions 2(i). Then, the equilibrium
point x̄ of the gradient dynamics, (8) is the NE of the game
x∗ and, under Assumption 3(i), is globally asymptotically.
Alternatively, under 3(ii) x∗ is exponentially stable, hence the
solutions of (8) converge exponentially to the NE of the game,
x∗ .
Proof. At an equilibrium x, of (8), F (x) = 0, hence by
(4), x̄ = x∗ , the NE of G(I, Ji , Ωi ). Consider the quadratic
Lyapunov function V : Ω → R, V (x) = 21 kx − x̄k2 . Along
(8) using F (x) = 0, V̇ (x) = −(x − x)T (F (x) − F (x)) < 0,
for all x 6= x, by Assumption 3(i). Hence V̇ (x) ≤ 0 and
V̇ (x) = 0 only if x = x = x∗ . Since V is radially
unbounded, the conclusion follows by LaSalle’s theorem [35].
Under Assumption 3(ii), V̇ (x) ≤ −µkx − xk2 , ∀x and global
exponential stability follows immediately.
IV. NE S EEKING DYNAMICS OVER A G RAPH
In this section we consider the following question: how can
we modify the gradient dynamics (8) such that it converges to
NE in a networked information setting, over some connected
communication graph Gc ?
We propose a new augmented gradient dynamics, derived
based on the reformulation as a multi-agent agreement problem between the players. We endow each player (agent) with

an auxiliary state that provides an estimate of all other players’
actions. We design a new signal for each player, based on the
relative feedback from its neighbours, such that these estimates
agree one with another.
Thus assume that player (agent) i maintains an estimate
vector xi = [(xi1 )T , . . . , (xiN )T ]T ∈ Ω where xij is player i’s
estimate of player j’s action and xii = xi is player i’s actual
action. xi−i represents player i’s estimate vector without its
own action, xii . All agents’ vectors are
Q stacked into a single
vector x = [(x1 )T , . . . , (xN )T ]T ∈ i∈IQΩ = ΩN = RN n .
Note that the state space is now ΩN = i∈I Ω = RN n . In
the enlarged space the estimate components will be different
initially, but in the limit all players estimate vectors should
be in consensus. We modify the gradient dynamics such that
player i updates xii to reduce its own cost function and updates
xi−i to reach a consensus with the other players. Let each
player combine its gradient-type dynamics with an integratortype auxiliary dynamics, driven by some control signal,
# "
#
"
i

 ẋi = −∇i Ji (xi , x−i ) + B i u
i
ei :
Σ
(9)
ẋi−i
0


i T i
yi = (B ) x
where B i is a full rank n × n matrix. For each player, ui ∈ Rn
is to be designed based on the relative output feedback from
its neighbours, such that xi = xj , for all i, j, and converge to
the NE x∗ .
Thus we have reformulated the design of NE dynamics over
Gc as a multi-agent agreement problem. We note that agent
dynamics (9) are heterogenous, separable, but do not satisfy
an individual passivity property as typically assumed in multiagent literature, e.g. [29], [36]. We show next that a Laplaciantype feedback can be designed under strict incremental passivity of the pseudo-gradient.
e i and the overall
To proceed, we first analyze properties of Σ
e Write Σ
e i (9) in a compact form
agents’ dynamics Σ.
(
ẋi = −RTi ∇i Ji (xi ) + B i ui
e
Σi :
(10)
yi = (B i )T xi
where
Ri = [0ni ×n<i Ini 0ni ×n>i ]
(11)
P
P
and n<i = j<i i,j∈I nj , n>i = j>i i,j∈I nj .
Thus RTi ∈ Rn×ni aligns the gradient to the action
component in ẋi . From (10), with x = [(x1 )T , . . . , (xN )T ]T ,
u = [uT1 , . . . , uTN ]T ∈ RN n , the overall agents’ dynamics
e can be written in stacked form as
denoted by Σ
(
ẋ = −RT F(x) + Bu
e
Σ:
(12)
y = BT x
where R = diag(R1 , . . . , RN ), B = diag(B 1 , . . . , B N ) and
T
F(x) = [∇1 J1T (x1 ), . . . , ∇N JN
(xN )]T

(13)

is the continuous extension of the pseudo-gradient F , (5) to the
augmented space, F(x) : ΩN → Rn . Note that F(1N ⊗ x) =
F (x). In the rest of the paper we consider one of the following
two assumptions on the extended F.

Assumption 4. (i) The extended pseudo-gradient F is
monotone, (x − x0 )T (F(x) − F(x0 )) ≥ 0, ∀x, x0 ∈ ΩN .
(ii) The extended pseudo-gradient F is Lipschitz continuous,
kF(x) − F(x0 )k ≤ θkx − x0 k, ∀x, x0 ∈ ΩN where θ > 0.
Remark 1. We compare this assumption to similar ones
used in distributed optimization and in multi-agent coordination control, respectively. First, note that Assumption 4(i)
on the extended pseudo-gradient F holds under individual
joint convexity of each Ji with respect to the full argument.
In distributed optimization problems, each objective function
is assumed to be strictly (strongly) jointly convex in the full
vector x and its gradient to be Lipschitz continuous, e.g. [10].
Similarly, in multi-agent coordination control, it is standard
to assume that individual agent dynamics are separable and
strictly (strongly) incrementally passive, e.g. [29]. However,
in a game context the individual joint convexity of Ji with
respect to the full argument is too restrictive, unless we have
a trivial game with separable cost functions. In general, Ji
is coupled to other players’ actions while each player has
under its control only its own action. This is a key difference
versus distributed optimization or multi-agent coordination,
one which introduces technical challenges. However, we show
that under the monotonicity Assumption 4(i) on F, the overall
e (12) is incrementally passive, hence EIP. Based on this, we
Σ
design a new dynamics which converges over any connected
Gc (Theorem 1). Under the weaker Lipschitz Assumption
4(ii) on F and Assumption 3(ii) on F , we show that the
new dynamics converges over any sufficiently connected Gc
(Theorem 2). We also note that Assumption 4(i) is similar to
those used in [17], [18], while Assumption 4(ii) is weaker.
Assumption 4(i) is the extension of Assumption 3(i) to the
augmented space, for local communication over the connected
graph Gc . The weaker Assumption 4(ii) on F, is the extension
of Lipschitz continuity of F in Assumption 3(ii). We also note
that these assumptions could be relaxed to hold only locally
around x∗ in which case all results become local.
e (12),
Lemma 3. Under Assumption 4(i), the overall system Σ,
is incrementally passive, hence EIP.
Proof. Consider two inputs u, u0 and let x, x0 , y, y0 be the
e (12). Let the storage function be
trajectories and outputs of Σ
1
0 2
0
V (x, x ) = 2 kx − x k . Then, along solutions of (12),


V̇ = −(x − x0 )T RT (F(x) − F(x0 )) + B(u − u0 )
= −(x − x0 )T (F(x) − F(x0 )) + (y − y0 )T (u − u0 )
(14)
by using R = diag(R1 , . . . , RN ) and (11). Using Assumption
4(i) it follows that
V̇ ≤ (y − y0 )T (u − u0 )
e is incrementally passive, hence EIP.
Thus by Definition 2, Σ,

A. Distributed feedback design
e i , (10), for each individual player
Given agent dynamics Σ
n
we design ui ∈ R based on the relative output feedback

from its neighbours, such that the auxiliary state variables
(estimates) agree one with another and converge to the NE
x∗ . For simplicity, take B = IN n so that y = x.
Let Ni denote the set of neighbours of player i in graph Gc
and L denote the symmetric Laplacian matrix. Let L = L⊗In
denote the augmented Laplacian matrix which satisfies
N ull(L) = Range(1N ⊗ In )

(15)

and Range(L) = N ull(1TN ⊗ In ), based on L1N = 0N . For
any W ∈ Rq×n , and any x ∈ RN n , using L1N = 0N ,
(1TN ⊗ W )Lx = ((1TN L) ⊗ (W In ))x = 0q

(16)

e (12), the objective
With respect to the overall dynamics Σ,
is to design u such that x reaches consensus, i.e., 1N ⊗ x,
for some x ∈ Ω and x converges towards the NE x∗ . The
e (12) is
consensus condition is written as Lx = 0. Since Σ,
incrementally passive by Lemma 3, and L is positive semidefinite, a passivity-based control design, e.g. [36], suggests
taking u = −Lx. The resulting closed-loop system which
e is given in
represents the new overall system dynamics P
stacked notation as
e : ẋ = −RT F(x) − Lx
P

(17)

e
shown in Figure 2 as the feedback interconnection between Σ
and L. Local solutions of (17) exist by Assumption 2(i). The
u

e:
Σ

−

(
ẋ = −RT F(x) + u
y=x

y

an extra correction term. This term is instrumental in proving
convergence on a single timescale as shown in Section V.
The next result shows that the equilibrium of (17) or (19)
occurs when the agents are at a consensus and at NE.
Lemma 4. Consider a game G(I, Ji , Ωi ) over a communication graph Gc under Assumptions 1, 2(i). Let the dynamics
ei be as in (18), (19), or overall P,
e (17).
for each agent P
At an equilibrium point x ∈ ΩN the estimate vectors of all
players are equal x̄i = x̄j , ∀i, j ∈ I and equal to the Nash
equilibrium profile x∗ , hence the action components of all
players coincide with the optimal actions, x̄ii = x∗i , ∀i ∈ I.
Proof. Let x denote an equilibrium of (17),
0N n = −RT F(x̄) − Lx̄

(21)

Pre-multiplying both sides by (1TN ⊗In ), yields 0n = −(1TN ⊗
In )RT F(x̄), where (1TN ⊗In )Lx̄ = 0 was used by (15). Using
(11) and simplifying (1TN ⊗ In )RT gives
0n = F(x̄),

or

∇i Ji (x̄i ) = 0, ∀i ∈ I

(22)

by (13). Substituting (22) into (21) results in 0N n = −Lx̄.
From this it follows that x̄i = x̄j , ∀i, j ∈ I by Assumption 1
and (15). Therefore x̄ = 1N ⊗ x̄, for some x̄ ∈ Ω. Substituting
this back into (22) yields 0n = F(1N ⊗ x̄) or ∇i Ji (x̄) = 0,
for all i ∈ I. Using (13), ∇i Ji (x̄i , x̄−i ) = 0, for all i ∈ I, or
0n = F (x̄). Therefore by (4) x̄ = x∗ , hence x̄ = 1N ⊗ x∗
and for all i, j ∈ I, x̄i = x̄j = x∗ the NE of the game.
V. C ONVERGENCE A NALYSIS

L ⊗ In
Fig. 2. Augmented gradient dynamics (17) over Gc

ei are
new individual player dynamics P
X
ei : ẋi = −RTi ∇i Ji (xi ) −
P
(xi − xj )

(18)

j∈Ni

or, separating the action xii = xi and estimate xi−i dynamics,
("
# "
#
P
i
i
j
−∇
J
(x
,
x
)
−
R
(x
−
x
)
ẋ
i
i
i
i
i
−i
j∈Ni
ei :
=
P
P
ẋi−i
−Si ( j∈Ni xi − xj )
(19)
where


Si =

In<i

0n>i×n<i

0n<i×ni
0n>i×ni

0n<i×n>i
In>i


(20)

and Si removes xii = xi , its own action component from agent
i’s estimate vector, xi .
ei , (18) or (19) is clearly distributed over
For player i, P
Gc . Its input is the relative difference between its estimate
and its neighbours’. In standard consensus terms, agent i can
use this information to move in the direction of the average
value of its neighbours, while the gradient term enforces the
move towards minimizing its own cost. Compared to the
gossip-based algorithm in [16], the action part of (19) has

In this section we analyze the convergence of player’s new
ei (18), (19) or overall P
e (17) to the NE of the
dynamics P
game, over a connected graph Gc . We consider two cases.
In Section V-A we analyze convergence of (19) on a single
timescale: in Theorem 1 under Assumptions 1, 2(i), 3(i) and
4(i), and in Theorem 2 under Assumptions 1, 2(i), 3(ii) and
4(ii). We exploit the incremental passivity (EIP) property of
e (12) (Lemma 3) and diffusive properties of the Laplacian.
Σ
In Section V-B, we modify the estimate component of the
dynamics (19) to be much faster, and in Theorem 3 prove
convergence under Assumptions 1, 2(i), 3(ii) and 4(ii), using
a two-timescale singular perturbation approach.
A. Single-Timescale Consensus and Player Optimization
Theorem 1 shows that, under Assumption 4(i), (19) converges to the NE of the game, over any connected Gc .
Theorem 1. Consider a game G(I, Ji , Ωi ) over a communication graph Gc under Assumptions 1, 2(i), 3(i) and 4(i). Let
ei , be as in (18), (19), or overall P,
e
each player’s dynamics P
(17), as in Figure 2. Then, any solution of (17) is bounded
and asymptotically converges to 1N ⊗ x∗ , and the actions
components converge to the NE of the game, x∗ .
e (17) is x̄ = 1N ⊗x∗ .
Proof. By Lemma 4, the equilibrium of P
We consider the quadratic storage function V (x) = 12 kx−x̄k2 ,
x̄ = 1N ⊗ x∗ as a Lyapunov function. As in (14) in the proof

of Lemma 3, using u = −Lx, (21) we obtain that along the
solutions of (17),
V̇ = −(x − x̄)T RT (F(x) − F(x̄)) − (x − x̄)T L(x − x̄)
(23)
where x̄ = 1N ⊗ x∗ , and xT RT = x. By Assumption 4(i)
and since the augmented Laplacian L is positive semi-definite
it follows that V̇ ≤ 0, for all x ∈ ΩN , hence all trajectories
of (17) are bounded and x is stable. To show convergence we
resort to LaSalle’s invariance principle, [35].
From (23), V̇ = 0 when both terms in (23) are zero, i.e.,
(x− x̄)T RT (F(x)−F(x̄)) = 0 and (x− x̄)T L(x− x̄) = 0. By
Assumption 1 and (15), (x − x̄)T L(x − x̄) = 0 is equivalent
to x − x̄ = 1N ⊗ x, for some x ∈ Rn . Since at equilibrium
x̄ = 1N ⊗ x∗ , this implies that x = 1N ⊗ x, for some x ∈ Rn .
By (13) F(1N ⊗ x) = F (x). Using R in (11) yields for the
first term in (23) to be zero,
0 = −(1N ⊗ x − 1N ⊗ x∗ )T RT [F (x) − F (x∗ )]
∗ T

∗

= −(x − x ) [F (x) − F (x )] < 0

∀x 6= x

∗

(24)

If F(·) is strongly monotone, exponential convergence can
be shown over any connected Gc . Next we show that, under a
weaker Lipschitz property of F (Assumption 4(ii)) and strong
monotonicity of F (Assumption 3(ii)), (19) converges over
any sufficiently connected Gc .
Theorem 2. Consider a game G(I, Ji , Ωi ) over a communication graph Gc under Assumptions 1, 2(i), 3(ii) and 4(ii). Let
ei be as in (18), (19) or overall P
e
each player’s dynamics P
2
(17). Then, if λ2 (L) > θµ + θ, any solution of (17) converges
asymptotically to 1N ⊗ x∗ , and the actions components con2
verge to the NE of the game, x∗ . If λ2 (L) > Nµθ + θ, then
convergence is exponential.
n
n
⊕ EN
, into
Proof. We decompose RN n as RN n = CN
n
n
the consensus subspace CN = {1N ⊗ x |x ∈ R } and its
n
orthogonal complement EN
. Let two projection matrices be
defined as
1
1
PC = 1N ⊗ 1TN ⊗ In , PE = IN n − 1N ⊗ 1TN ⊗ In
N
N

Then any x ∈ RN n can be decomposed as x = x|| + x⊥ ,
n
n
where x|| = PC x ∈ CN
and x⊥ = PE x ∈ EN
, with
(x|| )T x⊥ = 0. Thus x|| = 1N ⊗ x, for some x ∈ Rn , so
that Lx|| = 0, and minx⊥ ∈ENn (x⊥ )T Lx⊥ = λ2 (L)kx⊥ k2 ,
λ2 (L) > 0.
Consider V (x) = 21 kx − xk2 , x = 1N ⊗ x∗ , which using
x = x|| + x⊥ can be written as V (x) = 12 kx⊥ k2 + 12 kx|| −xk2 .
Then following the same steps as in Lemma 3, and replacing
x with its decomposed components x⊥ , x|| a relation similar
to (23) follows along (17), i.e.,
− (x − x)T L(x − x)

− (x⊥ )T Lx⊥
Using (x⊥ )T Lx⊥ ≥ λ2 (L)kx⊥ k2 and F(x|| ) = F (x),
F(x) = F (x∗ ) yields
V̇ ≤ kx⊥ kkF(x) − F(x|| )k
− (x⊥ )T RT [F (x) − F (x∗ )]
h
i
− (x|| − 1N ⊗ x∗ )T RT F(x) − F(x|| )
− (x|| − 1N ⊗ x∗ )T RT [F (x) − F (x∗ )]

where strict inequality follows by Assumption 3(i). Therefore
V̇ = 0 in (23) only if x = x∗ and hence x = 1N ⊗ x∗ . Since
V is radially unbounded, the conclusion follows by LaSalle’s
invariance principle.

V̇ ≤ −(x − x)T RT [F(x) − F(x)]

Using x = x⊥ +x|| , x = 1N ⊗x∗ , Lx|| = 0, V̇ can be written
as
h
i
V̇ ≤ −(x⊥ )T RT F(x) − F(x|| )
h
i
− (x⊥ )T RT F(x|| ) − F(x)
h
i
− (x|| − 1N ⊗ x∗ )T RT F(x) − F(x|| )
h
i
− (x|| − 1N ⊗ x∗ )T RT F(x|| ) − F(x)

− λ2 (L)kx⊥ k2
Under Assumption 4(ii), kF(x) − F(x|| )k ≤ θkx⊥ k, so that,
after simplifying Rx|| = x, R(1N ⊗ x∗ ) = x∗ ,
V̇ ≤ −(λ2 (L) − θ)kx⊥ k2 − x⊥ RT [F (x) − F (x∗ )]
− (x − x∗ )T [F(x) − F(x|| )]
− (x − x∗ )T [F (x) − F (x∗ )]
Using again Assumption 4(ii) in the 3rd and 2nd terms and
Assumption 3(ii) in the 4th one, it can be shown that
V̇ ≤ −(λ2 (L) − θ)kx⊥ k2 + 2θkx⊥ kkx − x∗ k

(25)

∗ 2

− µkx − x k

or V̇ ≤ −[kx−x∗ k  kx⊥ k] Θ [kx−x∗ k kx⊥ k]T , where Θ =

µ
−θ
. Under the conditions in the statement,
−θ λ2 (L) − θ
Θ is positive definite. Hence V̇ ≤ 0 and V̇ = 0 only if x⊥ = 0
and x = x∗ , hence x = 1N ⊗ x∗ . The conclusion follows by
LaSalle’s invariance principle.
Exponential convergence follows using kx − x∗ k =
1
√ kx|| − xk, under the stricter condition on λ2 (L). Indeed,
N




kx|| − xk
V̇ ≤ − kx|| − xk kx⊥ k ΘN
kx⊥ k
 1

−θ
Nµ
where ΘN =
is positive definite if
−θ λ2 (L) − θ
2
λ2 (L) > Nµθ + θ. This implies that V̇ (x(t)) ≤ −ηV (x(t)),
for some η > 0, so that x(t) converges exponentially to x.
Remark 2. Since θ, µ are related to the coupling in the
players’ cost functions and λ2 (L) to the connectivity between
players, Theorem 2 highlights the tradeoff between properties
of the game and those of the communication graph Gc . Key is
the fact that the Laplacian contribution can be used to balance
the other terms in V̇ . Alternatively L on feedback path in
Figure 2 has excess passivity which compensates the lack of
e on the forward path .
passivity in the F terms, or Σ

Remark 3. We note that we can relax the monotonicity
assumption to hold just at the NE x∗ , recovering a strictdiagonal assumption used in [1]. However, since x∗ is unknown, such an assumption cannot be checked a-priori except
for special cases such as quadratic games, (see Section VII).
Local results follow if assumptions for F (·) hold only locally
around x∗ , and for F(·) only locally around x∗ = 1N ⊗ x∗ .
We note that the class of quadratic games satisfies Assumption
3(ii) globally.
e (17),
An alternative representation of the dynamics P,
reveals interesting connections to distributed optimization and
passivity based control, [10], [36]. To do that we use two
e (17). Let
matrices to write a compact representation for P,
(N n−n)×N n
S = diag(S1 , ..., SN ) ∈ R
, where Si in (20). Then
S and R (11) satisfy SRT = 0 and
T

T

T

T

T

R R + S S = I, RR = I, RS = 0, SS = I (26)
Using
R
and
S,
the
stacked
actions
are
T T
)
]
=
Rx,
while
the
stacked
estimates
[(x11 )T , . . . , (xN
N
T T
= Sx. Let x = Rx and z = Sx,
[(x1−1 )T , . . . , (xN
−N ) ]
and using properties of R, S, (26), yields x = RT x + S T z.
e (17) is:
Thus the equivalent representation of P
(
ẋ = −F(RT x + S T z) − RL[RT x + S T z]
e
P:
(27)
ż = −SL[RT x + S T z]
which separates the actions and the estimates stacked components of the dynamics. Using L = L ⊗ In and L = QQT ,
with Q the incidence matrix, yields the interconnected blockdiagram in Figure 3.
We note that, unlike distributed optimization (e.g. [10])
and passivity based control (e.g. [36]) where the dynamics
are decoupled, in Figure 2 the dynamics on the top path are
coupled, due to the inherent coupling in players’ cost functions
in game G(I, Ji , Ωi ). As another observation, recall that given
a matrix Q, pre-multiplication by Q and post-multiplication
by QT preserves passivity of a system. Figure 2 shows that
possible generalized dynamics can be designed by substituting
the identity block on the feedback path by some other passive
dynamics. Based on Figure 2, one such dynamic generalization
can be obtained by substituting the static feedback through
L, with an integrator or proportional-integrator term through
L, which preserves passivity, as in [10]. Thus the passivity
interpretation of the game NE seeking dynamics design allows
a systematic derivation of new dynamics/algorithms.
Note that if the dynamics of the estimates were modified
such that the system approached quickly the consensus subspace then convergence to the NE could be shown via a timescale decomposition approach. This is explored in the next
section.
B. Two-Timescale Singular Perturbation Analysis
In this section we relax the connectivity bound on L
in Theorem 2, based on a time-scale separation argument.
e
The idea is to modify the dynamics of the estimates in P
(17) or (27) such that the system approaches quickly the
consensus subspace. Under Assumption 3(ii) and 4(ii), we

u

−R

x

ẋ = −F(x, z) + u

RT

z

−S

ż

1
s

0
..

ST

+

1
s

0

Q ⊗ In

z

.

Id

QT ⊗ In x

Fig. 3. Block Diagram of Actions and Estimates dynamics in (17)

show convergence to the NE over a sufficiently connected Gc
based on a time-scale decomposition approach.
e in (27) and modify
Recall the equivalent representation of P
the estimate component of the dynamics such that is much
faster than the action component,
(
T
T
T
T
e : ẋ = −F(R x + S z) − RL[R x + S z] (28)
P
T
T
ż = −SL[R x + S z]
where  > 0. Thus player i’s dynamics is as follows:
("
#
# "
P
i
i
j
−∇
J
(x
,
x
)
−
R
(x
−
x
)
ẋ
i
i
i
i
i
−i
j∈N
i
ei, :
P
=
P
ẋi−i
− 1 Si ( j∈Ni xi − xj )
(29)
e (28) is in
with the 1 high gain on the estimate component. P
the standard form of a singularly perturbed system, where the
estimate dynamics and the action dynamics are the fast and
the slow components, respectively.
Theorem 3. Consider a game G(I, Ji , Ωi ) over a communication graph Gc under Assumptions 1, 2(i), 3(ii) and 4(ii).
ei, be as in (29), or overall
Let each player’s dynamics P
e
P (28),  > 0. Then, there exists ∗ > 0, such that for
all 0 <  < ∗ , (x∗ , S(1N ⊗ x∗ )) is exponentially stable.
Alternatively, (x∗ , S(1N ⊗ x∗ )) is asymptotically stable, for
all 0 <  < 1 such that
√ θ
λ2 (L) >  N ( + 1)(θ + 2d∗ )).
µ
Proof. We analyze (28) by examining the reduced and the
boundary-layer systems. First we find the roots of SL[RT x +
S T z] = 0, or SLx = 0. Note that, by (26), x ∈ N ull(SL)
if and only if Lx ∈ N ull(S), which is equivalent to Lx ∈
Range(RT ). Thus x ∈ N ull(SL) if and only if there exists
q ∈ Rn such that Lx = RT q. Then for such q ∈ Rn and
for all w ∈ Rn , (1TN ⊗ wT )Lx = (1TN ⊗ wT )RT q. Using
(1TN ⊗wT )Lx = 0 by (16) and R in (11), this means 0 = wT q,
for all w ∈ Rn . Therefore, q = 0 and Lx = 0. By (15),
x = 1N ⊗ x, x ∈ Ω. Hence roots of SL[RT x + S T z] = 0 are
when x = (1N ⊗ x), i.e., z = S(1N ⊗ x).
We use a change of coordinates v = z − S(1N ⊗ x), to shift
the equilibrium of the boundary-layer system to the origin.

First, we use z = v + S(1N ⊗ x) and x = R(1N ⊗ x) to
rewrite the term RT x + S T z that appears in (28) as follows,
RT x + S T z = RT R(1N ⊗ x) + S T (v + S(1N ⊗ x))
= (RT R + S T S)(1N ⊗ x) + S T v = 1N ⊗ x + S T v

α1 α2
, is given as
Then using Theorem 11.3, ∗ = α1 γ+β
1 β2

∗ =

λ2 (L)µ
N N (θ + µ)(θ + λN (L))
√

and using λN (L) ≤ 2d∗ = 2 maxi∈I |Ni |,

where (26) was used. Using this and the change of variables
v = z − S(1N ⊗ x) into (28) with L(1N ⊗ x) = 0 yields,

T
T

ẋ = −F(1N ⊗ x + S v) − RLS v
e : v̇ = −SLS T v + S(1N ⊗ RLS T v)
P
(30)


T
+S(1N ⊗ F(1N ⊗ x + S v))

Then, by Theorem 11.3 in [35], for any 0 <  < 1 such that
√ θ
λ2 (L) > N N ( + 1)(θ + 2d∗ ))
µ

Note that v = 0 is the quasi-steady state of v̇ and substituting
this in ẋ gives the reduced system as

(x∗ , 0) is asymptotic stable for (30), hence (x∗ , S(1N ⊗ x∗ ))
is asymptotic stable for (28).

ẋ = −F(1N ⊗ x) = −F (x)

dv
= −SLS T v
dτ

(32)

It can be shown that matrix SLS T is positive definite, so that
(32) is exponentially stable. To see this note that SLS T v =
0 only if S T v ∈ N ull(SL). Recall that N ull(SL) =
N ull(L) = (1N ⊗ w), w ∈ Ω. Note that to be in N ull(L),
y = [(y 1 )T . . . (y N )T ]T = S T v has to have y i = y j , ∀i, j ∈ I,
but y has a 0 in component yii ∀i ∈ I, due to the definition of
S. Therefore y i 6= y j unless yij = yii = 0, for all j. Therefore
y = S T v has to be equal to 0 to be in the N ull(L). Since
N ull(S T ) = {0} this implies v = 0, hence N ull(SLS T ) = 0
and SLS T is positive definite. By Theorem 11.4 in [35] it
follows that there exists ∗ > 0, such that for all  < ∗ ,
(x∗ , 0) is exponentially stable for (30), or (x∗ , S(1N ⊗ x∗ ))
is exponentially stable for (28).
Alternatively, Theorem 11.3 in [35] can be applied to (30)
to show asymptotic stability. The two Lyapunov functions
are V (x) = 21 kx − x∗ k2 and W (v) = 21 kvk2 , and along
the reduced and the boundary layer-systems, (31),(32), the
following hold
−(x − x∗ )T F(1N ⊗ x) ≤ −µkx − x∗ k2
T

λ2 (L)µ
√
N N (θ + µ)(θ + 2d∗ ))

(31)

which is exactly the gradient dynamics and has equilibrium
x∗ at the NE. By Lemma 2, under Assumption 3(ii) the gradient
dynamics, (31), is exponentially stable.
The boundary-layer system on the τ = t/ timescale is

T

∗ ≥

ei, (29) the estimate dynamics is made faster
Remark 4. In P
with the gain
be shown that for sufficiently high
√ 1/. It can
∗
1/, 1 > N N (1 + 2 dθ ), the bound on λ2 (L) in Theorem 3
is lower than the bound on λ2 (L) in Theorem 2. Alternatively,
we can consider a gain parameter 1 > 0 on the estimates in
2
(17) to improve the lower bound to λ2 (L) > ( θµ + θ), as
shown in the next section. Thus a higher 1/ can relax the
connectivity bound on L, but  is a global parameter. This
highlights another aspect of the tradeoff between game properties (coupling), communication graph (consensus) properties
and information.
VI. P ROJECTED NE DYNAMICS FOR C OMPACT ACTION
S ETS
In this section we treat the case of compact Ωi action
sets, under Assumption 2(ii), using projected dynamics. We
highlight the major steps of the approach and their differences
compared to the unconstrained action set case.
In a game of perfect information, for compact Ωi action set,
under Assumption 2(ii) each player i ∈ I runs the projected
gradient-based dynamics, given as [21], [22],
Pi : ẋi = ΠΩi (xi , −∇i Ji (xi , x−i )), xi (0) ∈ Ωi

(33)

The overall system of all agents’ projected dynamics in stacked
notation is given by
P : ẋ(t) = ΠΩ (x(t), −F (x(t))) ,

x(0) ∈ Ω

(34)

2

−v SLS v ≤ −λ2 (L)/N kvk

so that (11.39) and (11.40) in [35] hold for α1 = µ, ψ1 (x) =
kx − x∗ k, and α2 = λ2 (L)/N , ψ2 (v) = kvk.
Note also that the following holds


(x − x∗ )T −F(1N ⊗ x + S T v) − RLS T v + F(1N ⊗ x)
≤ (θ + λN (L))kx − x∗ kkvk
so that (11.43) in [35] holds for β1 = θ + λN (L).
Similarly,
v T S(1N ⊗ RLS T v) + v T S(1N ⊗ F(1N ⊗ x + S T v))
√
√
≤ N θkx − x∗ kkvk + N (θ + λN (L))kvk2
√
√
and (11.44), [35] holds for β2 = N θ, γ = N (θ + λN (L)).

or, equivalently,
P : ẋ(t) = PTΩ (x(t)) [−F (x(t)] ,

x(0) ∈ Ω

where equivalence follows by using Lemma 1 (Moreau’s
decomposition theorem, [25]), or directly by Proposition 1
and Corollary 1 in [37]. Furthermore, this is equivalent to the
differential inclusion [38]
−F (x(t)) − ΠΩ (x(t), −F (x(t))) ∈ NΩ (x(t)).

(35)

In all the above the projection operator is discontinuous on the
boundary of Ω. We use the standard definition of a solution
of a projected dynamical system (PDS), (Definition 2.5 in
[24]). Thus we call x : [0, +∞) → Ω a solution of (34)
if x(·) is an absolutely continuous function t 7→ x(t) and

ẋ(t) = ΠΩ (x(t), −F (x(t))) holds almost everywhere (a.e.)
with respect to t, i.e., except on a set of measure zero.
The existence of a unique solution of (34) is guaranteed
for any x(0) ∈ Ω, under Lipschitz continuity of F on Ω, cf.
Theorem 2.5 in [24]. Note that any solution must necessarily
lie in Ω for almost every t. Alternatively, existence holds under
continuity and (hypo) monotonicity of F , i.e., for some µ ≤ 0,
(x − x0 )T (F (x) − F (x0 )) ≥ µkx − x0 k2 ,

∀x, x0 ∈ Ω

(see Assumption 2.1 in [24], and also Theorem 1 in [37] for
extension to a non-autonomous systems). This is similar to
the QUAD relaxation in [39]. It means that F (x) − µx is
monotone, where µ ≤ 0. Note that F (x) + ηx is strongly
monotone for any η > −µ, with η + µ > 0 monotonicity
constant. When µ > 0 in fact we can take η = 0 and recover
µ-strong monotonicity of F . Thus under Assumption 2(ii),
3(i), for any x(0) ∈ Ω, there exists a unique solution of (34)
and moreover, a.e., ẋ(t) ∈ TΩ (x(t)) and x(t) ∈ Ω.
Equilibrium points of (34) coincide with Nash equilibria,
which are solutions of the VI(F , Ω), by Theorem 2.4 in [24].
To see this, let x be an equilibrium point of (34) such that
{x ∈ Ω | 0n = ΠΩ (x, −F (x))}. By Lemma 2.1 in [24] and
(1), if x ∈ intΩ, then 0n = ΠΩ (x, −F (x)) = −F (x), while
if x ∈ ∂Ω, then
0n = ΠΩ (x, −F (x)) = −F (x) − β n

(36)

for some β > 0 and n ∈ n(x) ⊂ NΩ (x). Equivalently, by
(35), −F (x) ∈ NΩ (x) and using the definition of NΩ (x), it
follows that
−F (x)T (x − x) ≤ 0,

∀x ∈ Ω

Comparing to (6), or (7), it follows that x = x∗ . Thus the
equilibrium points of (34) {x∗ ∈ Ω | 0n = ΠΩ (x∗ , −F (x∗ ))}
coincide with Nash equilibria x∗ .
Lemma 5. Consider a game G(I, Ji , Ωi ) in the perfect
information case, under Assumptions 2(ii) and 3(i). Then, for
any xi (0) ∈ Ωi , the solution of (33), i ∈ I, or (34) converges
asymptotically to the NE of the game x∗ . Under Assumption
3(ii) convergence is exponential.
Proof. The proof follows from Theorem 3.6 and 3.7 in [24].
Consider any x(0) ∈ Ω and V (t, x) = 12 kx(t) − x∗ k2 ,
where x∗ is the Nash equilibrium of the game, and x(t) is
the solution of (34). Then the time derivative of V along
solutions of (34) is V̇ = (x(t) − x∗ )T ΠΩ (x(t), −F (x(t))).
Since TΩ (x(t)) = [NΩ (x(t))]o , by Moreau’s decomposition
theorem (Lemma 1), at any point x(t) ∈ Ω the pseudogradient −F (x(t)) can be decomposed as in (2) into normal
and tangent components, in NΩ (x(t)) and TΩ (x(t)). Since
ΠΩ (x(t), −F (x(t))) = PTΩ (x(t)) (−F (x(t))) is in the tangent
cone TΩ (x(t)), it follows as in (35) that
−F (x(t)) − ΠΩ (x(t), −F (x(t))) ∈ NΩ (x(t))

(37)

From the definition of the normal cone NΩ (x(t)) this means,
0

T

(x − x(t)) (−F (x(t)) − ΠΩ (x(t), −F (x(t)))) ≤ 0

for all x0 ∈ Ω. Thus it follows that for x0 = x∗ and ∀x(t) ∈ Ω,
(x(t) − x∗ )T ΠΩ (x(t), −F (x(t)))) ≤ −(x(t) − x∗ )T F (x(t))
From (6), at the Nash equilibrium F (x∗ )T (x(t) − x∗ ) ≥ 0,
∀x(t) ∈ Ω. Therefore adding this to the right-hand side of
the above and using V̇ (t) yields that along solutions of (34),
for all t ≥ 0, V̇ = (x(t) − x∗ )T ΠΩ (x(t), −F (x(t))) ≤
−(x(t)−x∗ )T (F (x(t))−F (x∗ )) < 0, when x(t) 6= x∗ , where
the strict inequality follows from Assumption 3(i). Hence V (t)
is monotonically decreasing and non-negative, and thus there
exists limt→∞ V (t) = V . As in Theorem 3.6 in [24], a
contradiction argument can be used to show that V = 0, hence
for any x(0) ∈ Ω, kx(t) − x∗ k → 0 as t → ∞.
Under Assumption 3(ii), for any x(0) ∈ Ω, along solutions
of (34), for all t ≥ 0, V̇ ≤ −µkx(t)−x∗ k2 = −µV (t), µ > 0,
∀x and exponential convergence follows immediately.
In the partial or networked information case, over graph Gc ,
e i , in (9) using projected dynamics
we modify each player’s Σ
for the action components to Ωi , as in
# "
"
#
i
i

 ẋi = ΠΩi xi , −∇i Ji (xi , x−i ) + Bi ui (t)
i
ei :
Σ
ẋi
B−i
ui
 −i

i T i
yi = (B ) x
(38)
where ui (t) ∈ Rn is a piecewise continuous function, to
be designed based on the relative output feedback from its
neighbours, such that xi = xj , for all i, j, and converge
e i (38) in a more compact form
towards the NE x∗ . Write Σ
(

i
T
i
i
ẋ
=
R
Π
x
,
−∇
J
(x
)
+
R
B
u
+ SiT Si B i ui
Ω
i
i
i
i
i
i
i
ei :
Σ
i T i
yi = (B ) x
(39)
where Ri , Si , are defined as in (11), (20). The overall
e
dynamics for all players becomes in stacked form, Σ,
(
T
T
e : ẋ = R ΠΩ (Rx(t), −F(x(t)) + RBu(t)) + S SBu(t)
Σ
T
y = B x(t)
(40)
where x = Rx, R = diag(R1 , . . . , RN ), S =
diag(S1 , . . . , SN ), satisfying the properties in (26), and u(t) ∈
RN n is piecewise continuous. This is similar to (12), except
that the dynamics for the action components is projected to
Ω. For any Rx(0) ∈ Ω, existence of a unique solution of (40)
is guaranteed under Assumption 4(i) or (ii) by Theorem 1 in
[37]. Extending the incrementally passivity and EIP concept
to projected dynamical systems leads to the following result.
e (40),
Lemma 6. Under Assumption 4(i), the overall system Σ,
is incrementally passive, hence EIP.
Proof. Consider two inputs u(t), u0 (t) and let x(t), x0 (t),
e (40). Let
y(t), y0 (t) be the state trajectories and outputs of Σ
the storage function be V (t, x, x0 ) = 12 kx(t) − x0 (t)k2 . Then,
along solutions of (40),
V̇ = (x(t) − x0 (t))T RT [ΠΩ (Rx(t), −F(x(t)) + RBu(t))
− ΠΩ (Rx0 (t), −F(x0 (t)) + RBu0 (t))]
0

T

T

0

+ (x(t) − x (t)) S SB(u(t) − u (t))

(41)

Notice that using (26) the following holds for (40),
Rẋ(t) = ΠΩ (Rx(t), −F(x(t)) + RBu(t)) ∈ TΩ (Rx(t))
Hence as in (37), for any Rx(t) ∈ Ω,
−F(x)(t) + RBu(t) − ΠΩ (Rx(t), −F(x(t)) + RBu(t))
∈ NΩ (Rx(t))
and using the definition of normal cone NΩ (Rx(t)),
(Rx(t) − Rx0 (t))T ΠΩ (Rx(t), −F(x(t)) + RBu(t)) ≤
(Rx(t) − Rx0 (t))T (−F(x(t)) + RBu(t))
(42)
for all Rx0 (t) ∈ Ω. Since Rx(t) ∈ Ω and Rx0 (t) ∈ Ω are
both arbitrary elements in Ω, swapping them leads to
(Rx0 (t) − Rx(t))T ΠΩ (Rx0 (t), −F(x0 (t)) + RBu0 (t)) ≤
(Rx0 (t) − Rx(t))T (−F(x0 (t)) + RBu0 (t))
(43)

T

T

(x(t)−x (t)) R [ΠΩ (Rx(t), −F(x(t)) + RBu(t))
0

ei , in (47) has projected action compoCompared to (19), P
nents. The next result shows that the equilibrium of (45) or
(47) occurs when the agents are at a consensus and at NE.
Lemma 7. Consider a game G(I, Ji , Ωi ) over a communication graph Gc under Assumptions 1, 2(ii) and 4(i) or (ii).
ei be as in (47), or overall
Let the dynamics for each agent P
e
P, (45). At an equilibrium point x the estimate vectors of
all players are equal x̄i = x̄j , ∀i, j ∈ I and equal to the
Nash equilibrium profile x∗ , hence the action components of
all players coincide with the optimal actions, x̄ii = x∗i , ∀i ∈ I.
Proof. Let x denote an equilibrium of (45),
0N n = RT ΠΩ (Rx, −F(x̄) − RLx̄) − S T SLx̄

Adding (42) and (43) results in
0

or (46) after separating the action xii = xi and estimate xi−i
ei are,
dynamics, the new projected player dynamics P


(
P
i
i
j
ẋ
=
Π
x
,
−∇
J
(x
)
−
R
(x
−
x
)
i
Ω
i
i
i
i
i
j∈Ni
ei :
P
P
ẋi−i = −Si ( j∈Ni xi − xj )
(47)

0

Pre-multiplying both sides by R and using (26) simplifies to,

0

− ΠΩ (Rx (t), −F(x (t)) + RBu (t))] ≤

0n = ΠΩ (Rx, −F(x̄) − RLx̄)

− (x(t) − x0 (t))T RT (F(x(t)) − F(x0 (t)))

(49)

Substituting (49) into (48) results in 0N n = −S T SLx̄ which
implies x̄ ∈ null(L). From this it follows that x̄i = x̄j ,
∀i, j ∈ I by Assumption 1 and (15). Therefore x̄ = 1N ⊗ x̄,
for some x̄ ∈ Ω. Substituting this back into (49) yields
0n = ΠΩ (R(1N ⊗ x̄), −F(1N ⊗ x̄)) or 0n = ΠΩ (x̄, −F (x̄))
by using (13). Therefore as in (36) it follows that −F (x̄) ∈
NΩ (x̄) hence, by (7), x̄ = x∗ the NE. Thus x̄ = 1N ⊗ x∗ and
for all i, j ∈ I, x̄i = x̄j = x∗ the NE of the game.

+ (x(t) − x0 (t))T RT RB(u(t) − u0 (t))
Therefore using this in (41), yields for V̇
V̇ ≤ −(x(t) − x0 (t))T RT (F(x(t)) − F(x0 (t)))
+ (x(t) − x0 (t))T RT RB(u(t) − u0 (t))
+ (x(t) − x0 (t))T S T SB(u(t) − u0 (t))
or, using RT R + S T S = I,
V̇ ≤ −(x(t) − x0 (t))T RT (F(x(t)) − F(x0 (t)))
+ (x(t) − x0 (t))T B(u(t) − u0 (t))

(48)

(44)

Finally, using Assumption 4(i), it follows that
V̇ ≤ (y(t) − y0 (t))T (u(t) − u0 (t))
e is incrementally passive, hence EIP.
and Σ
e (40) is incrementally passive by Lemma 6, and
Since Σ,
L is positive semi-definite, as in Section IV-A we consider a
passivity-based control u(t) = −Lx(t). The resulting closedloop system which represents the new overall system dynamics
e is given in stacked notation as
P
e : ẋ = RT ΠΩ (Rx(t), −F(x(t)) − RLx(t)) − S T SLx(t)
P
(45)
Alternatively, using x = Rx, z = Sx, RS T = 0, equivalently
with actions and estimates separated as in (27),
(

T
T
T
T
e : ẋ = ΠΩ x, −F(R x + S z) − RL[R x + S z]
P
ż = −SL[RT x + S T z]
(46)
Existence of a unique solution of (45) or (46) is guaranteed
under Assumption 4(i) or (ii) by Theorem 1 in [37]. From (45)

The following results show single-timescale convergence to
the NE of the game over a connected Gc , under Assumption
4(i) or Assumption 4(ii).
Theorem 4. Consider a game G(I, Ji , Ωi ) over a communication graph Gc under Assumptions 1, 2(ii), 3(i) and 4(i).
ei , be as in (47), or overall P,
e
Let each player’s dynamics P
(45). Then, for any x(0) ∈ Ω and any z(0), the solution of
(45) asymptotically converges to 1N ⊗ x∗ , and the actions
components converge to the NE of the game, x∗ .
Proof. The proof is similar to the proof of Theorem 1 except
that, instead of LaSalle’s invariance principle, the argument is
based on Barbalat’s Lemma, [35], since the system is timevarying. Let V (t, x) = 21 kx(t) − xk2 , where by Lemma 7,
x = 1N ⊗ x∗ . Using (44) in Lemma 6, for x0 (t) = x, u(t) =
−Lx(t), u0 (t) = −Lx, it follows that for any x(0) ∈ Ω and
any z(0), along (45),
V̇ ≤ − (x(t) − x̄)T RT (F(x(t)) − F(x̄))

(50)

T

− (x(t) − x̄) L(x(t) − x̄)
Under Assumption 4(i), V̇ ≤ 0, for all Rx(t) ∈ Ω, z(0). Thus
V (t, x(t)) is non-increasing and bounded from below by 0,
hence it converges as t → ∞ to some RV ≥ 0. Then, under Ast
sumption 4(i), it follows that limt→∞ 0 (x(τ )− x̄)T L(x(τ )−
x̄)dτ exists and is finite. Since x(t) is absolutely continuous,

hence uniformly continuous, from Barbalat’s Lemma in [35] it
follows that L(x(t) − x̄) → 0 as t → ∞. Since x = 1N ⊗ x∗ ,
this means that x(t) → 1N ⊗ x, as t → ∞ for some x ∈ Ω.
Then V (t, x(t)) = 12 kx(t) − xk2 → 12 k1N ⊗ (x − x∗ )k2 = V
as t → ∞. If V = 0 the proof if completed. Using the
strict monotonicity assumption 3(i), it can be shown by a
contradiction argument that x = x∗ and V = 0. Assume that
x 6= x∗ and V > 0. Then from (50) there exists a sequence
{tk }, tk → ∞, as k → ∞, such that V̇ (tk ) → 0 as k → ∞.
Suppose this claim is false. Then there exists a d > 0 and a
T > 0 such that V̇ (t) ≤ −d, for all t > T , which contradicts
V > 0, hence the claim is true. Substituting {tk } into (50)
yields
V̇ (tk ) ≤ − (x(tk ) − x̄)T RT (F(x(tk )) − F(x̄))
− (x(tk ) − x̄)T L(x(tk ) − x̄)
where the left-hand side converges to 0 as k → ∞. Hence,
0 ≤ − lim (x(tk ) − x̄)T RT (F(x(tk )) − F(x̄))
k→∞

− lim (x(tk ) − x̄)T L(x(tk ) − x̄)
k→∞

Using limk→∞ x(tk ) = 1N ⊗ x ∈ N ull(L), this leads to
0 ≤ − [1N ⊗ (x − x∗ )]T RT (F(1N ⊗ x) − F(1N ⊗ x∗ ))

Following the proof of Theorem 2 the matrix Θ becomes


µ
−θ
Θ=
−θ 1 λ2 (L) − θ
where the condition for the matrix to be positive definite is
2
λ2 (L) > ( θµ + θ). As in the two-time scale analysis this  is
a global parameter.
VII. N UMERICAL E XAMPLES
A. Unconstrained Ω and Dynamics
Example 1: Consider a N-player quadratic game from
economics, where 20 firms are involved in the production of
a homogeneous commodity. The quantity produced by firm
i is denoted by xi . The overall cost function of firm i is
Ji (xi , x−i ) = ci (xi ) − xi f (x), where ci (xi ) = (20
P+ 10(i −
1))xi is the production cost, f (x) = 2200 − i∈I xi is
the demand price, as in [18]. We investigate the proposed
dynamics (19) over a communication graph Gc via simulation.
The initial conditions are selected randomly from [0, 20].
Assumption 3(i) and 4(i) hold, so by Theorem 1 the dynamics
(19) will converge even over a minimally connected graph.
Figures 6 and 7 show the convergence of (19) over a randomly
generated communication graph Gc (Fig. 4) and over a cycle
Gc graph (Fig. 5), respectively.

or, 0 ≤ −(x − x∗ )]T (F (x) − F (x∗ )) < 0, by the strict
monotonicity Assumption 3(i), since we assumed x 6= x∗ .
This is a contradiction, hence x = x∗ and V = 0.

11
6
14

Note also that we can consider a gain parameter 1 > 0 on
the estimates in (45) to improve the lower bound to λ2 (L).

2

19

18

20

2

20
12

3

17

13
4

10

3

5

9

4

8

Fig. 4. Random Gc , λ2 = 4.95

Fig. 5. Cycle Gc Graph

250

500
450

200

400
350
300
action

150
action

Proof. The proof is similar to the proof of Theorem 2. Based
on Lemma 7, using V (t, x, x) = 12 kx(t) − xk2 and (44) in
Lemma 6, for u(t) = −Lx(t), u0 (t) = −Lx(t) one can obtain
(50) along (45), for any x(0) ∈ Ω and any z(0). Then further
decomposing x(t) into x⊥ (t) and x|| (t) components as in the
proof of Theorem 2 leads to an inequality as (25), where Θ
is positive under the conditions in the theorem. Then invoking
Barbalat’s Lemma in [35] as in the proof of Theorem 4 leads
to x(t) → x∗ and x⊥ (t) → 0 as t → ∞.

1

15

7
1

Theorem 5. Consider a game G(I, Ji , Ωi ) over a communication graph Gc under Assumptions 1, 2(ii), 3(ii) and 4(ii).
ei be as in (47) or overall P
e
Let each player’s dynamics P
θ2
(45). Then, if λ2 (L) > µ + θ, for any x(0) ∈ Ω and
any z(0), the solution of (45) asymptotically converges to
1N ⊗ x∗ , and the actions converge to the NE of the game,
2
x∗ . If λ2 (L) > Nµθ + θ, then convergence is exponential.

5

16

100

250
200
150

50

100
50

0
0

50

100

150
time

200

250

Fig. 6. (19) over random Gc

300

0
0

50

100

150
time

200

250

300

Fig. 7. (19) over cycle Gc

Consider
e : ẋ = RT ΠΩ (Rx, −F(x) − 1 RLx) − 1 S T SLx (51)
P


Thus player i’s dynamics is as follows:

 


ΠΩi (xi , −∇i Ji (xi , xi−i )
 ẋi
P
 

ei, : 
P
− 1 Ri j∈Ni (xi − xj ))

=

P
 i
ẋ−i
− 1 Si ( j∈Ni xi − xj )
(52)

Example 2: Consider a second example of an 8 player game
with Ji (xi , x−iP
) = ci (xi )−xi f (x), ci (xi ) = (10+4(i−1))xi ,
f (x) = 600 − i∈I x2i , as in [16]. Here Assumption 4(i) on
F does not hold globally, so cannot apply Theorem 1, but
Assumption 4(ii) holds locally. By Theorem 2, (19) will converge depending on λ2 (L). Figure 10 shows the convergence
of (19) over a sufficiently connected, randomly generated
communication graph Gc as depicted in Fig. 8. Over a cycle
Gc graph, (19) does not converge. Alternatively, by Theorem

4

250

250

200

200

150

150
action

action

3, a higher 1/ (time-scale decomposition) can balance the
connectivity loss. Fig. 11 shows convergence for (29) with
1/ = 200, over a cycle Gc graph as shown in Fig. 9. The
initial conditions are selected randomly from [0, 20].

100

100

3

1

6

2

50

50

0

0

2

8

8
5

1

3
5

−50
0

4

50

100

150
time

200

250

−50
0

300

200

400
time

600

800

7

Fig. 8. Random Gc , λ2 = 1.67

Fig. 9. Cycle Gc Graph

Fig. 14. (47) over random Gc

16

12

19 shows results for (52) with 1/ = 200, over a cycle Gc
graph as in Fig. 17. The actions’ initial conditions are selected
randomly from [0, 20] and the estimates from [−200, 200].

14

10

Fig. 15. (47) over cycle Gc

12

action

action

8

6

10
3

5

1

2

8

2

6

4
6

4

8

8

2

3

4
7

0
0

0.1

0.2
time

0.3

0.4

2
0

0.1

0.2

0.3

0.4

5

0.5

time

4

1

Fig. 16. Random Gc , λ2 = 0.83 Fig. 17. Cycle Gc Graph
Fig. 10. (19) over random Gc

Fig. 11. (29) cycle Gc , 1/ = 200
20

12

B. Compact Ω and Projected Dynamics

10

15

8
action

10
action

Example 1: N = 20 and this time Ωi = [0, 200].
We investigate the projected augmented gradient dynamics
(47) over a graph Gc . The actions’ initial conditions are
selected randomly from [0, 200], while the estimates from
[−2000, 2000]. Assumption 3(i) and 4(i) hold, so by Theorem
4 the dynamics (47) will converge even over a minimally
connected graph. Figures 14 and 15 show the convergence
of (47) over a randomly generated communication graph Gc
(Fig. 12) and over a cycle Gc graph (Fig. 13), respectively.

6

5
4
0

2

0
0

0.1

0.2
time

0.3

Fig. 18. (47) over random Gc

6
18

−5
0

0.2

0.4
time

0.6

0.8

Fig. 19. (52) cycle Gc , 1/ = 200

11

16

1

ID: 15

15

7

2

5
4

19

8

20

2
17

1

3

9
10

14
3

12

0.4

5

4

13

20

Fig. 12. Random Gc , λ2 = 3.13 Fig. 13. Cycle Gc Graph

Example 2: N = 8 and Ωi = [0, 20], as in [16]. Here
Assumption 4(i) on F does not hold globally, so cannot apply
Theorem 4. Under Assumption 3(ii) and 4(ii) by Theorem 2,
(47) will converge depending on λ2 (L). Figure 18 shows the
convergence of (47) over a sufficiently connected, randomly
generated communication graph Gc as in Fig. 16. A higher
1/ on the estimates can balance the lack of connectivity. Fig.

Example 3: Consider Ji (xi , x−i ) = ci (xi ) − xi f (x),
Pwhere
ci (xi ) = [20 + 40(i − 1)]xi and f (x) = 1200 − i (xi ),
Ω
 i = [0, 200], for N = 20. The NE is on the boundary

200 200 183.3 143.3 103.3 63.3 23.3 0 · · · .
Figure 22 shows the convergence of (47) over a randomly
generated communication graph Gc as in Fig. 20, while Fig.
23 gives similar results, this time over a cycle Gc graph as
depicted in Fig. 21.
VIII. C ONCLUSION
In this paper, we studied distributed Nash equilibrium (NE)
seeking over networks in continuous-time. We proposed an
augmented gradient-play dynamics with estimation in which
players communicate locally only with their neighbours to
compute an estimate of the other players’ actions. We derived

4

16

1

2
11

2

3

14
17
1

19
5

18

20

10

20

3

6
9
15

12

13

5

4

8
7

250

250

200

200

150

150
action

action

Fig. 20. Random Gc , λ2 = 1.87 Fig. 21. Cycle Gc Graph

100

100

50

50

0

0

−50
0

100

200
time

300

Fig. 22. (47) over random Gc

400

−50
0

200

400
time

600

800

Fig. 23. (47) over cycle Gc

the new dynamics based on the reformulation as a multiagent coordination problem over an undirected graph. We
exploited incremental passivity properties and showed that a
synchronizing, distributed Laplacian feedback can be designed
using relative estimates of the neighbours. Under strict monotonicity property of the pseudo-gradient, we proved that the
new dynamics converges to the NE of the game. We discussed
cases that highlight the tradeoff between properties of the
game and the communication graph.
R EFERENCES
[1] P. Frihauf, M. Krstic, and T. Başar, “Nash Equilibrium Seeking in
Noncooperative Games,” IEEE Trans. on Automatic Control, vol. 57,
no. 5, pp. 1192–1207, 2012.
[2] Y. Lou, Y. Hong, L. Xie, G. Shi, and K. Johansson, “Nash equilibrium
computation in subnetwork zero-sum games with switching communications,” IEEE Trans. on Automatic Control, vol. 61, no. 10, pp. 2920–
2935, 2016.
[3] M. S. Stankovic, K. H. Johansson, and D. M. Stipanovic, “Distributed
seeking of Nash equilibria with applications to mobile sensor networks,”
IEEE Trans. on Automatic Control, vol. 57, no. 4, pp. 904–919, 2012.
[4] H. Li and Z. Han, “Competitive Spectrum Access in Cognitive Radio
Networks: Graphical Game and Learning,” in 2010 IEEE Wireless
Communication and Networking Conference, April 2010, pp. 1–6.
[5] X. Chen and J. Huang, “Spatial Spectrum Access Game: Nash Equilibria
and Distributed Learning,” in Proc. of the 13th ACM MobiHoc. New
York, NY, USA: ACM, 2012, pp. 205–214.
[6] T. Alpcan and T. Başar, “A hybrid systems model for power control
in multicell wireless data networks,” Performance Evaluation, vol. 57,
no. 4, pp. 477 – 495, 2004.
[7] L. Pavel, Game theory for control of optical networks. BirkhäuserSpringer Science, 2012.
[8] ——, “A noncooperative game approach to OSNR optimization in
optical networks,” IEEE Trans. on Automatic Control, vol. 51, no. 5,
pp. 848 – 852, 2006.
[9] 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.
[10] J. Wang and N. Elia, “A control perspective for centralized and distributed convex optimization,” in Proc. of the 50th IEEE CDC-ECC,
Dec 2011, pp. 3800–3805.

[11] N. Li and J. R. Marden, “Designing games for distributed optimization,”
IEEE Journal of Selected Topics in Signal Processing, vol. 7, no. 2, pp.
230–242, 2013.
[12] H. Yin, U. Shanbhag, and P. G. Mehta, “Nash Equilibrium Problems
With Scaled Congestion Costs and Shared Constraints,” IEEE Trans. on
Automatic Control, vol. 56, no. 7, pp. 1702–1708, 2011.
[13] T. Alpcan and T. Başar, Distributed Algorithms for Nash Equilibria of
Flow Control Games. Birkhäuser Boston, 2005, pp. 473–498.
[14] J. Koshal, A. Nedic, and U. Shanbhag, “A gossip algorithm for aggregative games on graphs,” in Proc. of the 51st IEEE CDC, Dec 2012, pp.
4840–4845.
[15] S. Grammatico, F. Parise, M. Colombino, and J. Lygeros, “Decentralized
Convergence to Nash Equilibria in Constrained Deterministic Mean
Field Control,” IEEE Trans. on Automatic Control, vol. 61, no. 11, pp.
3315–3329, 2016.
[16] F. Salehisadaghiani and L. Pavel, “Distributed Nash equilibrium seeking:
A gossip-based algorithm,” Automatica, vol. 72, pp. 209 – 216, 2016.
[17] ——, “Distributed Nash Equilibrium seeking via the Alternating Direction Method of Multipliers,” in the 20th IFAC World Congress, to
appear, 2017.
[18] W. Shi and L. Pavel, “LANA: an ADMM-like Nash Equilibrium
seeking algorithm in decentralized environment,” in American Control
Conference, to appear, 2017.
[19] K. Arrow, L. Hurwitz, and H. Uzawa, A gradient method for approximating saddle points and constrained maxima. Rand Corporation,
United Staes Army Air Forces, 1951.
[20] ——, Studies in linear and non-linear programming. Stanford University Press, Stanford, California, 1958.
[21] S. Flåm, “Equilibrium, evolutionary stability and gradient dynamics,”
International Game Theory Review, vol. 4, no. 04, pp. 357–370, 2002.
[22] J. S. Shamma and G. Arslan, “Dynamic fictitious play, dynamic gradient
play, and distributed convergence to Nash equilibria,” IEEE Trans. on
Automatic Control, vol. 50, no. 3, pp. 312–327, 2005.
[23] B. Gharesifard and J. Cortes, “Distributed convergence to Nash equilibria in two-network zero-sum games,” Automatica, vol. 49, no. 6, pp.
1683 – 1692, 2013.
[24] A.Nagurney and D. Zhang, Projected Dynamical Systems and Variational Inequalities with Applications, ser. Innovations in Financial
Markets and Institutions. Springer US, 1996.
[25] J.-B. Hiriart-Urruty and C. Lemaréchal, Fundamentals of Convex Analysis. Springer, 2001.
[26] C. Godsil and G. Royle, Algebraic Graph Theory, ser. Graduate Texts
in Mathematics. Springer New York, 2001.
[27] G. Hines, M. Arcak, and A. Packard, “Equilibrium-independent passivity: A new definition and numerical certification,” Automatica, vol. 47,
no. 9, pp. 1949 – 1956, 2011.
[28] M. Bürger, D. Zelazo, and F. Allgöwer, “Duality and network theory
in passivity-based cooperative control,” Automatica, vol. 50, no. 8, pp.
2051 – 2061, 2014.
[29] M. Bürger and C. D. Persis, “Dynamic coupling design for nonlinear
output agreement and time-varying flow control,” Automatica, vol. 51,
pp. 210 – 222, 2015.
[30] A. Pavlov and L. Marconi, “Incremental passivity and output regulation,”
System & Control Letters, vol. 57, pp. 400 – 409, 2008.
[31] T. Başar and G. Olsder, Dynamic Noncooperative Game Theory: Second
Edition, ser. Classics in Applied Mathematics. SIAM, 1999.
[32] F. Facchinei and J. Pang, Finite-Dimensional Variational Inequalities
and Complementarity Problems, ser. Springer Series in Operations
Research and Financial Engineering. Springer New York, 2007.
[33] G. Scutari, F. Facchinei, J. S. Pang, and D. P. Palomar, “Real and Complex Monotone Communication Games,” IEEE Trans. on Information
Theory, vol. 60, no. 7, pp. 4197–4231, 2014.
[34] S. Li and T. Başar, “Distributed Algorithms for the Computation of
Noncooperative Equilibria,” Automatica, vol. 23, no. 4, pp. 523–533,
1987.
[35] H. Khalil, Nonlinear Systems. Prentice Hall, 2002.
[36] M. Arcak, “Passivity as a Design Tool for Group Coordination,” IEEE
Trans. on Automatic Control, vol. 52, no. 8, pp. 1380–1390, 2007.
[37] B. Brogliato, A. Daniilidis, C. Lemaréchal, and V. Acary, “On the
equivalence between complementarity systems, projected systems and
differential inclusions,” Systems & Control Letters, vol. 55, pp. 45–51,
2006.
[38] J.-P. Aubin and A. Cellina, Differential Inclusions. Springer, Heidelberg, 1984.
[39] M. d. B. P. DeLellis and G. Russo, “On QUAD, Lipschitz, and
contracting vector fields for consensus and synchronization of networks,”
IEEE Trans. on Circuits and Systems, vol. 58, no. 3, pp. 576–583, 2011.

