IEEE TRANSACTIONS ON AUTOMATIC CONTROL

1

Nash Equilibrium Computation in Subnetwork
Zero-Sum Games with Switching Communications

arXiv:1312.7050v2 [] 26 Nov 2015

Youcheng Lou, Yiguang Hong, Senior Member, IEEE, Lihua Xie, Fellow, IEEE, Guodong Shi
and Karl Henrik Johansson, Fellow, IEEE

Abstract—In this paper, we investigate a distributed Nash
equilibrium computation problem for a time-varying multiagent network consisting of two subnetworks, where the two
subnetworks share the same objective function. We first propose
a subgradient-based distributed algorithm with heterogeneous
stepsizes to compute a Nash equilibrium of a zero-sum game.
We then prove that the proposed algorithm can achieve a Nash
equilibrium under uniformly jointly strongly connected (UJSC)
weight-balanced digraphs with homogenous stepsizes. Moreover,
we demonstrate that for weighted-unbalanced graphs a Nash
equilibrium may not be achieved with homogenous stepsizes
unless certain conditions on the objective function hold. We show
that there always exist heterogeneous stepsizes for the proposed
algorithm to guarantee that a Nash equilibrium can be achieved
for UJSC digraphs. Finally, in two standard weight-unbalanced
cases, we verify the convergence to a Nash equilibrium by
adaptively updating the stepsizes along with the arc weights in
the proposed algorithm.
Index Terms—Multi-agent systems, Nash equilibrium, weightunbalanced graphs, heterogeneous stepsizes, joint connection

I. I NTRODUCTION
In recent years, distributed control and optimization of
multi-agent systems have drawn much research attention due
to their broad applications in various fields of science, engineering, computer science, and social science. Various tasks
including consensus, localization, and convex optimization can
be accomplished cooperatively for a group of autonomous
agents via distributed algorithm design and local information
exchange [8], [9], [37], [14], [15], [20], [21], [22].
Distributed optimization has been widely investigated for
agents to achieve a global optimization objective by cooperating with each other [14], [15], [20], [21], [22]. Furthermore, distributed optimization algorithms in the presence of
adversaries have gained rapidly growing interest [3], [2], [23],
[30], [31]. For instance, a non-model based approach was
Recommended by Associate Editor D. Bauso. This work is supported by the
NNSF of China under Grant 71401163, 61333001, Beijing Natural Science
Foundation under Grant 4152057, National Research Foundation of Singapore
under grant NRF-CRP8-2011-03, Knut and Alice Wallenberg Foundation, and
the Swedish Research Council.
Y. Lou and Y. Hong are with Academy of Mathematics and Systems
Science, Chinese Academy of Sciences, Beijing 100190 China (e-mail:
louyoucheng@amss.ac.cn, yghong@iss.ac.cn)
L. Xie is with School of Electrical and Electronic Engineering, Nanyang
Technological University, Singapore, 639798 (email: elhxie@ntu.edu.sg)
G. Shi is with College of Engineering and Computer Science, The
Australian National University, Canberra, ACT 0200 Australia (email:
guodong.shi@anu.edu.au)
K. H. Johansson is with ACCESS Linnaeus Centre, School of Electrical
Engineering, Royal Institute of Technology, Stockholm 10044 Sweden (email: kallej@ee.kth.se)

proposed for seeking a Nash equilibrium of noncooperative
games in [30], while distributed methods to compute Nash
equilibria based on extreme-seeking technique were developed
in [31]. A distributed continuous-time set-valued dynamical
system solution to seek a Nash equilibrium of zero-sum games
was first designed for undirected graphs and then for weightbalanced directed graphs in [23]. It is worthwhile to mention
that, in the special case of additively separable objective
functions, the considered distributed Nash equilibrium computation problem is equivalent to the well-known distributed
optimization problem: multiple agents cooperatively minimize
a sum of their own convex objective functions [11], [12], [14],
[15], [17], [16], [18], [19], [24], [29].
One main approach to distributed optimization is based on
subgradient algorithms with each node computing a subgradient of its own objective function. Distributed subgradientbased algorithms with constant and time-varying stepsizes,
respectively, were proposed in [14], [15] with detailed convergence analysis. A distributed iterative algorithm that avoids
choosing a diminishing stepsize was proposed in [29]. Both deterministic and randomized versions of distributed projectionbased protocols were studied in [20], [21], [22].
In existing works on distributed optimization, most of the
results were obtained for switching weight-balanced graphs
because there usually exists a common Lyapunov function to
facilitate the convergence analysis in this case [14], [15], [18],
[23], [24]. Sometimes, the weight-balance condition is hard to
preserve in the case when the graph is time-varying and with
communication delays [38], and it may be quite restrictive
and difficult to verify in a distributed setting. However, in
the case of weight-unbalanced graphs, there may not exist a
common (quadratic) Lyapunov function or it may be very hard
to construct one even for simple consensus problems [10],
and hence, the convergence analysis of distributed problems
become extremely difficult. Recently, many efforts have been
made to handle the weight unbalance problem, though very
few results have been obtained on distributed optimization. For
instance, the effect of the Perron vector of the adjacency matrix
on the optimal convergence of distributed subgradient and dual
averaging algorithms were investigated for a fixed weightunbalanced graph in [39], [40]. Some methods were developed for the unbalanced graph case such as the reweighting
technique [39] (for a fixed graph with a known Perron vector)
and the subgradient-push methods [41], [42] (where each node
has to know its out-degree all the time). To our knowledge,
there are no theoretical results on distributed Nash equilibrium
computation for switching weight-unbalanced graphs.

IEEE TRANSACTIONS ON AUTOMATIC CONTROL

In this paper, we consider the distributed zero-sum game
Nash equilibrium computation problem proposed in [23],
where a multi-agent network consisting of two subnetworks,
with one minimizing the objective function and the other
maximizing it. The agents play a zero-sum game. The agents in
two different subnetworks play antagonistic roles against each
other, while the agents in the same subnetwork cooperate. The
objective of the network is to achieve a Nash equilibrium via
distributed computation based on local communications under
time-varying connectivity. The considered Nash equilibrium
computation problem is motivated by power allocation problems [23] and saddle point searching problems arising from
Lagrangian dual optimization problems [13], [18], [25], [26],
[27], [28]. The contribution of this paper can be summarized
as follows:
• We propose a subgradient-based distributed algorithm to
compute a saddle-point Nash equilibrium under timevarying graphs, and show that our algorithm with homogeneous stepsizes can achieve a Nash equilibrium under
uniformly jointly strongly connected (UJSC) weightbalanced digraphs.
• We further consider the weight-unbalanced case, though
most existing results on distributed optimization were
obtained for weight-balanced graphs, and show that distributed homogeneous-stepsize algorithms may fail in the
unbalanced case, even for the special case of identical
subnetworks.
• We propose a heterogeneous stepsize rule and study
how to cooperatively find a Nash equilibrium in general
weight-unbalanced cases. We find that, for UJSC timevarying digraphs, there always exist (heterogeneous) stepsizes to make the network achieve a Nash equilibrium.
Then we construct an adaptive algorithm to update the
stepsizes to achieve a Nash equilibrium in two standard
cases: one with a common left eigenvector associated
with eigenvalue one of adjacency matrices and the other
with periodically switching graphs.
The paper is organized as follows. Section II gives some
preliminary knowledge, while Section III formulates the distributed Nash equilibrium computation problem and proposes a
novel algorithm. Section IV provides the main results followed
by Section V that contains all the proofs of the results. Then
Section VI provides numerical simulations for illustration.
Finally, Section VII gives some concluding remarks.
Notations: | · | denotes the Euclidean norm, h·, ·i the Euclidean inner product and ⊗ the Kronecker product. B(z, ε)
+
is a ball with
P z the center and ε > 0 the radius, Sn =
{µ|µi > 0, ni=1 µi = 1} is the set of all n-dimensional
positive stochastic vectors. z ′ denotes the transpose of vector
z, Aij the i-th row and j-th column entry of matrix A and
diag{c1 , . . . , cn } the diagonal matrix with diagonal elements
c1 , ..., cn . 1 = (1, ..., 1)′ is the vector of all ones with
appropriate dimension.

2

A. Graph Theory
A digraph (directed graph) Ḡ = (V̄, Ē) consists of a node
set V̄ = {1, ..., n̄} and an arc set Ē ⊆ V̄ × V̄. Associated with graph Ḡ, there is a (weighted) adjacency matrix
Ā = (āij ) ∈ Rn̄×n̄ with nonnegative adjacency elements
āij , which are positive if and only if (j, i) ∈ Ē. Node j is
¯ Assume (i, i) ∈ Ē for
a neighbor of node i if (j, i) ∈ E.
i = 1, ..., n̄. A path in Ḡ from i1 to ip is an alternating
sequence i1 e1 i2 e2 · · · ip−1 ep−1 ip of nodes ir , 1 ≤ r ≤ p and
arcs er = (ir , ir+1 ) ∈ Ē, 1 ≤ r ≤ p − 1. Ḡ is said to be
bipartite if V̄ can be
S partitioned into two disjoint parts V̄1 and
V̄2 such that Ē ⊆ 2ℓ=1 (V̄ℓ × V̄3−ℓ ).
Consider a multi-agent network Ξ consisting of two subnetworks Ξ1 and Ξ2 with respective n1 and n2 agents. Ξ
is described by a digraph, denoted as G = (V, E), which
contains self-loops, i.e., (i, i) ∈ E for each i. Here G can
be partitioned into three digraphs: Gℓ = (Vℓ , Eℓ ) with Vℓ =
{ω1ℓ , ..., ωnℓ ℓ }, ℓS= 1, 2, and a bipartite
S Sgraph G⊲⊳ = (V, E⊲⊳ ),
where V = V1 V2 and E = E1 E2 E⊲⊳ . In other words,
Ξ1 and Ξ2 are described by the two digraphs, G1 and G2 ,
respectively, and the interconnection between Ξ1 and Ξ2 is
described by G⊲⊳ . Here G⊲⊳ is called bipartite without isolated
nodes if, for any i ∈ Vℓ , there is at least one node j ∈ V3−ℓ
such that (j, i) ∈ E for ℓ = 1, 2. Let Aℓ denote the adjacency
matrix of Gℓ , ℓ = 1, 2. Digraph Gℓ is strongly connected if
there is a path in Gℓ from i to j for any pair node i, j ∈ Vℓ . A
node is called a root node if there is at least a path from this
node to any other node. In the sequel, we still write i ∈ Vℓ
instead of ωiℓ ∈ Vℓ , ℓ = 1, 2 for simplicity if there is no
confusion.
Let Aℓ = (aij ,i,j∈Vℓ ) ∈ Rnℓ ×nℓ bePthe adjacencyP
matrix of
Gℓ . Graph Gℓ is weight-balanced if j∈Vℓ aij = j∈Vℓ aji
for i ∈ Vℓ ; and weight-unbalanced otherwise.
A vector is said to be stochastic if all its components are
nonnegative and the sum of its components is one. A matrix is
a stochastic matrix if each of its row vectors is stochastic. A
stochastic vector is positive if all its components are positive.
Let B = (bij ) ∈ Rn×n be a stochastic matrix. Define
GB = ({1, ..., n}, EB ) as the graph associated with B, where
(j, i) ∈ EB if and only if bij > 0 (its adjacency matrix
is B). According to Perron-Frobenius theorem [1], there is
a unique positive stochastic left eigenvector of B associated
with eigenvalue one if GB is strongly connected. We call this
eigenvector the Perron vector of B.
B. Convex Analysis

II. P RELIMINARIES

A set K ⊆ Rm is convex if λz1 + (1 − λ)z2 ∈ K for any
z1 , z2 ∈ K and 0 < λ < 1. A point z is an interior point of
K if B(z, ε) ⊆ K for some ε > 0. For a closed convex set K
in Rm , we can associate with any z ∈ Rm a unique element
PK (z) ∈ K satisfying |z − PK (z)| = inf y∈K |z − y|, where
PK is the projection operator onto K. The following property
for the convex projection operator PK holds by Lemma 1 (b)
in [15],

In this section, we give preliminaries on graph theory [4],
convex analysis [5], and Nash equilibrium.

|PK (y) − z| ≤ |y − z| for any y ∈ Rm and any z ∈ K. (1)

IEEE TRANSACTIONS ON AUTOMATIC CONTROL

3

A function ϕ(·) : Rm → R is (strictly) convex if ϕ(λz1 +
(1 − λ)z2 )(<) ≤ λϕ(z1 ) + (1 − λ)ϕ(z2 ) for any z1 6= z2 ∈
Rm and 0 < λ < 1. A function ϕ is (strictly) concave if
−ϕ is (strictly) convex. A convex function ϕ : Rm → R is
continuous.
For a convex function ϕ, v(ẑ) ∈ Rm is a subgradient of
ϕ at point ẑ if ϕ(z) ≥ ϕ(ẑ) + hz − ẑ, v(ẑ)i, ∀z ∈ Rm . For
a concave function ϕ, v(ẑ) ∈ Rm is a subgradient of ϕ at
ẑ if ϕ(z) ≤ ϕ(ẑ) + hz − ẑ, v(ẑ)i, ∀z ∈ Rm . The set of all
subgradients of (convex or concave) function ϕ at ẑ is denoted
by ∂ϕ(ẑ), which is called the subdifferential of ϕ at ẑ.
C. Saddle Point and Nash Equilibrium
A function φ(·, ·) : Rm1 × Rm2 → R is (strictly) convexconcave if it is (strictly) convex in first argument and (strictly)
concave in second one. Given a point (x̂, ŷ), we denote by
∂x φ(x̂, ŷ) the subdifferential of convex function φ(·, ŷ) at x̂
and ∂y φ(x̂, ŷ) the subdifferential of concave function φ(x̂, ·)
at ŷ.
A pair (x∗ , y ∗ ) ∈ X × Y is a saddle point of φ on X × Y
if
φ(x∗ , y) ≤ φ(x∗ , y ∗ ) ≤ φ(x, y ∗ ), ∀x ∈ X, y ∈ Y.
The next lemma presents a necessary and sufficient condition
to characterize the saddle points (see Proposition 2.6.1 in [33]).
Lemma 2.1: Let X ⊆ Rm1 , Y ⊆ Rm2 be two closed convex
sets. Then a pair (x∗ , y ∗ ) is a saddle point of φ on X × Y if
and only if
sup inf φ(x, y) = inf sup φ(x, y) = φ(x∗ , y ∗ ),

y∈Y x∈X

x∈X y∈Y

and x∗ is an optimal solution of optimization problem
minimize sup φ(x, y)

subject to x ∈ X,

(2)

y∈Y

while y ∗ is an optimal solution of optimization problem
maximize inf φ(x, y)
x∈X

subject to y ∈ Y.

(3)

From Lemma 2.1, we find that all saddle points of φ on
X × Y yield the same value. The next lemma can be obtained
from Lemma 2.1.
Lemma 2.2: If (x∗1 , y1∗ ) and (x∗2 , y2∗ ) are two saddle points
of φ on X × Y , then (x∗1 , y2∗ ) and (x∗2 , y1∗ ) are also saddle
points of φ on X × Y .
Remark 2.1: Denote by Z̄ the set of all saddle points of
function φ on X × Y , X̄ and Ȳ the optimal solution sets
of optimization problems (2) and (3), respectively. Then from
Lemma 2.1 it is not hard to find that if Z̄ is nonempty, then
X̄, Ȳ are nonempty, convex, and Z̄ = X̄ × Ȳ . Moreover, if
X and Y are convex, compact and φ is convex-concave, then
Z̄ is nonempty (see Proposition 2.6.9 in [33]).
The saddle point computation can be related to a zerosum game. In fact, a (strategic) game is described as a
triple (I, W, U), where I is the set of all players; W =
W1 × · · · × Wn , n is the number of players, Wi is the set of
actions available to player i; U = (u1 , . . . , un ), ui : W → R
is the payoff
Pn function of player i. The game is said to be zerosum if i=1 ui (wi , w−i ) = 0, where w−i denotes the actions

of all players other than i. A profile action w∗ = (w1∗ , . . . , wn∗ )
∗
∗
is said to be a Nash equilibrium if ui (wi∗ , w−i
) ≥ ui (wi , w−i
)
for each i ∈ V and wi ∈ Wi . The Nash equilibria set of a
two-person zero-sum game (n = 2, u1 + u2 = 0) is exactly
the saddle point set of payoff function u2 .
III. D ISTRIBUTED NASH E QUILIBRIUM C OMPUTATION
In this section, we introduce a distributed Nash equilibrium
computation problem and then propose a subgradient-based
algorithm as a solution.
Consider a network Ξ consisting of two subnetworks Ξ1
and Ξ2 . Agent i in Ξ1 is associated with a convex-concave
objective function fi (x, y) : Rm1 × Rm2 → R, and agent i
in Ξ2 is associated with a convex-concave objective function
gi (x, y) : Rm1 × Rm2 → R. Each agent only knows its own
objective function. The two subnetworks have a common sum
objective function with closed convex constraint sets X ⊆
Rm 1 , Y ⊆ Rm 2 :
U (x, y) =

n1
X
i=1

fi (x, y) =

n2
X

gi (x, y), x ∈ X, y ∈ Y.

i=1

Then the network is engaged
in a (generalized) zero-sum game

{Ξ1 , Ξ2 }, X × Y, u , where Ξ1 and Ξ2 are viewedPas two
n1
players, their
payoff functions are uΞ1 = − i=1
fi
Prespective
n2
and uΞ2 = i=1 gi . The objective of Ξ1 and Ξ2 is to achieve
a Nash equilibrium of the zero-sum game.
Remark 3.1: Despite that the contribution of this paper
is mainly theoretical, the considered model appears also in
applications. Here we illustrate that by discussing two practical
examples in the literature. In the first example, from [23]
note that for multiple Gaussian communication channels with
budget constrained signal power and noise levels, the capacity
of each channel is concave in signal power and convex in
noise level. Suppose there are two subnetworks, one of which
is more critical than the other. The critical subnetwork aims to
maximize its capacity by raising its transmission power while
the other aims to reduce the interference to other channels
by minimizing its transmission power (and thus the capacity).
The objective of the two subnetworks is then to find the Nash
equilibrium of the sum of all channels’ capacities, see Remark
3.1 in [23] for more details. For the second example, recall that
many practical problems (for example, distributed estimation,
resource allocation, optimal flow control) can be formulated
as distributed convex constrained optimization problems, in
which the associated Lagrangian function can be expressed as
a sum of individual Lagrangian functions, which are convex
in the optimization variable and linear (hence concave) in the
Lagrangian multiplier. Under Salter’s condition, the optimal
solutions can be found by computing the saddle-points of the
convex-concave Lagrangian function, or equivalently, the Nash
equilibrium of the corresponding zero-sum game, see [18] for
further discussions.
We next provide a basic assumption.
A1
Pn1(Existence of Saddle Points) For each stochastic vector µ,
i=1 µi fi has at least one saddle point over X × Y .
Clearly, A1 holds if X and Y are bounded (see Proposition
2.6.9 in [33] for other conditions guaranteeing the existence

IEEE TRANSACTIONS ON AUTOMATIC CONTROL

4

of saddle points). However, in this paper we do not require X
and Y to be bounded. Let
Z∗ = X∗ × Y ∗ ⊆ X × Y
denote the set of all saddle points of U on X × Y . Notice that
X ∗ × Y ∗ is also the set of Nash equilibria of the generalized
zero-sum game.
Denote the state of node i ∈ V1 as xi (k) ∈ Rm1 and the
state of node i ∈ V2 as yi (k) ∈ Rm2 at time k = 0, 1, . . . .
Definition 3.1: The network Ξ is said to achieve a Nash
equilibrium if, for any initial condition xi (0) ∈ Rm1 , i ∈ V1
and yi (0) ∈ Rm2 , i ∈ V2 , there are x∗ ∈ X ∗ and y ∗ ∈ Y ∗
such that
lim xi (k) = x∗ , i ∈ V1 ,

k→∞

lim yi (k) = y ∗ , i ∈ V2 .

where G1 (k) = (V1 , E1 (k)) and G2 (k) = (V2 , E2 (k)) are the
graphs to describe subnetworks Ξ1 and Ξ2 , respectively, and
G⊲⊳ (k) = (V, E⊲⊳ (k)) is the bipartite graph to describe the
interconnection between Ξ1 and
 Ξ2 at time k ≥ 0. For k2 >
k1 ≥ 0, denote by G⊲⊳ [k1 , k2 ) the union graph with node set

Sk2 −1
E⊲⊳ (s), and Gℓ [k1 , k2 ) the union graph
V and arc set s=k
1
Sk2 −1
Eℓ (s) for ℓ = 1, 2. The
with node set Vℓ and arc set s=k
1
following assumption on connectivity is made.
A2 (Connectivity) (i) The graph sequence G⊲⊳ is uniformly
jointly bipartite; namely, there is an integer T⊲⊳ > 0 such that
G⊲⊳ [k, k + T⊲⊳ ) is bipartite without isolated nodes for k ≥ 0.
(ii) For ℓ = 1, 2, the graph sequence Gℓ is uniformly jointly
strongly connected (UJSC);
 namely, there is an integer Tℓ > 0
such that Gℓ [k, k + Tℓ ) is strongly connected for k ≥ 0.
Remark 3.2: The agents in Ξℓ connect directly with those
in Ξ3−ℓ for all the time in [23], while the agents in two
subnetworks are connected at least once in each interval of
length T⊲⊳ according to A2 (i). In fact, it may be practically
hard for the agents of different subnetworks to maintain
communications all the time. Moreover, even if each agent
in Ξℓ can receive the information from Ξ3−ℓ , agents may just
send or receive once during a period of length T⊲⊳ to save
energy or communication cost.
To handle the distributed Nash equilibrium computation
problem, we propose a subgradient-based algorithm, called
Distributed Nash Equilibrium Computation Algorithm:


xi (k + 1) = PX x̂i (k) − αi,k q1i (k) ,





q1i (k) ∈ ∂x fi x̂i (k), x̆i (k) , i ∈ V1 ,

(4)

ŷ
(k)
+
β
q
(k)
,
y
(k
+
1)
=
P
i
i,k
2i
i
Y




q2i (k) ∈ ∂y gi y̆i (k), ŷi (k) , i ∈ V2
with

X

aij (k)xj (k), x̆i (k) =

X

aij (k)yj (k), y̆i (k) =

j∈Ni1 (k)

ŷi (k) =

j∈Ni2 (k)

which is the last time before k when node i ∈ Vℓ has at least
one neighbor in V3−ℓ .

k→∞

The interconnection in the network Ξ is time-varying and
modeled as three digraph sequences:



G1 = G1 (k) , G2 = G2 (k) , G⊲⊳ = G⊲⊳ (k) ,

x̂i (k) =

where αi,k > 0, βi,k > 0 are the stepsizes at time k, aij (k)
is the time-varying weight of arc (j, i), Niℓ (k) is the set of
neighbors in Vℓ of node i at time k, and

k̆i = max s|s ≤ k, Ni3−ℓ (s) 6= ∅ ≤ k,
(5)

X

aij (k̆i )yj (k̆i ),

X

aij (k̆i )xj (k̆i ),

j∈Ni2 (k̆i )

j∈Ni1 (k̆i )

Figure 1: The zero-sum game communication graph
Remark 3.3: When all objective functions fi , gi are additively separable, i.e., fi (x, y) = fi1 (x) + fi2 (y), gi (x, y) =
gi1 (x) + gi2 (y), the considered distributed Nash equilibrium
computation problem is equivalent to two separated distributed
optimization
problems with respective objective functions
Pn1 1
P
n2
2
f
(x),
i=1 i
i=1 gi (y) and constraint sets X, Y . In this
case, the set of Nash equilibria is given by
n2
n1
X
X
gi2 .
fi1 × arg max
X ∗ × Y ∗ = arg min
X

i=1

Y

i=1

∂x fi1 (x)

Since ∂x fi (x, y) =
and ∂y gi (x, y) = ∂y gi2 (y),
algorithm (4) becomes in this case the well-known distributed
subgradient algorithms [14], [15].
Remark 3.4: To deal with weight-unbalanced graphs, some
methods, the rescaling technique [34] and the push-sum protocols [35], [36], [38] have been proposed for average consensus
problems; reweighting the objectives [39] and the subgradientpush protocols [41], [42] for distributed optimization problems. Different from these methods, in this paper we propose
a distributed algorithm to handle weight-unbalanced graphs
when the stepsizes taken by agents are not necessarily the
same.
Remark 3.5: Different from the extreme-seeking techniques
used in [30], [31], our method uses the subgradient to compute
the Nash equilibrium.
The next assumption was also used in [14], [15], [18], [21].
A3 (Weight Rule) (i) ThereSis 0 < η < 1 such that aij (k) ≥ η
for all P
i, k and j ∈ Ni1 (k) Ni2 (k);
(ii) j∈N ℓ (k) aij (k) = 1 for all k and i ∈ Vℓ , ℓ = 1, 2;
P i
(iii) j∈N 3−ℓ (k̆i ) aij (k̆i ) = 1 for i ∈ Vℓ , ℓ = 1, 2.
i
Conditions (ii) and (iii) in A3 state that the information from
an agent’s neighbors is used through a weighted average. The
next assumption is about subgradients of objective functions.
A4 (Boundedness of Subgradients) There is L > 0 such that,
for each i, j,
[
|q| ≤ L, ∀q ∈ ∂x fi (x, y) ∂y gj (x, y), ∀x ∈ X, y ∈ Y.
Obviously, A4 holds if X and Y are bounded. A similar
bounded assumption has been widely used in distributed
optimization [12], [13], [14], [15].

IEEE TRANSACTIONS ON AUTOMATIC CONTROL

Note that the stepsize in our algorithm (4) is heterogenous,
i.e., the stepsizes may be different for different agents, in
order to deal with general unbalanced cases. One challenging
problem is how to select the stepsizes {αi,k } and {βi,k }. The
homogenous stepsize case is to set αi,k = βj,k = γk for
i ∈ V1 , j ∈ V2 and all k, where
follows.
P∞{γk } is given as P
∞
A5 {γk } is non-increasing, k=0 γk = ∞ and k=0 γk2 <
∞.
P
P∞ 2
Conditions ∞
k=0 γk = ∞ and
k=0 γk < ∞ in A5 are
well-known in homogeneous stepsize selection for distributed
subgradient algorithms for distributed optimization problems
with weight-balanced graphs, e.g., [15], [16], [18].
Remark 3.6: While weight-balanced graphs are considered
in [14], [15], [18], [23], [24], we consider general (weightunbalanced) digraphs, and provide a heterogeneous stepsize
design method for the desired Nash equilibrium convergence.
IV. M AIN R ESULTS
In this section, we start with homogeneous stepsizes to
achieve a Nash equilibrium for weight-balanced graphs (in
Section IV.A). Then we focus on a special weight-unbalanced
case to show how a homogeneous-stepsize algorithm may
fail to achieve our aim (in Section IV.B). Finally, we show
that the heterogeneity of stepsizes can help us achieve a
Nash equilibrium in some weight-unbalanced graph cases (in
Section IV.C).
A. Weight-balanced Graphs
Here we consider algorithm (4) with homogeneous stepsizes
αi,k = βi,k = γk for weight-balanced digraphs. The following
result, in fact, provides two sufficient conditions to achieve a
Nash equilibrium under switching weight-balanced digraphs.
Theorem 4.1: Suppose A1–A5 hold and digraph Gℓ (k) is
weight-balanced for k ≥ 0 and ℓ = 1, 2. Then the multi-agent
network Ξ achieves a Nash equilibrium by algorithm (4) with
the homogeneous stepsizes {γk } if either of the following two
conditions holds:
(i) U is strictly convex-concave;
(ii) X ∗ × Y ∗ contains an interior point.
The proof can be found in Section V.B.
Remark 4.1: The authors in [23] developed a continuoustime dynamical system to solve the Nash equilibrium computation problem for fixed weight-balanced digraphs, and showed
that the network converges to a Nash equilibrium for a strictly
convex-concave differentiable sum objective function. Different from [23], here we allow time-varying communication
structures and a non-smooth objective function U . The same
result may also hold for the continuous-time solution in [23]
under our problem setup, but the analysis would probably be
much more involved.
B. Homogenous Stepsizes vs. Unbalanced Graphs
In the preceding subsection, we showed that a Nash equilibrium can be achieved with homogeneous stepsizes when
the graphs of two subnetworks are weight-balanced. Here we
demonstrate that the homogenous stepsize algorithm may fail

5

to guarantee the Nash equilibrium convergence for general
weight-unbalanced digraphs unless certain conditions about
the objective function hold.
Consider a special case, called the completely identical
subnetwork case, i.e., Ξ1 and Ξ2 are completely identical:
n1 = n2 , fi = gi , i = 1, ..., n1 ; A1 (k) = A2 (k),

G⊲⊳ (k) = (ωiℓ , ωi3−ℓ ), ℓ = 1, 2, i = 1, ..., n1 , k ≥ 0.

In this case, agents ωiℓ , ωi3−ℓ have the same objective function,
neighbor set and can communicate with each other at all times.
Each pair of agents ωiℓ , ωi3−ℓ can be viewed as one agent
labeled as “i”. Then algorithm (4) with homogeneous stepsizes
{γk } reduces to the following form:
(

P
xi (k + 1) = PX
j∈Ni1 (k) aij (k)xj (k) − γk q1i (k) ,

P
yi (k + 1) = PY
j∈Ni1 (k) aij (k)yj (k) + γk q2i (k) ,
(6)
for i = 1, ..., n1 , where q1i (k) ∈ ∂x fi (x̂i (k), yi (k)), q2i (k) ∈
∂y fi (xi (k), ŷi (k)).
Remark 4.2: Similar distributed saddle point computation
algorithms have been proposed in the literature, for example,
the distributed saddle point computation for the Lagrange
function of constrained optimization problems in [18]. In fact,
algorithm (6) can be used to solve the following distributed
saddle-point computation problem: consider a network Ξ1
consisting of n1 agents with node set V1 = {1, ..., n1 }, its
objective
is to seek a saddle point of the sum objective function
Pn1
i=1 fi (x, y) in a distributed way, where fi can only be
known by agent i. In (6), (xi , yi ) is the state of node “i”.
Moreover, algorithm (6) can be viewed as a distributed version
of the following centralized algorithm:
(

x(k + 1) = PX x(k) − γq1 (k) , q1 (k) ∈ ∂x U (x(k), y(k)),

y(k + 1) = PY y(k) + γq2 (k) , q2 (k) ∈ ∂y U (x(k), y(k)),

which was proposed in [13] to solve the approximate saddle
point problem with a constant stepsize.
We first show that, algorithm (4) with homogeneous stepsizes (or equivalently (6)) cannot seek the desired Nash
equilibrium though it is convergent, even for fixed weightunbalanced graphs.
Theorem 4.2: Suppose A1, A3–A5 hold, and fi , i =
1, ..., n1 are strictly convex-concave and the graph is fixed
with G1 (0) strongly connected. Then, with (6), all the agents
converge to the uniquePsaddle point, denoted as (~x, ~y), of
n1
an objective function
i=1 µi fi on X × Y , where µ =
′
(µ1 , . . . , µn1 ) is the Perron vector of the adjacency matrix
A1 (0) of graph G1 (0).
The proof is
the same as
of Theorem 4.1,
Pnalmost
Pnthat
1
2
by replacing P i=1
|xi (k) − x∗ |2 , Pi=1
|yi (k) − y ∗ |2 and
n1
n1
µi |yi (k) − ~y |2 and
µi |xi (k) − ~x|2 , i=1
U (x, y) with i=1
P
n1
i=1 µi fi (x, y), respectively. Therefore, the proof is omitted.
Although it is hard to achieve the desired Nash equilibrium
with the homogeneous-stepsize algorithm in general, we can
still achieve it in some cases. Here we can give a necessary
and sufficient condition to achieve a Nash equilibrium for any
UJSC switching digraph sequence.

IEEE TRANSACTIONS ON AUTOMATIC CONTROL

6

Theorem 4.3: Suppose A1, A3–A5 hold and fi , i = 1, ..., n1
are strictly convex-concave. Then the multi-agent network Ξ
achieves a Nash equilibrium by algorithm (6) for any UJSC
switching digraph sequence G1 if and only if fi , i = 1, ..., n1
have the same saddle point on X × Y .
The proof can be found in Section V.C.
Remark 4.3: The strict convexity-concavity of fi implies
that the saddle point of fi is unique. From the proof we
can find that the necessity of Theorem 4.3 does not require
that each objective function fi is strictly convex-concave, but
the
Pn1strict convexity-concavity of the sum objective function
i=1 fi suffices.
C. Weight-unbalanced Graphs
The results in the preceding subsections showed that the
homogenous-stepsize algorithm may not make a weightunbalanced network achieve its Nash equilibrium. Here we
first show the existence of a heterogeneous-stepsize design
to make the (possibly weight-unbalanced) network achieve a
Nash equilibrium.
Theorem 4.4: Suppose A1, A3, A4 hold and U is strictly
convex-concave. Then for any time-varying communication
graphs Gℓ , ℓ = 1, 2 and G⊲⊳ that satisfy A2, there always exist
stepsize sequences {αi,k } and {βi,k } such that the multi-agent
network Ξ achieves a Nash equilibrium by algorithm (4).
The proof is in Section V.D. In fact, it suffices to design
stepsizes αi,k and βi,k as follows:
αi,k =

1
1
γk , βi,k = i γk ,
αik
βk

(7)

where (α1k , . . . , αnk 1 )′ = φ1 (k + 1), (βk1 , . . . , βkn2 )′ = φ2 (k +
1), φℓ (k + 1) is the vector for which limr→∞ Φℓ (r, k + 1) :=
1(φℓ (k + 1))′ , Φℓ (r, k + 1) := Aℓ (r)Aℓ (r − 1) · · · Aℓ (k + 1),
ℓ = 1, 2, {γk } satisfies the following conditions:
lim γk

k→∞
∞
X

k=0

k−1
X

γs = 0, {γk } is non-increasing,

s=0

γk = ∞,

∞
X

(8)
γk2

< ∞.

k=0

Remark 4.4: The stepsize design in Theorem 4.4 is motivated by the following two ideas. On one hand, agents need
to eliminate the imbalance caused by the weight-unbalanced
graphs, which is done by {1/αik }, {1/βki }, while on the other
hand, agents also need to achieve a consensus within each
subnetwork and cooperative optimization, which is done by
{γk }, as in the balanced graph case.
Remark 4.5: Condition (8) can be satisfied by letting γk =
c
1
1 +ǫ for k ≥ 0, c > 0, b > 0, 0 < ǫ ≤ 2 . Moreover,
(k+b) 2

from the proof of Theorem 4.4 we find that, if the sets X and
Y are bounded, the system states are naturally bounded, and
then (8) can be relaxed as A5.
Clearly, the above choice of stepsizes at time k depend on the adjacency matrix sequences {A1 (s)}s≥k+1 and
{A2 (s)}s≥k+1 , which is not so practical. Therefore, we will
consider how to design adaptive algorithms to update the

stepsize sequences {αi,k } and {βi,k } such that the Nash equilibrium can be achieved, where the (heterogeneous) stepsizes
at time k just depend on the local information that agents can
obtain before time k.
Take
1
1
γk ,
(9)
αi,k = i γk , βi,k =
α̂k
β̂ki
where {γk } satisfies (8). The only difference between stepsize
selection rule (9) and (7) is that αik and βki are replaced with
α̂ik and β̂ki , respectively. We consider how to design distributed
adaptive algorithms for α̂i and β̂ i such that

α̂ik = α̂i aij (s), j ∈ Ni1 (s), s ≤ k ,

(10)
β̂ki = β̂ i aij (s), j ∈ Ni2 (s), s ≤ k ,
and



lim α̂ik − αik = 0, lim β̂ki − βki = 0.

k→∞

k→∞

(11)

Note that (α1k , . . . , αnk 1 )′ and (βk1 , . . . , βkn2 )′ are the Perron vectors of the two limits limr→∞ Φ1 (r, k + 1) and
limr→∞ Φ2 (r, k + 1), respectively.
The next theorem shows that, in two standard cases, we can
design distributed adaptive algorithms satisfying (10) and (11)
to ensure that Ξ achieves a Nash equilibrium. How to design
them is given in the proof.
Theorem 4.5: Consider algorithm (4) with stepsize selection
rule (9). Suppose A1–A4 hold, U is strictly convex-concave.
For the following two cases, with the adaptive distributed
algorithms satisfying (10) and (11), network Ξ achieves a Nash
equilibrium.
(i) For ℓ = 1, 2, the adjacency matrices Aℓ (k), k ≥ 0 have
a common left eigenvector with eigenvalue one;
(ii) For ℓ = 1, 2, the adjacency matrices Aℓ (k), k ≥ 0 are
switching periodically, i.e., there exist positive integers pℓ and
ℓ
two finite sets of stochastic matrices A0ℓ , ..., Apℓ −1 such that
Aℓ (rpℓ + s) = Asℓ for r ≥ 0 and s = 0, ..., pℓ − 1.
The proof is given in Section V.E.
Remark 4.6: Regarding case (i), note that for a fixed
graph, the adjacency matrices obviously have a common left
eigenvector. Moreover, periodic switching can be interpreted
as a simple scheduling strategy. At each time agents may
choose some neighbors to communicate with in a periodic
order.
Remark 4.7: In the case of a fixed unbalanced graph, the
optimization can also be solved by either reweighting the
objectives [39], or by the subgradient-push protocols [41],
[42], where the Perron vector of the adjacency matrix is
required to be known in advance or each agent is required
to know its out-degree. These requirements may be quite
restrictive in a distributed setting. Theorem 4.5 shows that,
in the fixed graph case, agents can adaptively learn the Perron
vector by the adaptive learning scheme and then achieve the
desired convergence without knowing the Perron vector and
their individual out-degrees.
When the adjacency matrices Aℓ (k) have a common left
eigenvector, the designed distributed adaptive learning strategy
(43) can guarantee that the differences between α̂ik = αii (k),

IEEE TRANSACTIONS ON AUTOMATIC CONTROL

β̂ki = βii (k) and the “true stepsizes” φ1i (k + 1), φ2i (k + 1)
asymptotically tend to zero. The converse is also true for
some cases. In fact, if the time-varying adjacency matrices are
switching within finite matrices and limk→∞ (αii (k) − φ1i (k +
1)) = 0, limk→∞ (βii (k) − φ2i (k + 1)) = 0, then we can show
that the finite adjacency matrices certainly have a common left
eigenvector.
Moreover, when the adjacency matrices have no common
left eigenvector, the adaptive learning strategy (43) generally
cannot make α̂ik , β̂ki asymptotically learn the true stepsizes and
then cannot achieve a Nash equilibrium. For instance, consider
the special distributed saddle-point computation algorithm
(6) with strictly convex-concave objective functions fi . Let
ᾱ = (ᾱ1 , ..., ᾱn1 )′ , α̂ = (α̂1 , ..., α̂n1 )′ be two different positive
stochastic vectors. Suppose A1 (0) = 1ᾱ′ and A1 (k) = 1α̂′
for k ≥ 1. In this case, αii (k) = ᾱi , φ1i (k + 1) = α̂i for all
k ≥ 0 and then (11) is not true. According to Theorem 4.2,
the learning strategy (43) can make (xi (k),P
yi (k)) converge
α̂i
1
to the (unique) saddle point of the function ni=1
ᾱi fi (x, y)
on
X
×
Y
,
which
is
not
necessarily
the
saddle
point of
Pn1
i=1 fi (x, y) on X × Y .
V. P ROOFS
In this section, we first introduce some useful lemmas and
then present the proofs of the theorems in last section.

7

Let b11 = b∗11 with 0 < b∗11 < 1. Clearly, there is a solution to
(12): b11 = b∗11 , 0 < brr = 1−(1−b∗11 )µ1 /µr < 1, 2 ≤ r ≤ n.
Then the conclusion follows.

The following lemma is about stochastic matrices, which
can be found from Lemma 3 in [7].
Lemma 5.4: Let B = (bij ) ∈ Rn×n be a stochastic matrix
and ~(µ) = max1≤i,j≤n |µi − µj |, µ = (µ1 , . . . , µn )′ ∈
Rn . Then
Pn~(Bµ) ≤ µ(B)~(µ), where µ(B) = 1 −
minj1 ,j2 i=1 min{bj1 i , bj2 i }, is called “the ergodicity coefficient” of B.
We next give a lemma about the transition matrix sequence
Φℓ (k, s) = Aℓ (k)Aℓ (k − 1) · · · Aℓ (s), k ≥ s, ℓ = 1, 2, where
(i), (ii) and (iv) are taken from Lemma 4 in [14], while (iii)
can be obtained from Lemma 2 in [14].
Lemma 5.5: Suppose A2 (ii) and A3 (i), (ii) hold. Then for
ℓ = 1, 2, we have
(i) The limit limk→∞ Φℓ (k, s) exists for each s;
(ii) There is a positive stochastic vector φℓ (s) =
ℓ
(φ1 (s), ..., φℓnℓ (s))′ such that limk→∞ Φℓ (k, s) = 1(φℓ (s))′ ;
(iii) For every i = 1, ..., nℓ and s, φℓi (s) ≥ η (nℓ −1)Tℓ ;
(iv) For every i, the entries Φℓ (k, s)ij , j = 1, ..., nℓ converge
to the same limit φℓj (s) at a geometric rate, i.e., for every
i = 1, ..., nℓ and all s ≥ 0,
Φℓ (k, s)ij − φℓj (s) ≤ Cℓ ρℓk−s
−Mℓ

for all k ≥ s and j = 1, ..., nℓ , where Cℓ = 2 1+η
, ρℓ =
1−η Mℓ
1

A. Supporting Lemmas
First of all, we introduce two lemmas. The first lemma is the
deterministic version of Lemma 11 on page 50 in [6], while
the second one is Lemma 7 in [15].
Lemma 5.1: P
Let {ak }, {bk } and {ck } be non-negative
∞
sequences with k=0 bk < ∞. If ak+1 ≤ ak + bk − ck holds
for any k, then limk→∞ ak is a finite number.
Lemma 5.2: Let 0 < λ < 1 and {ak }Pbe a positive sek
quence. If limk→∞ ak = 0, then limk→∞ r=0 λk−r ar = 0.
P∞
P∞ Pk
Moreover, if k=0 ak < ∞, then k=0 r=0 λk−r ar < ∞.
Next, we show some useful lemmas.
Lemma 5.3: For any µ ∈ Sn+ , there is a stochastic matrix
B = (bij ) ∈ Rn×n such that GB is strongly connected and
µ′ B = µ′ .
Proof: Take µ = (µ1 , . . . , µn )′ ∈ Sn+ . Without loss of
generality, we assume µ1 = min1≤i≤n µi (otherwise we can
rearrange the index of agents). Let B be a stochastic matrix
such that the graph GB associated with B is a directed cycle:
1en n · · · 2e1 1 with er = (r + 1, r), 1 ≤ r ≤ n − 1 and
en = (1, n). Clearly, GB is strongly connected. Then all
nonzero entries of B are bii , bi(i+1) , 1 ≤ i ≤ n−1, bnn , bn1
and µ′ B = µ′ can be rewritten as b11 µ1 + (1 − bnn )µn = µ1 ,
(1 − brr )µr + b(r+1)(r+1) µr+1 = µr+1 , 1 ≤ r ≤ n − 1.
Equivalently,

(1 − b22 )µ2 = (1 − b11 )µ1



 (1 − b33 )µ3 = (1 − b11 )µ1
(12)
..

.



(1 − bnn )µn = (1 − b11 )µ1

(1 − η Mℓ ) Mℓ , and Mℓ = (nℓ − 1)Tℓ .
The following lemma shows a relation between the left
eigenvectors of stochastic matrices and the Perron vector of
the limit of their product matrix.
Lemma 5.6: Let {B(k)} be a sequence of stochastic matrices. Suppose B(k), k ≥ 0 have a common left eigenvector
µ corresponding to eigenvalue one and the associated graph
sequence {GB(k) } is UJSC. Then, for each s,
lim B(k) · · · B(s) = 1µ′ /(µ′ 1).

k→∞

Proof : Since µ is the common left eigenvector of B(r), r ≥
s associated with eigenvalue one, µ′ limk→∞ B(k) · · · B(s) =
limk→∞ µ′ B(k) · · · B(s) = µ′ . In addition, by Lemma 5.5,
for each s, the limit limk→∞ B(k) · · · B(s) := 1φ′ (s) exists.
Therefore, µ′ = µ′ (1φ′ (s)) = (µ′ 1)φ′ (s), which implies
(µ′ 1)φ(s) = µ. The conclusion follows.

Basically, the two dynamics of algorithm (4) are in the same
form. Let us check the first one,

xi (k + 1) = PX x̂i (k) − αi,k q1i (k) ,

(13)
q1i (k) ∈ ∂x fi x̂i (k), x̆i (k) , i ∈ V1 .

By treating the term containing yj (j ∈ V2 ) as “disturbance”,
we can transform (13) to a simplified model in the following
form with disturbance ǫi :
X
xi (k + 1) =
aij (k)xj (k) + ǫi (k), i ∈ V1 ,
(14)
j∈Ni1 (k)


where ǫi (k) = PX x̂i (k) + wi (k) − x̂i (k). It follows from
xj (k) ∈ X, the convexity of X and A3 (ii) that x̂i (k) =
P
j∈N 1 (k) aij (k)xj (k) ∈ X. Then from (1), |ǫi (k)| ≤ |wi (k)|.
i

IEEE TRANSACTIONS ON AUTOMATIC CONTROL

8

The next lemma is about a limit for the two subnetworks.
Denote
ᾱk = max αi,k , β̄k = max βi,k .
1≤i≤n1

1≤i≤n2

Lemma 5.7: Consider
A3 (ii) and
Pk−1 algorithm (4) withPk−1
A4. If limk→∞ ᾱk s=0 ᾱs = limk→∞ β̄k s=0 β̄s = 0,
then for any x, y, limk→∞ ᾱk max1≤i≤n1 |xi (k) − x| =
limk→∞ β̄k max1≤i≤n2 |yi (k) − y| = 0.
Proof : We will only show limk→∞ ᾱk max1≤i≤n1 |xi (k) −
x| = 0 since the other one about β̄k canPbe proved similarly.
k−1
At first, it follows from limk→∞ ᾱk s=0 ᾱs = 0 that
limk→∞ ᾱk = 0. From A4 we have |ǫi (k)| ≤ ᾱk L. Then
from (14) and A3 (ii) we obtain
max |xi (k + 1) − x| ≤ max |xi (k) − x| + ᾱk L, ∀k.

1≤i≤n1

1≤i≤n1

Therefore, max1≤i≤n1 |xi (k) − x| ≤ max1≤i≤n1 |xi (0) − x| +
Pk−1
L s=0
ᾱs and then, for each k,

ᾱk max |xi (k) − x| ≤ ᾱk max |xi (0) − x| + ᾱk
1≤i≤n1

1≤i≤n1

k−1
X

Therefore, for each k,
Φ1 (k, r + 1)ǫ(r) + ǫ(k). (15)

r=s

At the end of this section, we present three lemmas for
(4) (or (14) and the other one for y). The first lemma gives
an estimation for h1 (k) = max1≤i,j≤n1 |xi (k) − xj (k)| and
h2 (k) = max1≤i,j≤n2 |yi (k) − yj (k)| over a bounded interval.
Lemma 5.8: Suppose A2 (ii), A3 and A4 hold. Then for
ℓ = 1, 2 and any t ≥ 1, 0 ≤ q ≤ T ℓ − 1,
ℓ

hℓ (tT ℓ + q) ≤ (1 − η T )hℓ ((t − 1)T ℓ + q)
λℓr ,

1

1
TX
−1

ᾱr

r=0

1

1

≤ µ(Φ (T − 1, 0))h1 (0) + 2L

1
TX
−1

ᾱr

r=0

1

≤ (1 − η T )h1 (0) + 2L

1
TX
−1

ᾱr ,

r=0

Φℓ (k, s) = Aℓ (k)Aℓ (k − 1) · · · Aℓ (s), k ≥ s, ℓ = 1, 2.

+ 2L

1

h1 (T ) ≤ h1 (Φ (T − 1, 0)x(0)) + 2L

Recall transition matrix

tT ℓX
+q−1

so we have Φ1 (T 1 −1, 0)j0 i0 > 0. Because j0 is taken from V1
freely, Φ1 (T 1 − 1, 0)ji0 > 0 for j ∈ V1 . As a result, Φ1 (T 1 −
1
1, 0)ji0 ≥ η T for j ∈ V1 with A3 (i) and so µ(Φ1 (T 1 −
1
1, 0)) ≤ 1 − η T by the definition of ergodicity coefficient
given in Lemma 5.4. According to (15), the inequality ~(µ +
ν) ≤ ~(µ) + 2 maxi νi , Lemma 5.4 and A4,
1

x(k + 1) = A1 (k)x(k) + ǫ(k), k ≥ 0.

k−1
X

(D1 )r0 r1 > 0, (D2 )r1 r2 > 0 =⇒ (D1 D2 )r0 r2 > 0,

ᾱs L.

s=0

Taking the limit over both sides of the preceding inequality
yields the conclusion.

We assume without loss of generality that m1 = 1 in
the sequel of this subsection for notational simplicity. Denote
x(k) = (x1 (k), . . . , xn1 (k))′ , ǫ(k) = (ǫ1 (k), . . . , ǫn1 (k))′ .
Then system (14) can be written in a compact form:

x(k + 1) = Φ1 (k, s)x(s) +

node, say i0 , at least n1 − 1 times. Assume without loss
 of
generality that i0 is a root node of G1 [tT1 , (t+1)T1 −1] , t =
t0 , ..., tn1 −2 .
Take j0 6= i0 from V1 . It is not hard to show that there exist
a node set {j1 , ..., jq } and time set {k0 , ..., kq }, q ≤ n1 − 2
such that (jr+1 , jr ) ∈ E1 (kq−r ), 0 ≤ r ≤ q − 1 and (i0 , jq ) ∈
E1 (k0 ), where k0 < · · · < kq−1 < kq and all kr belong to
different intervals [tr T1 , (tr + 1)T1 − 1], 0 ≤ r ≤ n1 − 2.
Noticing that the diagonal elements of all adjacency matrices are positive, and moreover, for matrices D1 , D2 ∈ Rn1 ×n1
with nonnegative entries,

(16)

r=(t−1)T ℓ +q

where λ1r = ᾱr , λ2r = β̄r , T ℓ = (nℓ (nℓ − 2) + 1)Tℓ for a
constant Tℓ given in A2 and L as the upper bound on the
subgradients of objective functions in A4.
Proof: Here we only show the case of ℓ = 1 since the other one
can be proven in the same way. Consider n1 (n1 − 2) + 1 time
intervals [0, T1 − 1], [T1 , 2T1 − 1], ..., [n1 (n1 − 2)T1 , (n1 (n1 −
2) + 1)T1− 1]. By the definition of UJSC graph, G1 [tT1 , (t +
1)T1 −1] contains a root node for 0 ≤ t ≤ n1 (n1 −2). Clearly,
the set of the n1 (n1 − 2) + 1 root nodes contains at least one

which shows (16) for ℓ = 1, t = 1, q = 0. Analogously, we
can show (16) for ℓ = 1, 2 and t ≥ 1, 0 ≤ q ≤ T ℓ − 1.

Lemma P
5.9: Suppose A2 (ii), A3 P
and A4 hold.
∞
∞
2
2
If
<
< ∞, then
k=0 ᾱk
k=0 β̄k
P∞∞ and
P(i)
∞
β̄
h
(k)
<
∞;
ᾱ
h
(k)
<
∞,
k
2
k
1
k=0
k=0
(ii) If for each i, limk→∞ αi,k = 0 and limk→∞ βi,k = 0,
then the subnetworks Ξ1 and Ξ2 achieve a consensus, respectively, i.e., limk→∞ h1 (k) = 0, limk→∞ h2 (k) = 0.
Note that (i) is an extension of Lemma 8 (b) in [15]
dealing with weight-balanced graph sequence to general graph
sequence (possibly weight-unbalanced), while (ii) is about the
consensus within the subnetworks, and will be frequently used
in the sequel. This lemma can be shown by Lemma 5.8 and
similar arguments to the proof of Lemma 8 in [15], and hence,
the proof is omitted here.
The following provides the error estimation between agents’
states and their average.
Lemma 5.10: Suppose
hold, P
and {ᾱ(k)}, {β̄(k)}
PA2–A4
∞
∞
2
2
<
∞,
are non-increasing with k=0 ᾱ
k
k=0 β̄k < ∞. Then
P
∞
for each i ∈ V1 and j ∈ V2 , k=0 β̄k |x̆i (k) −
ȳ(k)| < ∞,
P
∞
1 Pn1
ᾱ
|y̆
(k)−x̄(k)|
<
∞,
where
x̄(k)
=
k
j
i=1 xi (k) ∈
k=0
n1
Pn2
X, ȳ(k) = n12 i=1
yi (k) ∈ Y .
Proof: We only need to show the first conclusion since the
second one can be obtained in the same way. At first, from
A3 (iii) and |yj (k̆i ) − ȳ(k̆i )| ≤ h2 (k̆i ) we have
∞
X

k=0

β̄k |x̆i (k) − ȳ(k̆i )| ≤

∞
X

k=0

β̄k h2 (k̆i ).

(17)

IEEE TRANSACTIONS ON AUTOMATIC CONTROL

9

Let {sir , r ≥ 0} be the set of all moments when Ni2 (sir ) 6= ∅.
Recalling the definition of k̆i in (5), k̆i = sirPwhen sir ≤ k <
si(r+1) . Since {β̄k } is non-increasing and ∞
k=0 β̄k h2 (k) <
∞ (by Lemma 5.9), we have
∞
X

β̄k h2 (k̆i ) ≤

k=0

=

∞
X

+ 2γk x̂i (k) − x, −q1i (k) + γk2 |q1i (k)|2 .

k=0

∞
X

≤ T⊲⊳

β̄sir |si(r+1) − sir |h2 (sir )
∞
X

β̄sir h2 (sir ) ≤ T⊲⊳

∞
X

β̄k h2 (k) < ∞,

k=0

where T⊲⊳ is the constantPin A2 (i). Thus, the preceding
∞
inequality and (17) imply k=0 β̄k |x̆i (k) − ȳ(k̆i )| < ∞.
Since yi (k) ∈ Y for all i and Y is convex, ȳ(k) ∈ Y . Then,
from the non-expansiveness property of the convex projection
operator,
|ȳ(k + 1) − ȳ(k)|

Pn2
i=1 PY (ŷi (k) + βi,k q2i (k)) − PY (ȳ(k))
=
n2
n2
X
1
ŷi (k) + βi,k q2i (k) − ȳ(k)
≤
n2 i=1
≤ h2 (k) + β̄k L.

(18)

Based on (18), the non-increasingness of {β̄k } and k̆i ≥ k −
T⊲⊳ + 1, we also have
β̄k |ȳ(k̆i ) − ȳ(k)| ≤

k=0

≤

β̄k

k=0

≤

≤

∞
X

k−1
X

β̄k

k−1
X

β̄k

h2 (r) +

k−1
X

β̄k h2 (k) +

k=0

∞
(T⊲⊳ − 1)L X

2

j∈Ni1 (k)


+ 2γk fi (x, x̆i (k)) − fi (x̂i (k), x̆i (k)) .

(20)

Again employing A4, |fi (x, y1 ) − fi (x, y2 )| ≤ L|y1 − y2 |,
|fi (x1 , y)−fi (x2 , y)| ≤ L|x1 −x2 |, ∀x, x1 , x2 ∈ X, y, y1 , y2 ∈
Y . This imply


(21)
|fi x, x̆i (k) − fi x, ȳ(k) | ≤ L|x̆i (k) − ȳ(k)|,

fi x̂i (k), x̆i (k) − fi x̄(k), ȳ(k)

≤ L |x̂i (k) − x̄(k)| + |x̆i (k) − ȳ(k)|

≤ L h1 (k) + |x̆i (k) − ȳ(k)| .
(22)

Hence, by (20), (21) and (22),
X
|xi (k + 1) − x|2 ≤
aij (k)|xj (k) − x|2
j∈N 1 (k)

i

+ 2γk (fi (x, ȳ(k) − fi x̄(k), ȳ(k))) + L2 γk2 + 2Lγk ei1 (k),
(23)

where ei1 (k) = h1 (k) + 2|x̆i (k) − ȳ(k)|.
PIt follows from the weight balance of G1 (k) and A3 (ii) that
i∈V1 aij (k) = 1 for all j ∈ V1 . Then, from (23), we have
n1
X

(T⊲⊳ − 1)L
2

∞
X

|xi (k + 1) − x|2 ≤

∞

k=0

β̄k2 < ∞,

k=0

where h2 (r) = β̄r = 0, r < 0. Since |x̆i (k)− ȳ(k)| ≤ |x̆i (k)−
ȳ(k̆i )| + |ȳ(k̆i ) − ȳ(k)|, the first conclusion follows.

Remark 5.1: From the proof we find that Lemma 5.10 still
holds when the non-increasing condition of {ᾱk } and {β̄k } is
replaced by that there are an integer T ∗ > 0 and c∗ > 0 such
that ᾱk+T ∗ ≤ c∗ ᾱk and β̄k+T ∗ ≤ c∗ β̄k for all k.

|xi (k) − x|2 + 2γk U (x, ȳ(k))

i=1

(24)

i=1

k=0

(T⊲⊳ − 1)L X 2
β̄k
2

n1
X

n1
X

ei1 (k).
− U (x̄(k), ȳ(k)) + n1 L2 γk2 + 2Lγk

β̄k2

β̄r2

k=0 r=k−T⊲⊳ +1
∞
X

≤ (T⊲⊳ − 1)

It is easy to see that | · | is a convex function from the
2
convexity of |·| and the convexity of scalar
P function h(c) = c .
2
From this and A3 (ii), |x̂i (k)−x| ≤ j∈N 1 (k) aij (k)|xj (k)−
i
x|2 . Moreover, since q1i (k) is a subgradient of fi (·, x̆i (k)) at
x̂i (k), hx − x̂i (k), q1i (k)i ≤ fi (x, x̆i (k)) − fi (x̂i (k), x̆i (k)).
Thus, based on (19) and A4,
X
|xi (k + 1) − x|2 ≤
aij (k)|xj (k) − x|2 + L2 γk2

i=1

r=k−T⊲⊳ +1

∞
LX

2

ȳ(r) − ȳ(r + 1)

r=k̆i

(h2 (r) + β̄r L)

r=k−T⊲⊳ +1

k=0

k−1
X

(h2 (r) + β̄r L)

∞
X

+

β̄k

r=k̆i

k=0

+

∞
X

k=0
k−1
X

(19)

2

r=0

∞
X

We complete the proof by the following two steps.
Step 1: We first show that the states of (4) are bounded.
Take (x, y) ∈ X × Y . By (4) and (1),
|xi (k + 1) − x|2 ≤ |x̂i (k) − γk q1i (k) − x|2 = |x̂i (k) − x|2

β̄k̆i h2 (k̆i )

r=0

∞
X

B. Proof of Theorem 4.1

Analogously,
n2
X

2

|yi (k + 1) − y| ≤

n2
X

|yi (k) − y|2 + 2γk (U (x̄(k), ȳ(k))

i=1

i=1

− U (x̄(k), y)) +

n2 L2 γk2

+ 2Lγk

n2
X

ei2 (k),

(25)

i=1

where ei2 (k) = h2 (k) + 2|y̆i (k) − x̄(k)|. Let (x, y) =
∗
(x∗ , y ∗ ) ∈ X P
× Y ∗ , which is nonempty
by A1. Denote
Pn2
n1
∗ ∗
ξ(k, x , y ) = i=1
|xi (k) − x∗ |2 + i=1
|yi (k) − y ∗ |2 . Then
adding (24) and (25) together leads to
ξ(k + 1, x∗ , y ∗ ) ≤ ξ(k, x∗ , y ∗ ) − 2γk Υ(k)
+ (n1 + n2 )L2 γk2 + 2Lγk

nℓ
2 X
X
ℓ=1 i=1

eiℓ (k),

(26)

IEEE TRANSACTIONS ON AUTOMATIC CONTROL

10

where
Υ(k) = U (x̄(k), y ∗ ) − U (x∗ , ȳ(k))
= U (x∗ , y ∗ ) − U (x∗ , ȳ(k)) + U (x̄(k), y ∗ ) − U (x∗ , y ∗ )
≥0

(27)

following from U (x∗ , y ∗ ) − U (x∗ , ȳ(k)) ≥ 0, U (x̄(k), y ∗ ) −
∗ ∗
U (x∗ , y ∗ ) ≥ 0 for k ≥ 0 since
P∞(x , y ) is a saddle point of
U on X × Y . Moreover, by k=0 γk2 < ∞ and Lemmas 5.9,
5.10,
∞
X

γk

k=0

nℓ
2 X
X

eiℓ (k) < ∞.

(28)

ℓ=1 i=1

P∞
Therefore, by virtue of k=0 γk2 < ∞ again, (28), (26) and
Lemma 5.1, limk→∞ ξ(k, x∗ , y ∗ ) is a finite number, denoted
as ξ(x∗ , y ∗ ). Thus, the conclusion follows.

Step 2: We next show that the limit points of all agents
satisfy certain objective function equations, and then prove
the Nash equilibrium convergence under either of the two
conditions: (i) and (ii).
As shows in Step 1, (xi (k), yi (k)), k ≥ 0 are bounded.
Moreover, it also follows from (26) that
2

k
X

γr Υ(r) ≤ ξ(0, x∗ , y ∗ ) + (n1 + n2 )L2

r=0

γr2

r=0

+ 2L

k
X
r=0

and then by

k
X

P∞

k=0

γr

nℓ
2 X
X

∞
X

ℓ=1 i=1

γk Υ(k) < ∞.

(29)

k=0

P∞
The stepsize condition
k=0 γk = ∞ and (29) imply lim inf k→∞ Υ(k) = 0. As a result, there is a subsequence {kr } such that limr→∞ U (x∗ , ȳ(kr )) = U (x∗ , y ∗ )
and limr→∞ U (x̄(kr ), y ∗ ) = U (x∗ , y ∗ ). Let (x̃, ỹ) be any
limit pair of {(x̄(kr ), ȳ(kr ))} (noting that the finite limit
pairs exist by the boundedness of system states). Because
U (x∗ , ·), U (·, y ∗ ) are continuous and the Nash equilibrium
point (x∗ , y ∗ ) is taken from X ∗ × Y ∗ freely, the limit pair
(x̃, ỹ) must satisfy that for any (x∗ , y ∗ ) ∈ X ∗ × Y ∗ ,
U (x∗ , ỹ) = U (x̃, y ∗ ) = U (x∗ , y ∗ ).

Taking the gradient with respect to x on both sides of (31)
yields 2n1 (x− x̀1 ) = 2n1 (x− x̀2 ), namely, x̀1 = x̀2 . Similarly,
we can show ỳ1 = ỳ2 . Thus, the limits, limk→∞ x̄(k) = x̀ ∈
X and limk→∞ ȳ(k) = ỳ ∈ Y , exist. Based on Lemma 5.9 (ii),
limk→∞ xi (k) = x̀, i ∈ V1 and limk→∞ yi (k) = ỳ, i ∈ V2 .
We claim that (x̀, ỳ) ∈ P
X ∗ × Y ∗P
. First it follows from
n1
∞
γ
(24) that, for
any
x
∈
X,
k
i=1
k=0

P U (x̄(k), ȳ(k)) −
U (x, ȳ(k)) < ∞. Moreover, recalling ∞
k=0 γk = ∞, we
obtain

lim inf U (x̄(k), ȳ(k)) − U (x, ȳ(k)) ≤ 0.
(32)
k→∞

eiℓ (r)

γk2 < ∞ and (28) we have
0≤

limk→∞ ξ(k, x∗ , y ∗ ) = ξ(x∗ , y ∗ ) as given in Step 1, so
ξ(x∗ , y ∗ ) = limr→∞ ξ(kr , x∗ , y ∗ ) = 0, which in return
implies limk→∞ xi (k) = x∗ , i ∈ V1 and limk→∞ yi (k) = y ∗ ,
i ∈ V2 .
(ii). In Step 1, we proved limk→∞ ξ(k, x∗ , y ∗ ) = ξ(x∗ , y ∗ )
for any (x∗ , y ∗ ) ∈ X ∗ × Y ∗ . We check the existence of the
two limits limk→∞ x̄(k) and limk→∞ ȳ(k). Let (x+ , y + ) be
an interior point of X ∗ × Y ∗ for which B(x+ , ε) ⊆ X ∗ and
B(y + , ε) ⊆ Y ∗ for some ε > 0. Clearly, any two limit pairs
(x̀1 , ỳ1 ), (x̀2 , ỳ2 ) of {(x̄(k), ȳ(k))} must satisfy n1 |x̀1 − x|2 +
n2 |ỳ1 − y|2 = n1 |x̀2 − x|2 + n2 |ỳ2 − y|2 , ∀x ∈ B(x+ , ε), y ∈
B(y + , ε). Take y = y + . Then for any x ∈ B(x+ , ε),

n1 |x̀1 − x|2 = n1 |x̀2 − x|2 + n2 |ỳ2 − y + |2 − |ỳ1 − y + |2 .
(31)

(30)

We complete the proof by discussing the proposed two
sufficient conditions: (i) and (ii).
(i). For the strictly convex-concave function U , we claim
that X ∗ × Y ∗ is a single-point set. If it contains two different
points (x∗1 , y1∗ ) and (x∗2 , y2∗ ) (without loss of generality, assume
x∗1 6= x∗2 ), it also contains point (x∗2 , y1∗ ) by Lemma 2.2. Thus,
U (x∗1 , y1∗ ) ≤ U (x, y1∗ ) and U (x∗2 , y1∗ ) ≤ U (x, y1∗ ) for any
x ∈ X, which yields a contradiction since U (·, y1∗ ) is strictly
convex and then the minimizer of U (·, y1∗ ) is unique. Thus,
X ∗ × Y ∗ contains only one single-point (denoted as (x∗ , y ∗ )).
Then x̃ = x∗ , ỹ = y ∗ by (30). Consequently, each limit pair
of {(x̄(kr ), ȳ(kr ))} is (x∗ , y ∗ ), i.e., limr→∞ x̄(kr ) = x∗ and
limr→∞ ȳ(kr ) = y ∗ . By Lemma 5.9, limr→∞ xi (kr ) = x∗ ,
i ∈ V1 and limr→∞ yi (kr ) = y ∗ , i ∈ V2 . Moreover,

Then U (x̀, ỳ) − U (x, ỳ) ≤ 0 for all x ∈ X due to
limk→∞ x̄(k) = x̀, limk→∞ ȳ(k) = ỳ, the continuity of U ,
and (32). Similarly, we can show U (x̀, y) − U (x̀, ỳ) ≤ 0 for
all y ∈ Y . Thus, (x̀, ỳ) is a saddle point of U on X × Y ,
which implies (x̀, ỳ) ∈ X ∗ × Y ∗ .
Thus, the proof is completed.

C. Proof of Theorem 4.3

(Necessity) Let (x∗ , y ∗ ) be the unique saddle point of
strictly convex-concave function U on X × Y . Take µ =
(µ1 , . . . , µn1 )′ ∈ Sn+1 . By Lemma 5.3 again, there is a
stochastic matrix A1 such that µ′ A1 = µ′ and GA1 is strongly
connected. Let G1 = {G1 (k)} be the graph sequence of
algorithm (4) with G1 (k) = GA1 for k ≥ 0 and A1 being
the adjacency matrix of G1 (k). Clearly, G1 is UJSC. On one
hand, by Proposition
Pn1 4.2, all agents converge to the unique
saddle point of
i=1 µi fi on X × Y . On the other hand,
the necessity condition states that limk→∞ xi (k) = x∗ and
limk→∞ yi (k) =Py ∗ for i = 1, ..., n1 . Therefore, (x∗ , y ∗ ) is a
1
saddle point of ni=1
µi fi on X × Y .
Because µ is taken from Sn+1 freely, we have that, for any
µ ∈ Sn+1 , x ∈ X, y ∈ Y ,
n1
X
i=1

µi fi (x∗ , y) ≤

n1
X
i=1

µi fi (x∗ , y ∗ ) ≤

n1
X

µi fi (x, y ∗ ). (33)

i=1

We next show by contradiction that, given any i = 1, ..., n1 ,
fi (x∗ , y ∗ ) ≤ fi (x, y ∗ ) for all x ∈ X. Hence suppose there are i0 and x̂ ∈ X such that fi0 (x∗ , y ∗ ) >
∗
fP
i0 (x̂, y ). Let µi , i 6= i0 be sufficiently small such that
µ
∗ ∗
< 2i0 (fi0 (x∗ , y ∗ ) − fi0 (x̂, y ∗ )) and
i6=i0 µi fi (x , y )

IEEE TRANSACTIONS ON AUTOMATIC CONTROL

11

µ

µi fi (x̂, y ∗ ) < 2i0 (fi0 (x∗ , y ∗ ) − fi0 (x̂, y ∗ )). Conse
Pn1
µ
quently, i=1
µi fi (x∗ , y ∗ ) > 2i0 fi0 (x∗ , y ∗ )+ fi0 (x̂, y ∗ ) >
P
n1
∗
i=1 µi fi (x̂, y ), which contradicts the second inequality of
(33). Thus, fi (x∗ , y ∗ ) ≤ fi (x, y ∗ ) for all x ∈ X. Analogously,
we can show from the first inequality of (33) that for each
i, fi (x∗ , y) ≤ fi (x∗ , y ∗ ) for all y ∈ Y . Thus, we obtain
that fi (x∗ , y) ≤ fi (x∗ , y ∗ ) ≤ fi (x, y ∗ ), ∀x ∈ X, y ∈ Y, or
equivalently, (x∗ , y ∗ ) is the saddle point of fi on X × Y .
(Sufficiency) Let (x∗ , y ∗ ) be the unique saddle point of
fi , i = 1, ..., n1 on X × Y . Similar to (23), we have
X
|yi (k + 1) − y ∗ |2 ≤
aij (k)|yj (k) − y ∗ |2
P

i6=i0

j∈Ni1 (k)

D. Proof of Theorem 4.4
We design the stepsizes αi,k and βi,k as that given before
Remark 4.4. First by Lemma 5.5 (i) and (ii), the limit
limr→∞ Φℓ (r, k) = 1(φℓ (k))′ exists for each k. Let (x∗ , y ∗ )
be the unique Nash equilibrium. From (23) we have
X
|xi (k + 1) − x∗ |2 ≤
aij (k)|xj (k) − x∗ |2
j∈Ni1 (k)

+ 2αi,k (fi (x∗ , ȳ(k)) − fi (x̄(k), ȳ(k)))

+ L2 α2i,k + 2Lαi,k ei1 (k).
Analogously,

2L2 γk2

+
+ 2Lγk (u1 (k) + u2 (k))
= ζ(k) + 2γk max (fi (x∗ , ȳ(k)) − fi (x∗ , y ∗ )
1≤i≤n1


+ 2βi,k gi (x̄(k), ȳ(k)) − gi (x̄(k), y ∗ )
2
+ L2 βi,k
+ 2Lβi,k ei2 (k).

(35)

∗ 2

where ζ(k) = max1≤i≤n1 (|xi (k) − x | + |yi (k) − y | ),
u1 (k) = h1 (k) + 2h2 (k). Since fi (x∗ , ȳ(k)) − fi (x∗ , y ∗ ) ≤ 0
and fi (x∗ , y ∗ ) − fi (x̄(k), y ∗ ) ≤ 0 for all i, k, the second term
in (35) is non-positive. By Lemma 5.1,
lim ζ(k) = ζ ∗ ≥ 0

k→∞

for a finite number ζ , which implies that (xi (k), yi (k)), k ≥ 0
are bounded.
Denote ℘(k) = min1≤i≤n1 (fi (x∗ , y ∗ ) − fi (x∗ , ȳ(k)) +
fi (x̄(k), y ∗ ) − fi (x∗ , y ∗ )). From (35), we also have
γl ℘(l) ≤ ζ(0) − ζ(k + 1) + 2L

l=0

k
X

+ 6L

ϑℓ (k) = (ϑℓ1 (k), . . . , ϑℓnℓ (k))′ ,
ϑ1i (k) = fi (x̄(k), ȳ(k)) − fi (x∗ , ȳ(k)),
ϑ2i (k) = gi (x̄(k), y ∗ ) − gi (x̄(k), ȳ(k));
eℓ (k) = (e1ℓ (k), . . . , enℓ ℓ (k))′ .
Then it follows from (37) and (38) that
ψ ℓ (k + 1) ≤ Aℓ (k)ψ ℓ (k) − 2γk Λℓk ϑℓ (k)
+ δ∗2 L2 γk2 1 + 2δ∗ Lγk eℓ (k),
where δ∗ = supi,k {1/αik , 1/βki }. By Lemma 5.5 (iii), αik ≥
η (n1 −1)T1 , βki ≥ η (n2 −1)T2 , ∀i, k and then δ∗ is a finite
number. Therefore,
ψ ℓ (k + 1) ≤ Φℓ (k, r)ψ ℓ (r) − 2

γl2

l=0

k
X

n 1
n 1
1 o
1 o
Λ1k = diag 1 , . . . , n1 , Λ2k = diag 1 , . . . , n2 ;
αk
αk
βk
βk
ℓ
ℓ
ℓ
′
ψ (k) = (ψ1 (k), . . . , ψnℓ (k)) , ℓ = 1, 2,

(36)

∗

0≤2

Denote

∗ 2

2

(38)

ψi1 (k) = |xi (k) − x∗ |2 , ψi2 (k) = |yi (k) − y ∗ |2 ;

+ fi (x∗ , y ∗ ) − fi (x̄(k), y ∗ )) + 2L2 γk2
+ 6Lγk (h1 (k) + h2 (k)),

k
X

aij (k)|yj (k) − y ∗ |2

j∈Ni2 (k)

where u2 (k) = 2h1 (k) + h2 (k). Merging (23) and (34) gives
1≤i≤n1

X

|yi (k + 1) − y ∗ |2 ≤


+ 2γk fi (x̄(k), ȳ(k)) − fi (x̄(k), y ∗ ) + L2 γk2 + 2Lγk u2 (k),
(34)
ζ(k + 1) ≤ ζ(k) + 2γk max (fi (x∗ , ȳ(k)) − fi (x̄(k), y ∗ ))

(37)

γl (h1 (l) + h2 (l)), k ≥ 0,

l=0

P∞

and
P∞hence 0 ≤ k=0 γk ℘(k) < ∞. The stepsize condition
k=0 γk = ∞ implies that there is a subsequence {kr } such
that
lim ℘(kr ) = 0.
r→∞

k−1
X

γs Φℓ (k, s + 1)Λℓs ϑℓ (s)

s=r

+ δ∗2 L2

k
X

γs2 1 + 2δ∗ L

s=r

k−1
X

γs Φℓ (k, s + 1)eℓ (s)

s=r

− 2γk Λℓk ϑℓ (k) + 2δ∗ Lγk eℓ (k).

(39)

Then (39) can be written as
ψ ℓ (k + 1)
≤ Φℓ (k, r)ψ ℓ (r) − 2

k−1
X

γs 1(φℓ (s + 1))′ Λℓs ϑℓ (s)

s=r

We assume without loss of generality that limr→∞ x̄(kr ) =
x́, limr→∞ ȳ(kr ) = ý for some x́, ý (otherwise we can find
a subsequence of {kr } recalling the boundedness of system
states). Due to the finite number of agents and the continuity
of fi s, there exists i0 such that fi0 (x∗ , y ∗ ) = fi0 (x∗ , ý) and
fi0 (x́, y ∗ ) = fi0 (x∗ , y ∗ ). It follows from the strict convexityconcavity of fi0 that x́ = x∗ , ý = y ∗ .
Since the consensus is achieved within two subnetworks,
limr→∞ xi (kr ) = x∗ and limr→∞ yi (kr ) = y ∗ , which leads
to ζ ∗ = 0 based on (36). Thus, the conclusion follows.


+ δ∗2 L2

k
X
s=r

+2

k−1
X
s=r

γs2 1 + 2δ∗ L

k−1
X

γs 1(φℓ (s + 1))′ eℓ (s)

s=r


γs 1(φℓ (s + 1))′ − Φℓ (k, s + 1) Λℓs ϑℓ (s)

− 2γk Λℓk ϑℓ (k) + 2δ∗ Lγk eℓ (k)
+ 2δ∗ L

k−1
X
s=r


γs Φℓ (k, s + 1) − 1(φℓ (s + 1))′ eℓ (s).

(40)

IEEE TRANSACTIONS ON AUTOMATIC CONTROL

12

The subsequent proof is given as follows. First, we show
that the designed stepsizes (7) can eliminate the imbalance
caused by the weight-unbalanced graphs (see the second term
in (40)), and then we prove that all the terms from the third
one to the last one in (40) is summable based on the geometric
rate convergence of transition matrices. Finally, we show the
desired convergence based on inequality (40), as (26) for the
weight-balance case in Theorem 4.1.
Clearly, 1(φℓ (s + 1))′ Λℓs = 11′ , ℓ = 1, 2. From Lemma 5.5
(iv) we also have that Φℓ (k, s)ij − φℓj (s) ≤ Cρk−s for ℓ =
1, 2, every i = 1, ..., nℓ , s ≥ 0, k ≥ s, and j = 1, ..., nℓ , where
C = max{C1 , C2 }, 0 < ρ = max{ρ1 , ρ2 } < 1. Moreover, by
A4, |ϑ1i (s)| = |fi (x̄(s), ȳ(s)) − fi (x∗ , ȳ(s))| ≤ L|x̄(s) − x∗ |
for i ∈ V1 , and |ϑ2i (s)| = |fi (x̄(s), y ∗ ) − fi (x̄(s), ȳ(s))| ≤
L|ȳ(s) − y ∗ | for i ∈ V2 . Based on these observations,
multiplying n1ℓ 1′ on the both sides of (40) and taking the sum
over ℓ = 1, 2 yield
2
2
X
X
1 ′ ℓ
1 ′ ℓ
1 ψ (k + 1) ≤
1 Φ (k, r)ψ ℓ (r)
nℓ
nℓ
ℓ=1

ℓ=1

−2

k−1
X
s=r

+ 2δ∗ L

γs

nℓ
2 X
X

ϑℓi (s)

ℓ=1 i=1
nℓ
k−1
2 X
X X

γs

s=r

+

2δ∗2 L2

k
X

ρk−s−1 γs ς(s)

ℓ=1

+ 2CLδ∗

γs ρk−s−1

s=r

:=

eiℓ (s)

(41)

ℓ=1 i=1

2
X
1 ′ ℓ
1 Φ (k, r)ψ ℓ (r)
nℓ
ℓ=1

−2

k−1
X
s=r

γs

nℓ
2 X
X

ϑℓi (s) + ̺(k, r),

(42)

ℓ=1 i=1

where ς(s) = max{|xi (s) − x∗ |, i ∈ V1 , |yj (s) − y ∗ |, j ∈ V2 },
̺(k, r) is the sum of all terms from the third one to the last
one in (41).
We next show limr→∞ supk≥r ̺(k, r) = 0. First by LemP2 Pnℓ
P
mas 5.9, 5.10 and Remark 5.1, ∞
ℓ=1
s=r γs
i=1 eiℓ (s) <
P2 P
ℓ
∞ and hence limk→∞ γk ℓ=1 ni=1
eiℓ (k) = 0. It follows
from 0 < ρ < 1 that for each k,
k−1
X
s=r

γs ρk−s−1

nℓ
2 X
X
ℓ=1 i=1

eiℓ (s) ≤

∞
X
s=r

γs

nℓ
2 X
X

k≥kl

P2
which implies limk→∞ ℓ=1 n1ℓ 1′ ψ ℓ (k) = 0. Therefore,
limk→∞ xi (k) = x∗ , i ∈ V1 and limk→∞ yi (k) = y ∗ , i ∈ V2 .
Thus, the proof is completed.


αii (0)

nℓ
2
X
1 X
eiℓ (k)
+ 2Lδ∗ γk ς(k) + 2δ∗ Lγk
nℓ i=1
nℓ
2 X
X

ℓ=1

+ sup ̺(k, kl ) ≤ 2ε2 + ε,

i

s=r

k−1
X

ℓ=1

(i). In this case we design a dynamics for auxiliary states
αi = (αi1 , . . . , αin1 )′ ∈ Rn1 for i ∈ V1 and β i =
(β1i , . . . , βni 2 )′ ∈ Rn2 for i ∈ V2 to estimate the respective
desired stepsizes:
(
P
αi (k + 1) = j∈N 1 (k) aij (k)αj (k), k ≥ 0,
i
(43)
P
β i (k + 1) = j∈N 2 (k) aij (k)β j (k), k ≥ 0

eiℓ (s)

+ 2CLδ∗ (n1 + n2 )

2
2
X
X
1 ′ ℓ
1 ′ ℓ
1 ψ (k + 1) ≤
1 Φ (k, kl )ψ ℓ (kl )
nℓ
nℓ

E. Proof of Theorem 4.5

γs2

s=r

ℓ=1 i=1
k−1
X

procedures to the proof of Theorem 4.1, we can show that
there is a subsequence {kl } such that liml→∞ x̄(kl ) = x∗ ,
liml→∞ ȳ(kl ) = y ∗ .
P2
Now let us show limk→∞ ℓ=1 n1ℓ 1′ ψ ℓ (k) = 0. First
it follows from limr→∞ supk≥r ̺(k, r) = 0 that, for any
ε > 0, there is a sufficiently large l0 such that when
l ≥ l0 , supk≥kl ̺(k, kl ) ≤ ε. Moreover, since the consensus is
achieved within the two subnetworks, l0 can be selected sufficiently large such that |xi (kl0 )−x∗ | ≤ ε and |yi (kl0 )−y ∗ | ≤ ε
for each i. With (42), we have that, for each k ≥ kl ,

eiℓ (s) < ∞.

ℓ=1 i=1

Moreover, by Lemma 5.7,
limr→∞ γr ς(r) = 0, which imPk−1
ρk−s−1 γs ς(s) = 0 along with
plies limr→∞ supk≥r+1 s=r
Pk−1 k−s−1
1
sups≥r γs ς(s). From the precedγs ς(s) ≤ 1−ρ
s=r ρ
ing zero limit results, we have limr→∞ supk≥r ̺(k, r) = 0.
P2 Pnℓ ℓ
P∞
Then from (42)
γs ℓ=1 i=1
ϑi (s) < ∞. Clearly,
P2 Ps=r
nℓ
ℓ
from (27)
ϑ
(s)
=
Υ(s)
≥ 0. By the similar
ℓ=1
i=1 i

with the initial value
= 1, αij (0) = 0, ∀j 6= i; βii (0) = 1,
i
βj (0) = 0, ∀j 6= i.
Then for each i and k, let α̂ik = αii (k), β̂ki = βii (k). Clearly,
(10) holds.
First by A3 (i) and algorithm (43), αii (k) ≥ η k > 0 and
i
βi (k) ≥ η k > 0 for each k, which guarantees that the stepsize
selection rule (9) is well-defined. Let φℓ = (φℓ1 , . . . , φℓnℓ )′ be
the common left eigenvector
Pnℓ ofℓ Aℓ (r), r ≥ 0 associated with
eigenvalue one, where i=1
φi = 1. According to Lemma
5.6, limr→∞ Φℓ (r, k) = limr→∞ Aℓ (r) · · · Aℓ (k) = 1(φℓ )′ for
each k. As a result, αik = φ1i , i = 1, ..., n1 ; βki = φ2i , i =
1, ..., n2 for all k.
Let θ(k) = ((α1 (k))′ , . . . , (αn1 (k))′ )′ . From (43) we have
θ(k + 1) = (A1 (k) ⊗ In1 )θ(k)

and then limk→∞ θ(k) = limk→∞ (Φ1 (k, 0) ⊗ In1 )θ(0) =
(1(φ1 )′ ⊗ In1 )θ(0) = 1 ⊗ φ1 . Therefore, limk→∞ αii (k) = φ1i
for i ∈ V1 . Similarly, limk→∞ βii (k) = φ2i for i ∈ V2 . Since
αik = φ1i and βki = φ2i for all k, (11) holds. Moreover,
the above convergence is achieved with a geometric rate by
Lemma 5.5. Without loss of generality, suppose |αii (k)−φ1i | ≤
C̄ ρ̄k and |βii (k) − φ2i | ≤ C̄ ρ̄k for some C̄ > 0, 0 < ρ̄ < 1,
and all i, k.
The only difference between the models in Theorem 4.4
and the current one is that the terms αik and βki (equal to
φ1i and φ2i in case (i), respectively) in stepsize selection rule
(7) are replaced with α̂ik and β̂ki (equal to αii (k) and βii (k),
respectively) in stepsize selection rule (9). We can find that all
lemmas involved in the proof of Theorem 4.4 still hold under

IEEE TRANSACTIONS ON AUTOMATIC CONTROL

13

the new stepsize selection rule (9). Moreover, all the analysis
is almost the same as that in Theorem 4.4 except that the new
stepsize selection rule will yield an error term (denoted as
̟ℓ (k, r)) on the right-hand side of (39). In fact,
ℓ

̟ (k, r) = 2

k−1
X

1(ν+1)

Consequently, for each r ≥ 0, αirp1 +ν = φi
1

lim θν (r)

ℓ

γs Φ (k, s +

1)̟sℓ ϑℓ (s)

+

r→∞

2γk ̟kℓ ϑℓ (k),

=

1
, . . . , φ11 − αn11(s) ,
where
=
α11 (s)
n1
n1
1

̟s2 = diag φ12 − β 11(s) , . . . , φ21 − β n21(s) . Moreover, since
n2
n2
1
1
lims→∞ αii (s) = φ1i , αii (s) ≥ φ1i /2 ≥ η (n1 −1)T1 /2,

1
αii (s)

−

1
=
φ1i


diag φ11 −

αii (s) − φ1i
αii (s)φ1i

≤

2|αii (s) − φ1i |
(η (n1 −1)T1 )2

for a sufficiently large s. Analogously,
s

2C̄ ρ̄

η 2(n2 −1)T2

≤

1
βii (s)

2C̄ ρ̄

s

η 2(n1 −1)T1
−

1
φ2i

≤

. Then for a sufficiently large r and any k ≥ r + 1,

2
X
1 ′ ℓ
1 ̟ (k, r)
nℓ
ℓ=1

≤ 4C̄Lε1

k−1
X

, ν =

1(0)
φi .

Moreover, from (45) and
0, 1, ..., p − 2,
=
(46) we obtain that for ν = 0, 1, ..., p1 − 1,

s=r

̟s1

αirp1 +p1 −1

γs ρ̄s max{|xi (s) − x∗ |, |yj (s) − y ∗ |}

s=r
k−1
X

≤ 4C̄Lε1 ε2

(44)

s=r

where ε1 = max{1/η 2(n1 −1)T1 , 1/η 2(n2 −1)T2 }, ε2 =
sups {γs maxi,j {|xi (s) − x∗ |, |yj (s) − y ∗ |}} < ∞ due to
lims→∞ γs maxi,j {|xi (s) − x∗ |, |yj (s) − y ∗ |} = 0 by Lemma
5.7. From the proof of Theorem 4.4, we can find that the
relation (44) makes all the arguments hold and then a Nash
equilibrium is achieved for case (i).
(ii). Here we design a dynamics for the auxiliary states
(ν)i
(ν)i
α(ν)i = (α1 , . . . , αn1 )′ , ν = 0, ..., p1 − 1 for i ∈ V1 and
(ν)i
(ν)i
β (ν)i = (β1 , . . . , βn2 )′ , ν = 0, ..., p2 − 1 for i ∈ V2 to
estimate the respective desired stepsizes:
(
P
α(ν)i (s + 1) = j∈N 1 (s) aij (s)α(ν)j (s),
i
s≥ν+1
P
β (ν)i (s + 1) = j∈N 2 (s) aij (s)β (ν)j (s),
i
(45)
(ν)i
(ν)i
with the initial value αi (ν +1) = 1, αj (ν +1) = 0, j 6= i;
(ν)i
(ν)i
βi (ν + 1) = 1, βj (ν + 1) = 0, j 6= i.
(ν)i
Then, for each r ≥ 0, let α̂irp1 +ν = αi (rp1 + ν) for
(ν)i

i
(rp2 + ν) for
i ∈ V1 , ν = 0, ..., p1 − 1; let β̂rp
2 +ν = βi
2
i ∈ V2 , ν = 0, ..., p − 1.
S ℓ −1
Note that A2 implies that the union graphs ps=0
GAsℓ , ℓ =
1, 2 are strongly connected. Let φℓ(0) be the Perron vector
of limr→∞ Φℓ (rpℓ − 1, 0), i.e., limr→∞ Φℓ (rpℓ − 1, 0) =
ℓ
limr→∞ (Apℓ −1 · · · A0ℓ )r = 1(φℓ(0) )′ . Then for ν = 1, ..., pℓ −
1,

lim Φℓ (rpℓ + ν − 1, ν)

r→∞

ℓ

= lim (Aℓν−1 · · · A0ℓ Apℓ

−1

r→∞

ℓ

= lim (Apℓ

−1

r→∞

ℓ

= 1(φℓ(0) )′ Apℓ

ℓ

· · · A0ℓ )r Apℓ
−1

· · · Aν+1
Aνℓ )r
ℓ
−1

· · · Aν+1
Aνℓ
ℓ

· · · Aν+1
Aνℓ := 1(φℓ(ν) )′ .
ℓ

=

r→∞


1
lim Φ1 (r, 0)Aℓp −1 · · · Aν+1
⊗ In1 θν (ν
ℓ
r→∞

1(φ1(ν+1) )′ ⊗ In1 θν (ν + 1),

+ 1)

1

where θν = ((α(ν)1 )′ , . . . , (α(ν)n1 )′ )′ , φ1(p ) = φ1(0) . Then
1(ν+1)
(ν)i
for i ∈ V1 . Hence,
limr→∞ αi (r) = φi

lim α̂irp1 +ν − αirp1 +ν = 0, ν = 0, ..., p1 − 1.
r→∞

i
i
Analogously, we have limr→∞ (β̂rp
2 +ν − βrp2 +ν ) = 0, ν =
0, ..., p2 − 1. Moreover, the above convergence is achieved
with a geometric rate. Similar to the proof of case (i), we can
prove case (ii). Thus, the conclusion follows.


VI. N UMERICAL E XAMPLES

i,j

ρ̄s ≤ 4C̄Lε1 ε2 ρ̄r /(1 − ρ̄),

=


lim Φ1 (r, ν + 1) ⊗ In1 θν (ν + 1)

(46)

In this section, we provide examples to illustrate the obtained results in both the balanced and unbalanced graph cases.
Consider a network of five agents, where n1 = 3, n2 =
2, m1 = m2 = 1, X = Y = [−5, 5], f1 (x, y) = x2 − (20 −
x2 )(y − 1)2 , f2 (x, y) = |x − 1| − |y|, f3 (x, y) = (x − 1)4 − 2y 2
and g1 (x, y) = (x − 1)4 − |y| − 54 y 2 − 12 (20 − x2 )(y − 1)2 ,
g2 (x, y) = x2 + |x − 1| − 43 y 2 − 12 (20 − x2 )(y − 1)2 . Notice
P2
P3
that i=1 fi = i=1 gi and all objective functions are strictly
convex-concave on [−5, 5] × [−5, 5]. The unique saddle point
of the sum objective function g1 + g2 on [−5, 5] × [−5, 5] is
(0.6102, 0.8844).
Take initial conditions x1 (0) = 2, x2 (0) = −0.5, x3 (0) =
−1.5 and y1 (0) = 1, y2 (0) = 0.5. When x̂2 (k) = 1, we take
q12 (k) = 1 ∈ ∂x f2 (1, x̆2 (k)) = [−1, 1]; when ŷ1 (k) = 0,
2
we
 take q212(k) = −1 + (20 − y̆1 (k)) ∈ ∂y g1 (y̆1 (k), 0) =
r + (20 − y̆1 (k))| − 1 ≤ r ≤ 1 . Let γk = 1/(k + 50), k ≥ 0,
which satisfies A5.
We discuss three examples. The first example is given for
verifying the convergence of the proposed algorithm with
homogeneous stepsizes in the case of weight-balanced graphs,
while the second one is for the convergence with the stepsizes
provided in the existence theorem in the case of weightunbalanced graphs. The third example demonstrates the efficiency of the proposed adaptive learning strategy for periodical
switching unbalanced graphs.
Example 6.1: The communication graph is switching periodically over the two graphs G e , G 0 given in Fig. 2, where
G(2k) = G e , G(2k + 1) = G o , k ≥ 0. Denote by G1e and
G2e the two subgraphs of G e describing the communications
within the two subnetworks. Similarly, the subgraphs of G o
are denoted as G1o and G2o . Here the adjacency matrices of G1e ,
G2e and G1o are as follows:




0.6 0.4 0
0.9 0.1


0.4 0.6 0
A1 (2k) =
, A2 (2k) =
,
0.1 0.9
0
0 1

IEEE TRANSACTIONS ON AUTOMATIC CONTROL

14

1.5

3

3

2

2

2

2

1
0.8844

1

1

xi(k),yi(k)

1

1

0.6102
0.5

0

Figure 2: Two possible communication graphs in Example 6.1


1
A1 (2k + 1) =  0
0


0
0
0.7 0.3  .
0.3 0.7

−0.5

Clearly, with the above adjacency matrices, the three digraphs G1e , G2e and G1o are weight-balanced. Let the stepsize
be αi,k = βj,k = γk for all i, j and k ≥ 0. Fig. 3
shows that the agents converge to the unique Nash equilibrium
(x∗ , y ∗ ) = (0.6102, 0.8844).

0

20

40

60
k

80

100

120

Figure 4: The Nash equilibrium is achieved for weightunbalanced digraphs with heterogenous stepsizes.

Example 6.3: Here we verify the result obtained in Theorem
4.5 (ii). Consider Example 6.2, where p1 = p2 = 2. Design
adaptive stepsize algorithms: for ν = 0, 1,
θν (r) = (A1 (r) · · · A1 (ν + 1) ⊗ I3 )θν (ν + 1), r ≥ ν + 1,

1
0.8844
0.8
0.6102

ϑν (r) = (A2 (r) · · · A2 (ν + 1) ⊗ I2 )ϑν (ν + 1), r ≥ ν + 1,

0.4
0.2
0
−0.2
−0.4
0

20

40

60
k

80

100

120

Figure 3: The Nash equilibrium is achieved (i.e., xi → x∗ and
yi → y ∗ ) for the time-varying weight-balanced digraphs with
homogeneous stepsizes.
Example 6.2: Consider the same switching graphs given
in Example 6.1 except that a new arc (2, 3) is added in G1e .
The new graph is still denoted as G1e for simplicity. Here the
adjacency matrices of the three digraphs G1e , G2e and G1o are
given by




0.8 0.2 0
0.9 0.1


0.7 0.3 0
A1 (2k) =
, A2 (2k) =
,
0.8 0.2
0 0.6 0.4


1 0
0
A1 (2k + 1) =  0 0.3 0.7  .
0 0.4 0.6

In this case, G1e , G2e and G1o are weight-unbalanced
with (α12k , α22k , α32k )
=
(0.5336, 0.1525, 0.3139),
(α12k+1 , α22k+1 , α32k+1 ) = (0.5336, 0.3408, 0.1256) and
(βk1 , βk2 ) = (0.8889, 0.1111), ∀k ≥ 0. We design the
heterogeneous stepsizes as follows: αi,2k = α1i γ2k , αi,2k+1 =
1
1
γ
, i = 1, 2, 3; βi,k = β1i γk , i = 1, 2. Fig. 4 shows
αi0 2k+1
0
that the agents converge to the unique Nash equilibrium with
those heterogeneous stepsizes.

where ϑν (r) = ((β (ν)1 (r))′ , (β (ν)2 (r))′ )′ , θν (ν + 1) =
(1, 0, 0, 1)′.
(1)i
(0)i
i
=
Let α̂i2k = αi (2k), α̂i2k+1 = αi (2k + 1), β̂2k
(1)i
(0)i
i
βi (2k), β̂2k+1 = βi (2k + 1) and
1
1
γ2k , αi,2k+1 = i
γ2k+1 , i = 1, 2, 3,
α̂i2k
α̂2k+1
1
1
=
γ2k , βi,2k+1 =
γ2k+1 , i = 1, 2.
i
i
β̂2k
β̂2k+1

αi,2k =
βi,2k

Fig. 5 shows that the agents converge to the unique Nash
equilibrium under the above designed adaptive stepsizes.

1.5

1
0.8844
xi(k),yi(k)

xi(k),yi(k)

0.6

where θν (r) = ((α(ν)1 (r))′ , (α(ν)2 (r))′ , (α(ν)3 (r))′ )′ , θν (ν +
1) = (1, 0, 0, 0, 1, 0, 0, 0, 1)′; for ν = 0, 1,

0.6102
0.5

0

−0.5

0

20

40

60
k

80

100

120

Figure 5: The Nash equilibrium is achieved for weightunbalanced digraphs by adaptive stepsizes.

IEEE TRANSACTIONS ON AUTOMATIC CONTROL

VII. C ONCLUSIONS
A subgradient-based distributed algorithm was proposed to
solve a Nash equilibrium computation problem as a zerosum game with switching communication graphs. Sufficient
conditions were provided to achieve a Nash equilibrium for
switching weight-balanced digraphs by an algorithm with homogenous stepsizes. In the case of weight-unbalanced graphs,
it was demonstrated that the algorithm with homogeneous
stepsizes might fail to reach a Nash equilibrium. Then the
existence of heterogeneous stepsizes to achieve a Nash equilibrium was established. Furthermore, adaptive algorithms were
designed to update the hoterogeneous stepsizes for the Nash
equilibrium computation in two special cases.
R EFERENCES
[1] R. Horn and C. R. Johnson, Matrix Analysis. Cambridge University Press,
1985.
[2] W. Liebrand, A. Nowak, and R. Hegselmann, Computer Modeling of
Social Processes. Springer-Verlag, London, 1998.
[3] S. Boyd and L. Vandenberghe, Convex Optimization. New York: Cambridge University Press, 2004.
[4] C. Godsil and G. Royle, Algebraic Graph Theory. Springer-Verlag, New
York, 2001.
[5] R. T. Rockafellar, Convex Analysis. New Jersey: Princeton University
Press, 1972.
[6] B. T. Polyak, Introduction to Optimization. Optimization Software, Inc.,
New York, 1987.
[7] J. Hajnal and M. S. Bartlett, “Weak ergodicity in non-homogeneous
markov chains,” Proc. Cambridge Philos. Soc., vol. 54, no. 2, pp. 233246, 1958.
[8] M. Cao, A. S. Morse, and B. D. O. Anderson, “Reaching a consensus
in a dynamically changing environment: A graphical approach,” SIAM J.
Control Optim., vol. 47, no. 2, pp. 575-600, 2008.
[9] W. Meng, W. Xiao, and L. Xie, “An efficient EM algorithm for energybased sensor network multi-source localization in wireless sensor networks,” IEEE Trans. Instrum. Meas., vol. 60, no. 3, pp. 1017-1027, 2011.
[10] A. Olshevsky and J. N. Tsitsiklis, “On the nonexistence of quadratic
Lyapunov functions for consensus algorithms,” IEEE Trans. Autom.
Control, vol. 53, no. 11, pp. 2642-2645, 2008.
[11] B. Johansson, T. Keviczky, M. Johansson, and K. H. Johansson, “Subgradient methods and consensus algorithms for solving convex optimization
problems,” in Proc. IEEE Conf. on Decision and Control, Cancun,
Mexico, pp. 4185-4190, 2008.
[12] B. Johansson, M. Rabi, and M. Johansson, “A randomized incremental
subgradient method for distributed optimization in networked systems,”
SIAM J. Optim., vol. 20, no. 3, pp. 1157-1170, 2009.
[13] A. Nedić and A. Ozdaglar, “Subgradient methods for saddle-point
problems,” J. Optim. Theory Appl., vol. 142, no. 1, pp. 205-228, 2009.
[14] A. Nedić and A. Ozdaglar, “Distributed subgradient methods for multiagent optimization,” IEEE Trans. Autom. Control, vol. 54, no. 1, pp. 4861, 2009.
[15] A. Nedić, A. Ozdaglar, and P. A. Parrilo, “Constrained consensus and
optimization in multi-agent networks,” IEEE Trans. Autom. Control, vol.
55, no. 4, pp. 922-938, 2010.
[16] S. S. Ram, A. Nedić, and V. V. Veeravalli, “Incremental stochastic
subgradient algorithms for convex optimization,” SIAM J. Optim., vol.
20, no. 2, pp. 691-717, 2009.
[17] B. Touri, A. Nedić, and S. S. Ram, “Asynchronous stochastic convex
optimization over random networks: Error bounds,” in Proc. Inf. Theory
Applicat. Workshop, San Diego, CA, 2010.
[18] M. Zhu and S. Martı́nez, “On distributed convex optimization under
inequality and equality constraints via primal-dual subgradient methods,”
IEEE Trans. Autom. Control, vol. 57, no. 1, pp. 151-164, 2012.

15

[19] J. Chen and A. H. Sayed, “Diffusion adaptation strategies for distributed
optimization and learning over networks,” IEEE Trans. Signal Processing,
vol. 60, no. 8, pp. 4289-4305, 2012.
[20] G. Shi, K. H. Johansson, and Y. Hong, “Reaching an optimal consensus:
Dynamical systems that compute intersections of convex sets,” IEEE
Trans. Autom. Control, vol. 58, no. 3, pp. 610-622, 2013.
[21] G. Shi and K. H. Johansson, “Randomized optimal consensus of multiagent systems,” Automatica, vol. 48, no. 12, pp. 3018-3030, 2012.
[22] Y. Lou, G. Shi, K. H. Johansson, and Y. Hong, “Approximate projected
consensus for convex intersection computation: Convergence analysis and
critical error angle,” IEEE Trans. Autom. Control, vol. 59, no. 7, pp. 17221736, 2014.
[23] B. Gharesifard and J. Cortés, “Distributed convergence to Nash equilibria in two-network zero-sum games,” Automatica, vol. 49, no. 6, pp.
1683-1692, 2013.
[24] B. Gharesifard and J. Cortés, “Distributed continuous-time convex
optimization on weight-balanced digraphs,” IEEE Trans. Autom. Control,
vol. 59, no. 3, pp. 781-786, 2014.
[25] K. J. Arrow, L. Hurwicz, and H. Uzawa, Studies in Linear and Nonlinear programming, Stanford University Press, Stanford, CA, 1958.
[26] E. G. Gol’shtein, “A generalized gradient method for finding saddle
points,” Matekon 10, pp. 36-52, 1974.
[27] H. B. Dürr and C. Ebenbauer, “A smooth vector field for saddle point
problems,” in Proc. IEEE Conf. on Decision and Control, Orlando, pp.
4654-4660, 2011.
[28] D. Maistroskii, “Gradient methods for finding saddle points,” Matekon
13, pp. 3-22, 1977.
[29] J. Wang and N. Elia, “Control approach to distributed optimization,” in
Allerton Conf. on Communications, Control and Computing, Monticello,
IL, pp. 557-561, 2010.
[30] P. Frihauf, M. Krstic, and T. Basar, “Nash equilibrium seeking in
noncooperative games,” IEEE Trans. Autom. Control, vol. 57, no. 5, pp.
1192-1207, 2012.
[31] M. S. Stankovic, K. H. Johansson, and D. M. Stipanović, “Distributed
seeking of Nash equilibria with applications to mobile sensor networks,”
IEEE Trans. Autom. Control, vol. 57, no. 4, pp. 904-919, 2012.
[32] G. Theodorakopoulos and J. S. Baras, “Game theoretic modeling of malicious users in collaborative networks,” IEEE J. Select. Areas Commun.,
Special Issue on Game Theory in Communication Systems, vol. 26, no.
7, pp. 1317-1327, 2008.
[33] D. P. Bertsekas, A. Nedić, and A. Ozdaglar. Convex Analysis and
Optimization. Belmont, MA: Athena Scientific, 2003.
[34] A. Olshevsky and J. N. Tsitsiklis, “Convergence speed in distributed
consensus and averaging,” SIAM J. Control Optim., vol. 48, no. 1, pp.
33-55, 2009.
[35] D. Kempe, A Dobra, and J. Gehrke, “Gossip-based computation of
aggregate information,” in Proc. 44th Annual IEEE Symposium on Foundations of Computer Science, pp. 482-491, 2003.
[36] F. Benezit, V. Blondel, P. Thiran, J. Tsitsiklis, and M. Vetterli, “Weighted
gossip: Distributed averaging using non-doubly stochastic matrices,” in
Proc. 2010 IEEE International Symposium on Information Theory, 2010.
[37] M. Rabbat and R. Nowak, “Distributed optimization in sensor networks,”
in IPSN’04, pp. 20-27, 2004.
[38] K. Tsianos and M. Rabbat, “The impact of communication delays on
distributed consensus algorithms,” Available at
http://arxiv.org/abs/1207.5839 , 2012.
[39] K. Tsianos and M. Rabbat, “Distributed dual averaging for convex optimization under communication delays,” in American Control Conference,
pp. 1067-1072, 2012.
[40] J. Chen and A. H. Sayed, “On the limiting behavior of distributed
optimization strategies,” in Fiftieth Annual Allerton Conference, pp. 15351542, 2012.
[41] A. Nedić and A. Olshevsky, “Distributed optimization over time-varying
directed graphs,” IEEE Trans. Autom. Control, vol. 60, no. 3, pp. 601-615,
2015.
[42] A. Nedić and A. Olshevsky, “Stochastic gradient-push for strongly
convex functions on time-varying directed graphs,” Available at
http://arxiv.org/abs/1406.2075 , 2014.

