Geometric Convergence of Gradient Play Algorithms
for Distributed Nash Equilibrium Seeking

arXiv:1809.07383v3 [math.OC] 23 Oct 2018

Tatiana Tatarenko, Wei Shi and Angelia Nedić

Abstract—We study distributed algorithms for seeking a Nash
equilibrium in a class of non-cooperative convex games with
strongly monotone mappings. Each player has access to her
own smooth local cost function and can communicate to her
neighbors in some undirected graph. To deal with fast distributed
learning of Nash equilibria under such settings, we introduce
a so called augmented game mapping and provide conditions
under which this mapping is strongly monotone. We consider
a distributed gradient play algorithm for determining a Nash
equilibrium (GRANE). The algorithm involves every player
performing a gradient step to minimize her own cost function
while sharing and retrieving information locally among her
neighbors in the network. Using the reformulation of the Nash
equilibrium problem based on the strong monotone augmented
game mapping, we prove the convergence of this algorithm to a
Nash equilibrium with a geometric rate. Further, we introduce
the Nesterov type acceleration for the gradient play algorithm.
We demonstrate that, similarly to the accelerated algorithms in
centralized optimization and variational inequality problems, our
accelerated algorithm outperforms GRANE in the convergence
rate. Moreover, to relax assumptions required to guarantee
the strongly monotone augmented mapping, we analyze the
restricted strongly monotone property of this mapping and prove
geometric convergence of the distributed gradient play under
milder assumptions.

I. I NTRODUCTION
Game theory provides a framework to deal with optimization problems arising in multi-agent systems, where objective
functions are coupled through decision variables of all agents
in a system. The applications of game theoretic approach
include, for example, electricity markets, power systems, flow
control problems, and communication networks [1], [14], [17].
Nash equilibria in games characterize desirable and stable
solutions to the corresponding multi-agent optimization problems. The focus of our paper is on discrete-time algorithms
applicable to fast distributed Nash equilibrium seeking in
a class of non-cooperative games with strongly monotone
mappings.
There is a large body of work on Nash equilibrium computation in non-cooperative games. Each approach is based on
information available to agents in a systems and takes into account some structural properties of agents’ cost functions. For
example, in the case of the convex potential game structure, a
central optimization problem can be formulated whose minimizers are Nash equilibria in the game. To compute the minima of the potential function, some distributed communicationbased algorithms can be set up [5]. Moreover, in absence
The authors are with School of Electrical, Computer and Energy Engineering, Arizona State University, USA.
A. Nedić is also affiliated with Moscow Institute of Physics and Technology
(MIPT), Dolgoprudny, Russia.
The work has been partially supported by Office of Naval Research grant
no. N00014-12-1-0998.

of communication, so called oracle-based algorithms can be
applied to Nash equilibrium seeking in potential games. In
systems with oracle information each agent can calculate her
current output given any action from her action set. Various
versions of the logit dynamics have been presented to compute
Nash equilibria in such setting in both discrete action [7], [21]
and continuous action [13], [22] games. In some practical
situations agents do not have access to functional forms of
their objectives. Rather, each agent (player) can only observe
obtained payoffs and be aware of her own actions. Such
information structure is usually referred to as payoff-based.
A payoff-based Nash equilibrium learning is proposed in [8],
[24] for discrete action potential games and in [3], [20], [23]
for continuous action convex games.
Many works study convex games where players can exchange their local information with neighbors in some undirected connected communication graph. Distributed algorithms
are proposed for aggregative games [4], [11]. Communication
protocols are applied to general convex games with some
convergence guarantees [15], [16]. The work [15] studies distributed Nash equilibrium seeking of general non-cooperative
games and proposes a gradient based gossip algorithm. Under
strict convexity, Lipschitz continuity and bounded gradient
assumptions, this algorithm converges almost surely to the
Nash equilibrium, given a diminishing step size. Under further
assumption of strong convexity, with some constant step size
α, the algorithm converges to an O(α) neighborhood of the
Nash equilibrium in average. The work [16] develops an
algorithm within the framework of inexact-ADMM and proves
its convergence to the Nash equilibrium with the rate o(1/k)
under cocoercivity of the game mapping.
All aforementioned works focus on convergence guarantees
in different game settings and do not aim to provide fast
distributed algorithms with a geometric convergence rate.
The contributions of this paper are as follows. We provide
an equivalent condition for Nash equilibrium states based
on so called augmented game mapping which takes into
account agents’ local information that is exchanged over
some communication graph. Further, similarly to majority of
research on distributed Nash equilibrium seeking, we consider
undirected connected communication graphs and figure out
under which assumptions the augmented game mapping is
strongly monotone and Lipschitz continuous. Next, we present
a distributed gradient play algorithm for determining a Nash
equilibrium (GRANE). We demonstrate that GRANE converges to the Nash equilibrium with a geometric rate, given
strongly monotone and Lipschitz continuous augmented game
mapping. Moreover, using the results for strongly monotone
variational inequalities presented in [10], we introduce the
Nesterov type acceleration for the gradient play algorithm. We

show that the corresponding accelerated gradient play algorithm (Acc-GRANE) outperforms GRANE in the convergence
rate. However, the assumptions under which the augmented
game mapping is strongly monotone restrict the class of
games where Acc-GRANE can be applied. To rectify this
issue we consider a relaxed assumption implying the restricted
strongly monotone game mapping. Although Acc-GRANE
is not applicable in this case, we demonstrate that GRANE
converges to the Nash equilibrium with a geometric rate under
this milder assumption. A preliminary and brief version of
our work will appear in Conference on Decision and Control
2018 [?]. In the current paper, we extend our past work in the
following ways. Firstly, we provide all proofs omitted in the
conference paper. Secondly, we relax the assumption for the
augmented mapping to be able to consider a broader class of
games where geometric convergence to a Nash equivilibrium
takes place. Finally, we discuss how communication topology
affects the convergence rate of the distributed algorithms.
This paper is organized as follows. In Section II, we set
up the game under consideration. In Section III, we define
the augmented game mapping, analyze its properties, and
provide an equivalent condition for Nash equilibrium states
based on this mapping. Section IV develops the algorithms
with geometric convergence to a Nash equilibrium. We provide
a numerical case study in Section V. In Section VI, we
summarize the result and discuss future work.
Notations. The set {1, . . . , n} is denoted by [n]. For any
function f : K → R, K ⊆ Rn , ∇i f (x) = ∂f∂x(x)
is the
i
partial derivative taken in respect to the ith coordinate of the
vector variable x ∈ Rn . For any real vector space Ẽ its dual
space is denoted by Ẽ ∗ and the inner product is denoted by
hu, vi, u ∈ Ẽ ∗ , v ∈ Ẽ. Some operator B : Ẽ → Ẽ ∗ is
positive definite if hBv, vi > 0 for all v ∈ Ẽ \ {0}. Some
operator B : Ẽ → Ẽ ∗ is self-adjoint if hBv, v ′ i = hBv ′ , vi
for all v ′ , v ∈ Ẽ. Given a positive definite and self-adjoint
operator B, we define the Euclidean norm on Ẽ as kvk=
hBv, vi1/2 . Any mapping g : Ẽ → Ẽ ∗ is said to be strongly
monotone with the constant µ > 0 on Q ⊆ Ẽ, if hg(u) −
g(v), u − vi ≥ µku − vk2 for any u, v ∈ Q, where k·k is
the corresponding norm in Ẽ. We consider real vector space
E, which is either space of real vectors E = E ∗ = Rn or
the space of real matrices E = E ∗ =pRn×n . In the case
E = Rn×n the inner product hu, vi , trace(uT v) is the
Frobenius inner product on Rn×n . In the case E = Rn we use
k·k2 to denote the Euclidean norm induced by the standard
dot product in Rn , whereas in the case E = Rn×n we use
k·kFro to denote the Frobenius
p norm induced by the Frobenius
inner product i.e. kvkFro , trace(v T v). We use PΩ {v} to
denote the projection of v ∈ E to a set Ω ⊆ E. The largest
singular value of a matrix A is denoted by σmax {A}. The
smallest nonzero eigenvalue of a positive semidefinite matrix
A 6= 0 is denoted by λ̃min {A}, which is strictly positive. For
a matrix A ∈ Rm×n , null{A} , {x ∈ Rn |Ax = 0} is the
null space of A and span{A} , {y ∈ Rm |y = Ax, ∀x ∈ Rn }
is the linear span of all the columns of A. For any matrix
A ∈ Rn×n we use diag(A) to denote its diagonal vector, i.e.
diag(A) = (a11 , . . . , ann ). For any vector a ∈ Rn we use
Diag(a) to denote the diagonal matrix with the vector a on

its diagonal. We call a matrix A consensual, if it has equal
row vectors. Assuming that Ω ⊆ Rn , we define the indicator
function IΩ (x) of the set Ω such that IΩ (x) = 0, if x ∈ Ω,
and IΩ (x) = +∞, otherwise.
II. NASH E QUILIBRIUM S EEKING
A. Problem Formulation
We consider a non-cooperative game between n players. Let
Ji and Ωi ⊆ R1 denote respectively the cost function and the
feasible action set of the player i. We denote the joint action
set by Ω = Ω1 × . . . × Ωn . Each function Ji (xi , x−i ), i ∈ [n],
depends on xi and x−i , where xi ∈ Ωi is the action of the
player i and x−i ∈ Ω−i = Ω1 × . . . × Ωi−1 × Ωi+1 × Ωn
denotes the joint action of all players except for the player
i. We assume that the players can interact over an undirected
communication graph G([n], A). The set of nodes is the set
of the player [n] and the set of undirected arcs A is such
that (i, j) ∈ A if and only if (j, i) ∈ A, i.e. there is an
undirected communication link between i to j. Thus, some
information (message) can be passed from the player i to the
player j and vice versa. For each player i the set Ni is the
set of neighbors in the graph G([n], A), namely Ni , {j ∈
[n] : (i, j) ∈ A}. Let us denote the game introduced above
by Γ(n, {Ji }, {Ωi }, G). We make the following assumptions
regarding the game Γ.
Assumption 1. The game under consideration is convex.
Namely, for all i ∈ [n], the set Ωi is convex and closed,
the cost function Ji (xi , x−i ) is convex in xi and continuously
differentiable in xi for each fixed x−i .
Under Assumption 1, we can define the game mapping.
Definition 1. The game mapping F(x) : Ω → Rn is defined
as follows:
T

F(x) , [∇1 J1 (x1 , x−1 ), . . . , ∇n Jn (xn , x−n )] .

(1)

Assumption 2. The game mapping F(x) is defined on the
whole space Rn and is strongly monotone on Rn with the
constant µF .
Remark 1. Note that Assumption 2 above implies strongly
convexity of each cost function Ji (xi , x−i ) in xi for any fixed
x−i with the constant µF . Thus, the part of Assumption 1
holds. However, we consider Assumptions 1 and 2 separately,
to be able to emphasize what conditions are required in each
of the results presented further in the paper.
Assumption 3. For every i ∈ [n] the function ∇i Ji (xi , x−i ) is
Lipschitz continuous in xi on Ωi for every fixed x−i ∈ Rn−1 ,
that is, given any x−i ∈ Rn−1 , for some constant Li ≥ 0, we
have ∀ xi , yi ∈ Ωi
|∇i Ji (xi , x−i ) − ∇i Ji (yi , x−i )| ≤ Li |xi − yi |.
Moreover, for every i ∈ [n] the function ∇i Ji (xi , x−i ) is
Lipschitz continuous in x−i on Rn−1 , for every fixed xi ∈ Ωi ,
1 All results below are applicable for games with different dimensions {d }
i
of the action sets {Ωi }. The one-dimensional case is considered for the sake
of notation simplicity.

that is, given any xi ∈ Ωi , for some constant L−i ≥ 0, we
have
|∇i Ji (xi , x−i ) − ∇i Ji (xi , y−i )| ≤ L−i kx−i − y−i k2 ,
∀ x−i ,y−i ∈ Rn−1 .

Finally, we make the following assumption on the communication graph, which guarantees sufficient information
”mixing” in the network.
Assumption 4. The underlying undirected communication
graph G([n], A) is connected. The associated symmetric nonnegative mixing matrix W = [wij ] ∈ Rn×n defines the weights
on the undirected
P arcs such that wij > 0 if and only if
(i, j) ∈ A and ni=1 wij = 1, ∀j ∈ [n].

Remark 2. Note that there are some simple strategies for
generating symmetric mixing matrices for which Assumption 4
holds (see Section 2.4 in [18] for summarized strategies).

Assumption 4 implies the following properties of the mixing
matrix W (see [2]):
n
X

wij =

n
X
j=1

i=1

wij = 1, ∀i, j ∈ [n]

W is symmetric, I − W < 0;
null{I − W } = span{1}.

(2a)
(2b)
(2c)

One of the stable solutions in any game Γ corresponds to a
Nash equilibrium defined below.
Definition 2. A vector x∗ = [x∗1 , x∗2 , · · · , x∗n ]T ∈ Ω is a Nash
equilibrium if for any i ∈ [n] and xi ∈ Ωi
Ji (x∗i , x∗−i ) ≤ Ji (xi , x∗−i ).

In this work, we are interested in distributed seeking of
a Nash equilibrum in a game Γ(n, {Ji }, {Ωi }, G) for which
Assumptions 1-4 hold.
B. Existence and Uniqueness of the Nash Equilibrium
In this subsection, we demonstrate the existence and uniqueness of the Nash equilibrium for Γ(n, {Ji }, {Ωi }, G) under
Assumptions 1 and 2. For this purpose we recall the results
connecting Nash equilibria and solutions of variational inequalities [12].
Definition 3. For a set Q ⊆ Rd and a mapping g: Q → Rd
the variational inequality problem V I(Q, g) is formulated as
follows:
Find q ∗ ∈ Q :

hg(q ∗ ), q − q ∗ i ≥ 0 for all q ∈ Q.

The set of solutions to the variational inequality problem
V I(Q, g) is denoted by SOL(Q, g).
The following theorem is the well-known result on the
connection between Nash equilibria in games and solutions of
a definite variational inequality (see Corollary 1.4.2 in [12]).
Theorem 1. Consider a non-cooperative game Γ. Suppose
that the action sets of the players {Ωi } are closed and convex,
the cost functions {Ji (xi , x−i )} are continuously differentiable

and convex in xi for every fixed x−i on the interior of the joint
action set Ω. Then, a vector x∗ ∈ Ω is a Nash equilibrium for
the Γ if and only if x∗ ∈ SOL(Ω, F), where F is the game
mapping defined by (1).
The following result holds for variational inequalities with
strongly monotone mappings (see Proposition 2.3.3 in [12]).
Theorem 2. Given the V I(Q, g), suppose that Q is a closed
convex set and the mapping g is continuous and strongly
monotone. Then, the solution set SOL(Q, g) is nonempty and
is a singleton.
Taking into account Theorems 1 and 2, we obtain the
following results.
Theorem 3. Let Γ(n, {Ji }, {Ωi }, G) be a game for which
Assumptions 1-2 hold. Then, there exists a unique Nash
equilibrium in Γ. Moreover, the Nash equilibrium in Γ is the
solution of V I(Ω, F), where F is the game mapping (see (1)).
Finally, if Assumption 2 does not hold, but in addition to
Assumption 1 all action sets are compact, then, according to
Corollary 2.2.5 in [12], we can guarantee only existence of a
Nash equilibrium in the game under consideration.
Theorem 4. Let Γ(n, {Ji }, {Ωi }, G) be a game for which
Assumption 1 hold and Ωi is a compact set for all i ∈ [n].
Then, there exists a Nash equilibrium in Γ. Moreover, any
Nash equilibrium in Γ is the solution of V I(Ω, F), where F
is the game mapping (see (1)).
Thus, if Assumptions 1-2 hold, we can guarantee existence and uniqueness of the Nash equilibrium in the game
Γ(n, {Ji }, {Ωi }, G) under consideration. However, the reformulation of the Nash equilibrium in terms of the solution
of the variational inequality V I(Ω, F) does not take into
account the distributed setting of the problem presented in
the previous subsection. Hence, to let the players learn the
unique Nash equilibrium in a distributed way, we need to
find an alternative condition which allows us to determine the
Nash equilibrium in presence of partial information exchange
over the communication graph G with the associated mixing
matrix W . In the next section, we provide such a condition
and present distributed algorithms for computing the Nash
Equilibrium.
III. E QUIVALENT C ONDITION FOR NASH E QUILIBRIA AND
AUGMENTED G AME M APPING
A. Nash Equilibria in Distributed Settings
To deal with the partial information available to players
and exchanged among them over the communication graph,
we assume that each player i maintains a local variable
x(i) = [x̃(i)1 , · · · , x̃(i)i−1 , xi , x̃(i)i+1 , · · · , x̃(i)n ]T ∈ Rn , (3)
which is her estimation of the joint action x =
[x1 , x2 , · · · , xn ]T ∈ Ω. Here x̃(i)j ∈ R is the player i’s
estimate of xj and x̃(i)i = xi ∈ Ωi . Also, we compactly
denote the estimates of other players’ actions by the player i
as
x̃−i = [x̃(i)1 , · · · , x̃(i)i−1 , x̃(i)i+1 , · · · , x̃(i)n ]T ∈ Rn−1 , (4)

and the estimates of the player j’s action xj by all players as
T

n

x̃(:)j = [x̃(1)j , · · · , x̃(j−1)j , xj , x̃(j+1)j , · · · , x̃(n)j ] ∈ R .
Thus, we can define the estimation matrix x ∈ Rn×n , where
the ith row is equal to the estimation vector x(i) , i ∈ [n],
namely


— xT
—
(1)
 — xT
— 
(2)


x,
.
..


.
T
— x(n) —

Note that the estimation matrix belongs to a subset of the
space Rn×n that we denote by Ωa . The set Ωa consists of
matrices whose diagonal vectors are from the set of joint action
set Ω, i.e. Ωa , {x ∈ Rn×n : diag(x) ∈ Ω}. Finally, for
any given estimation matrix, we define the diagonal matrix
F̃(x) ∈ Rn×n with F̃(x)ii = ∇i Ji (x(i) ), i ∈ [n], namely
F̃(x) , Diag(∇1 J1 (x(1) ), . . . , ∇n Jn (x(n) )).

(5)

Now we are ready to state the proposition providing a
necessary and sufficient condition for a joint action x∗ to be
a Nash equilibrium in the game Γ(n, {Ji }, {Ωi }, G).
Proposition 1. Let us consider the game Γ(n, {Ji }, {Ωi }, G)
for which Assumptions 1 and 4 hold. Then the following
statements are equivalent
1) The vector x∗ = [x∗1 , . . . , x∗n ]T is a Nash equilibrium in
Γ(n, {Ji }, {Ωi }, G).
2) There exists an estimation matrix x∗ ∈ Ωa with the
diagonal vector x∗ = [x∗1 , . . . , x∗n ]T ∈ Ω and corresponding diagonal matrix F̃(x∗ ) (see (5)) such that for
any x ∈ Ωa the following holds:
∗

∗

∗

h(I − W )x + ΛF̃(x ), x − x i ≥ 0,
where Λ = Diag(α1 , . . . , αn ) ∈ Rn×n is an arbitrary
diagonal matrix with αi > 0, ∀i ∈ [n].
Proof. From the definition of Nash equilibrium (see Definition 2) and Assumption 1 we conclude that x∗ =
[x∗1 , . . . , x∗n ]T is a Nash equilibrium in Γ(n, {Ji }, {Ωi }, G) if
and only if there exists the estimation vector x∗(i) ∈ Rn , ∀i ∈
[n], such that
h∇i Ji (x∗(i) ), xi − x∗i i ≥ 0, ∀xi ∈ Ωi ,
x∗(1) = x∗(2) = . . . = x∗(n) .

(6a)
(6b)

Now we proceed with showing the equivalence (6) ⇔ 2).
The implication (6) ⇒ 2) holds, if we take x∗ to be the
matrix with each row equal toPtranspose of x∗ . Indeed, in this
case (I − W )x∗ = 0 (since ni=1 wij = 1, ∀j ∈ [n], due to
Assumption 4) and, according to (6), ∇i Ji (x∗ )(xi − x∗i ) ≥ 0
for all i ∈ [n].
To show 2) ⇒ (6) we define a matrix x(i, j), where its
element x(i, j)kl , k 6= i, l 6= j, is equal to the corresponding
element x∗kl of the matrix x∗ , x(i, j)ij is an arbitrary real
number, if i 6= j, and x(i, j) ∈ Ωi , if i = j. Next, let us
consider the inequalities
h(I − W )x∗ + ΛF̃(x∗ ), x(i, j) − x∗ i ≥ 0, for all i, j ∈ [n].

From the inequalities above we can conclude that
(I − W )x∗ + Λ(F̃(x∗ ) + G(x∗ )) = 0,

(7)

˜ Ωn (xn )) and
˜ Ω1 (x1 ), . . . , ∇I
where G(x∗ ) = Diag(∇I
˜
∇IΩi (xi ) is a subgradient of the indicator function IΩ (xi )
of the set Ωi .
Recall that the j-th column of x∗ is denoted by x̃∗(:)j .
For each x̃∗(:)j , j = 1, · · · , n, discarding the j-th equation
contained in (7) gives
[I − W ]−j x̃∗(:)j = 0, j = 1, · · · , n.
According to (2c), the matrix [I − W ]−j has the full row rank
for any j ∈ [n]. Thus, that only vectors x̃∗(:)j ∈ span{1}, j ∈
[n], are solutions to the systems of the linear equations above.
Therefore, (I − W )x∗ = 0 and (6b) holds. Furthermore, we
have F̃(x∗ ) + G(x∗ ) = 0 and, thus, (6a) follows.
Note that, regarding conditions for the communication
graph, to prove the proposition above we used only assumption
on stochastic rows of the matrix W and condition (2c),
which can correspond to any directed strongly connected
communication graph. Thus, the equivalent reformulation of
Nash equilibria presented in Proposition 1 holds also for
any convex game Γ(n, {Ji }, {Ωi }, G), where the graph G is
possibly directed, strongly
and the mixing matrix
Pconnected
n
W is row stochastic, i.e. i=1 wij = 1, ∀j ∈ [n].
Moreover, in proof of Proposition 1 we did not use Assumption 2 requiring strongly monotone game mapping. However,
we need this assumption in the next subsections, where we
present distributed algorithms and prove their convergence to
the Nash Equilibrium with a geometric rate.
B. Augmented Mapping
According to Proposition 1, to determine a Nash equilibrium in the game Γ(n, {Ji }, {Ωi }, G) under consideration we
need find an estimation matrix x∗ that solves the following
variational inequality:
h(I − W )x∗ + ΛF̃(x∗ ), x − x∗ i ≥ 0,
n×n

∀x ∈ Ωa .

(8)

where Λ ∈ R
is an arbitrary diagonal matrix Λ =
Diag(α1 , . . . , αn ), αi > 0, ∀i ∈ [n]. Due to Proposition 1,
any solution matrix x∗ of the variational inequality above is
consensual and its diagonal vector, as well as any row, represents a Nash equilibrium in Γ. Further we call such estimation
matrix x∗ the Nash equilibrium matrix. Note that (8) is defined
in terms of the matrix mapping Fa : Rn×n → Rn×n :
Fa (x) = (I − W )x + ΛF̃(x).

(9)

We refer to Fa (x) above as to the augmented mapping
of the game Γ(n, {Ji }, {Ωi }, G). In contrast to the game
mapping F̃(x) (see (1)), the augmented mapping allows us
to take into account the partial information exchange among
the players over the graph G. To set up efficient distributed
procedures with fast convergence rates, we leverage the results
on centralized algorithms for classical variational inequalities
with strongly monotone and Lipschitz continuous mappings
obtained in [10]. The summary of these results and corresponding algorithms for distributed settings are presented

in the next subsections. We conclude this subsection by
formulating conditions under which the augmented mapping is
Lipschitz continuous, strongly monotone, or restricted strongly
monotone and, thus, the results from [10] can be applied to
the game Γ(n, {Ji }, {Ωi }, G).
Lemma 1. Under Assumption 3, the augmented mapping
Fa (x) of the game Γ(n, {Ji }, {Ωi }, G) is Lipschitz continuous
on Ωa with the
constant
q
n Lipschitz
o LΛF +σmax {I − W }, where
LΛF = max αi L2i + L2−i .

Proof. (i) For any x, y ∈ Ωa , when x − y is not consensual,
due to Assumption 2 (see Remark 1), we have
hΛ(F̃(x) − F̃(y)), x − yi
n
X
hαi (∇i Ji (xi , x̃−i ) − ∇i Ji (yi , ỹ−i )), xi − yi i
=
i=1

n
X
hαi (∇i Ji (xi , x̃−i ) − ∇i Ji (yi , x̃−i )), xi − yi i
=
i=1

i

Proof. By Assumption 3, we see that ∀x, y ∈ Rn such that
xi , yi ∈ Ωi and x−i , y−i ∈ Rn−1 , we have
k∇i Ji (xi , x−i ) − ∇i Ji (yi , y−i )k2
= k∇i Ji (xi , x−i ) − ∇i Ji (yi , x−i )

≤ (βk∇i Ji (xi , x−i ) − ∇i Ji (yi , x−i )k22
1
β
+
k∇i Ji (yi , x−i ) − ∇i Ji (yi , y−i )k22 ) 2
β−1
(for any β > 1)
 12

β
L2−i kx−i − y−i k22
≤ βL2i kxi − yi k22 +
β−1

i=1
n
X

αi µF (xi − yi )2 −

n
X
i=1

αi L−i kx̃−i − ỹ−i k2 ·|xi − yi |

αi µF (xi − yi )2

i=1
n
X
i=1

{

αi L−i βi
αi L−i
(xi − yi )2 }
kx̃−i − ỹ−i k22 +
2
2βi

hΛ(F̃(x) − F̃(y)),
q x − yi

µ2F + L2−i − µF )}kx − yk2Fro .
(13)
Thus, due to Assumption 4 (see (2b)), we obtain
≥ −0.5 maxi {αi (

hFa (x) − Fa (y), x − yi

therefore,
(10)

≥ λ̃min {I − W }kx − yk2Fro
q
− 0.5 max{αi ( µ2F + L2−i − µF )}kx − yk2Fro ,
i

Given the condition (11a) and definition of µFa , we conclude
that
hFa (x) − Fa (y), x − yi ≥ µFa kx − yk2Fro .


where LF = max L(i) .
i

Thus, we have

kΛ(F̃(x) − F̃(y)) + (I − W )(x − y)kFro
≤ (LΛF + σmax {I − W }) kx − ykFro , ∀ x, y,

where LΛF = max αi L(i) .
i

(ii) For any x, y ∈ Ωa , when x − y is consensual, (12) is
still valid. However, (I − W )(x − y) = 0. Thus,
hFa (x) − Fa (y), x − yi = hΛ(F̃(x) − F̃(y)), x − yi
n
X
αi µF (xi − yi )2
≥
i=1

n
X
αi L−i βi
αi L−i
{
−
(xi − yi )2 }.
kx̃−i − ỹ−i k22 +
2
2β
i
i=1

Lemma 2. Under Assumptions 2 and 4 and given

Further, by choosing βi =
(11b), we get
(11a)
(11b)

the
augmented
mapping
Fa (x)
of
the
game
Γ(n, {Ji }, {Ωi }, G) is strongly monotone with the constant
µFa = min{a1 , a2 }.

n
X

hαi (∇i Ji (yi , x̃−i ) − ∇i Ji (yi , ỹ−i )), xi − yi i

(βi > 0 ∀i ∈ [n] are arbitrary).
(12)
√ 2 2
µF +L−i −µF
Further choosing βi =
in (12), we have
L−i

q
L2i + L2−i kx − yk2 , L(i) kx − yk2 ,

a1 = λ̃min {I − W }
q
− 0.5 max{αi ( µ2F + L2−i − µF )} > 0,
o
ni α
√
i
(µF − L−i n − 1) > 0,
a2 = min
i
n

≥

−

L2
(choose β = 1 + L−i
2 )
i

kF̃(x) − F̃(y)kFro ≤ LF kx − ykFro , ∀ x, y,

n
X
i=1

≥

+ ∇i Ji (yi , x−i ) − ∇i Ji (yi , y−i )k2

=

+

√1
n−1

and taking into account

hFa (x) − Fa (y), x − yi
n
X
√
≥
αi (µF − L−i n − 1)kxi − yi k22
i=1

≥ min

nα

i

o
√
(µF − L−i n − 1) kx − yk2Fro

i
n
≥ µFa kx − yk2Fro .

√
Remark 3. Lemma 2 holds for games with µF > n − 1L−i
for all i. Intuitively speaking, this means that, the strong
monotonicity of the game mapping should be strong enough
while for each player i, its local objective’s dependency on
other player’s strategies should be less than quadratically
or have small enough quadratic terms. To make this easier
to imagine, let us consider a class of game with objectives
in the form of Ji (xi , x−i ) = fi (xi ) + li (x−i )xi , where fi ’s
are twice differentiable and strongly convex while li (x−i )’s
are linear in x−i . For this special case, the Jacobian of the
game mapping F(x) is always positive definite as long as
the strong convexity constant of fi (xi )’s are large enough
because the Jacobian’s off-diagonal entries are all bounded.
Meanwhile, in this case, the Lipschitz constant L−i is any
number that satisfies |li (x−i ) − li (y−i )|≤ L−i kx−i − y−i k2
for all x−i , y−i ∈ Rn−1 . This is fulfilled by any Lipschitz
continuous function and linear function is obviously one of
the members.
To rectify the issue pointed out in Remark 3 and, thus,to
broaden the class of games under consideration, let us relax
Assumption 2. Namely, instead of the assumption on strongly
monotone game mapping F, let us introduce the following
assumption of restricted strongly monotone game mapping.
Assumption 5. The game mapping F is restricted strongly
monotone over Rn in respect to any Nash equilibrium x∗ ∈ Ω
with the constant µr > 0, namely for any x ∈ Rn
hF (x) − F (x∗ ), x − x∗ i ≥ µr kx − x∗ k22 .

Next, we show that under Assumption 5 there exist settings
for which the augmented mapping Fa is restricted strongly
monotone in respect to the Nash equilibrium matrix x∗ with
some positive constant.
Lemma 3. Under Assumptions 3, 4, and 5, the augmented
mapping Fa (x) of the game Γ(n, {Ji }, {Ωi }, G) is restricted
strongly monotone over Ωa in respect to any Nash equilibrium
matrix x∗ with the constant
µr,Fa = min{b1 , b2 },
n µ

o
r
b1 = min α
− LF (β 2 + 2β) , λ̃min {I − W } ,
n
λ̃min {I − W }
− αLF ,
b2 =
1 + β12

Let c = diag(c) ∈ Rn denote the vector in rows of the matrix
c. Due to Assumption 5 and given αi = α for all i ∈ [n], we
obtain
hΛ(F̃(c) − F̃(x∗ )), c − x∗ i
n
X
αi (∇i Ji (c) − ∇i Ji (x∗ ))(ci − x∗i )
=
i=1

≥ αhF(c) − F(x∗ ), c − x∗ i
µr
≥ αµr kc − x∗ k22 = α kc − x∗ k2Fro .
n

(15)

Since F̃ is nLipschitz
continuous
on Ωa with the constant
q
o
2
2
LF = max α Li + L−i (see equation (10) in the proof
i
of Lemma 1), we conclude that
hΛ(F̃(c) − F̃(x∗ )), x − ci ≥ − αLF kc − x∗ kFro kx − ckFro
= − αLF kc − x∗ kFro knkFro ,
(16a)
hΛ(F̃(x) − F̃(c)), c − x∗ i ≥ − αLF kx − ckFro kc − x∗ kFro ,
(16b)
hΛ(F̃(x) − F̃(c)), x − ci ≥ − αLF kx − ck2Fro

= −αLF knk2Fro ,
(16c)

Next, taking into account inequalities (15) and (16), we obtain
hΛ(F̃(x) − F̃(x∗ )), x − x∗ i = hΛ(F̃(c) − F̃(x∗ )), c − x∗ i
+ hΛ(F̃(c) − F̃(x∗ )), x − ci + hΛ(F̃(x) − F̃(c)), c − x∗ i
≥α

µ

r

n

+ hΛ(F̃(x) − F̃(c)), x − ci



kc − x∗ k2Fro −LF knkFro (2kc − x∗ kFro +knkFro)

.

(17)

Moreover, due to (14),
h(I − W )(x − x∗ ), x − x∗ i ≥ λ̃min {I − W }kx − x∗ k2Fro
= λ̃min {I − W }(kc − x∗ k2Fro +knk2Fro)
= λ̃min {I − W }knk2Fro,

(18)

since (I − W )(c − x∗ ) = 0 (see (2c)). Summing inequalities
(17) and (18), we conclude that

=

hFa (x) − Fa (x∗ ), x − x∗ i ≥ λ̃min {I − W }knk2Fro
µ

r
+α
kc − x∗ k2Fro −LF knkFro (2kc − x∗ kFro +knkFro) .
n
(19)

Proof. As the set of all consensual matrices in Rn×n is a
linear subspace of Rn×n , for any estimation matrix x ∈ Ωa
we can consider the following linear decomposition:

Let us fix some positive β > 0.
(i) If knkFro ≤ βkc − x∗ kFro , then, according to (19) and
(14),

wheren βq > 0 o
is a positive constant and LF
2
2
max α Li + L−i .
i

x = c + n,
where c ∈ Ωa is some consensual matrix and n is some matrix
from the subspace orthogonal to the subspace of all consensual
matrices on Ωa , namely hc, ni = 0. Since x∗ is a consensual
matrix, hc − x∗ , ni = 0. Thus, we get
kx − x∗ k2Fro = kc − x∗ k2Fro +knk2Fro.

(14)

hFa (x) − Fa (x∗ ), x − x∗ i ≥ λ̃min {I − W }knk2Fro

µ
r
− LF (β 2 + 2β) kc − x∗ k2Fro
+α
n
≥ b1 kx − x∗ k2Fro ,

(20)

where

o
n µ
r
− LF (β 2 + 2β) , λ̃min {I − W } .
b1 = min α
n

(ii) If knkFro ≥ βkc − x∗ kFro , then, according to (19) and
(14) and since F̃ is Lipschitz continuous with the constant LF ,
we obtain
∗

∗

hFa (x) − Fa (x ), x − x i ≥ λ̃min {I − W }knk2Fro
− αLF kx − x∗ k2Fro
= −αLF kx − x∗ k2Fro

 2
β knk2Fro knk2Fro
+
+ λ̃min {I − W }
1 + β2
1 + β2

≥ −αLF kx − x∗ k2Fro

 2
β knk2Fro β 2 kc − x∗ k2Fro
+
+ λ̃min {I − W }
1 + β2
1 + β2
∗ 2
= b2 kx − x kFro ,
(21)

where
b2 =

λ̃min {I − W }
− αLF .
1 + β12

Thus, combining (20) and (21), we conclude that
µr,Fa = min{b1 , b2 }.

Remark 4. Given any game Γ(n, {Ji }, {Ωi }, G), for which
Assumptions 3, 4, and 5 hold, there exist settings of the
augmented mapping Fa with Λ = Diag(α, · · · , α), α > 0,
such that Fa is restricted strongly monotone over Ωa in respect
to any Nash equilibrium matrix x∗ with the positive constant
β
µr,Fa > 0. Indeed, naccording to Lemma 3, we can choose o

such that b1 = min α µnr − LF (β 2 + 2β) , λ̃min {I − W }
is positive. It holds, for example, if
β 2 + 2β =

µr
.
2nLF

µr
> 0, there exists some positive β > 0
Note that as 2nL
F
solving the equation above. Further, based on the choice of
β > 0, we can proceed with settings for α > 0. We these
{I−W }
settings we need to guarantee that b2 = λ̃min1+
− αLF >
1

0. It holds, for example, if
α=

β2

λ̃min {I − W }
.
2LF (1 + β12 )

IV. G RADIENT A LGORITHMS WITH G EOMETRIC R ATES
A. Gradient and Accelerated Gradient Algorithms for Strongly
Monotone Variational Inequalities
In this subsection we summarize the results presented in
[10] that allow us to set up distributed procedures with
geometric convergence to the Nash Equilibrium in games with
strongly monotone mappings.
The paper [10] deals with the following general settings.
Let us consider some finite-dimensional real vector space E,
the dual space E ∗ . The scalar product of x ∈ E and s ∈ E ∗
is denoted by hs, xi. The Euclidean norms are defined by a

positive definite and self-adjoint operator B : E → E ∗ as
follows:
kxk = hBx, xi1/2 ,

ksk∗ = hs, B

−1

1/2

si

,

x ∈ E,

s ∈ E∗.

(22)

Let Q ⊆ E be some convex closed subset of E and
g : Q → E ∗ be some operator on Q. The goal is to solve
the corresponding variational inequality problem V I(Q, g):
Find x∗ ∈ Q :

hg(x∗ ), x − x∗ i ≥ 0 for all x ∈ Q2 .

Let us introduce γ = L
µ ≥ 1, which is the condition number
of the operator g.
The standard iterative gradient-type method for solving the
inequality above can be formulated as follows:
x0 = x ∈ Q,

xk+1 = PQ xk − λB −1 g(xk ) ,

k ≥ 0,

(23)

where B is an operator defining the Euclidean norms in the
spaces E and E ∗ (see (22)). In the case of strongly monotone
and Lipschitz continuous operator g and given an optimal
setting of the stepsize λ, the procedure above converges to
the unique solution of V I(Q, g) with a geometric rate.
Theorem 5. ( [10]) Let the operator g be continuous, strongly
monotone with some constant µ > 0, and Lipschitz continuous
with some constant L > 0. Let x∗ be the unique solution
of V I(Q, g), where Q is convex and closed. Then, given the
optimal stepsize λ = Lµ2 , the following holds for the gradient
algorithm (23):


k
k
∗ 2
kx − x k ≤ exp − 2 .
γ
According to Theorem 5, the convergence rate of the
procedure (23) depends on the squared condition number γ 2 .
As γ > 1, the convergence rate would be faster, if the constant
factor γ 2 is replaced by γ. To obtain this better dependence
of the rate on the condition number, namely to accelerate the
algorithm (23), the paper [10] follows the idea of the Nesterov
type acceleration in optimization of strongly convex functions
with Lipshitz continuous gradients (see [9], Section 2.2). For
this purpose the following merit function on Q needs to be
introduced:
f (x) = sup {hg(y), x − yi + 0.5µkx − yk2 }.
y∈Q

It is shown in [10] that the function f is strongly convex on
Q with the constant µ. Moreover, it is non-negative on Q and
is equal to 0 only at the unique solution of V I(Q, g). Thus,
x∗ = SOL(Q, g) is equal to the unique minimum of f on Q.
Further, analogously to the construction of optimization methods with optimal convergence rates presented in Section 2.2
of [9], the work [10] provides the estimate sequence of the
function f . For construction of the estimate sequence and the
2 see also Definition 3 for the special case E = E ∗ = Rd .

accelarated algorithmP
the authors use the sequence of positive
k
weights {λt }, S k = t=0 λt , and the following functions:
ψyβ (x) = hg(y), y − xi − 0.5βkx − yk2 ,

Ψk (x) =

k
X

(β > 0),

λt ψyµt (x),

(24)

t=0

where y t is some sequence generated by the corresponding
iterative process. The accelerated algorithm is based on the
definitions above and can be presented by the following
iterations:
xk = arg max Ψk (x),
x∈Q

y k+1 = arg max ψxLk (x),
x∈Q

1
· Sk,
γ

k ≥ 0.

Set mixing matrix W ; Choose step size λ > 0;
All players i ∈ [n] pick arbitrary initial x0(i) ∈ Rn ,
where the ith coordinate of x0(i) is from Ωi ;
for k = 0, 1, . . ., all players i ∈ [n] do
P
λwij x̃k(j)i
xk+1
= PΩi {(1 − λ + λwii )xki +
i
j∈Ni

−λαi ∇i Ji (xki , x̃k−i )};
for l = {1, · · · , i − 1, i + 1, · · · , n}
P
k
λwij x̃k(j)l ;
x̃k+1
(i)l = x̃(i)l +
j∈Ni

end for;
end for.

λ0 = 1, y 0 ∈ Q,

λk+1 =

Algorithm 1: GRANE

(25)

The following result holds for the procedure above.
Theorem 6. ( [10], Theorem 3) Let the operator g be
continuous, strongly monotone with some constant µ > 0, and
Lipschitz continuous with some constant L > 0. Let x∗ be the
unique solution of V I(Q, g), where Q is convex and
P closed.
Let the output of the algorithm (25) be ỹ k = S1k kt=0 λt y t .
Then


k
.
0.5µkỹ k − x∗ k2 ≤ f (y 0 ) · γ 2 exp −
γ+1
Thus, according to Theorems 5 and 6, for large values of
γ, the convergence rate of the accelerated procedure (25) is
much better than the convergence rate of the gradient method
(23), while both algorithms have the same implementation
complexity. In the next section we apply the results above
to set up and accelerate distributed Nash equilibrium seeking
in the case of strongly monotone game mappings.

As we can see, to run GRANE, agents start with arbitrary
estimations of the joint action, namely, they do not need
any prior information on the action sets of other players in
the game. As time runs, agents exchange the information
about their current estimations with their neighbors over the
communication graph with the mixing matrix W and update
their action based on local gradient steps. Thus, GRANE is a
distributed gradient algorithm. Moreover, due to the relation
(26), Lemmas 1, 2, and Theorems 3, 5, the following theorem
can be formulated.
Theorem 7. Let us consider the game Γ(n, {Ji }, {Ωi }, G) for
which Assumptions 1-4 hold. Then there exists the unique Nash
equilibrium x∗ in Γ. Moreover, given αi , i ∈ [n], such that
µ
µFa > 0, and the stepsize λ = LFFa2 , the estimation matrix
a
sequence {xk } generated by the algorithm GRANE satisfies
k

kx

− x∗ k2Fro ≤ exp



k
− 2
γ Fa



,

L

where γFa = µFFa and x∗ is the Nash equilibrium matrix.
a

B. Distributed Algorithms for Nash Equilibrium Seeking
Recall that in Proposition 1 we obtained the following result
for the game Γ(n, {Ji }, {Ωi }, G):
x∗ is a Nash Equilibrium ⇔ hFa (x∗ ),x − x∗ i ≥ 0,
∀x ∈ Ωa ,

(26)

where Fa is defined in (9) and x∗ is the Nash equilibrium
matrix. Moreover, it was shown in Lemmas 1 and 2 that under
Assumptions 2 and 3 there are settings for the parameters αi ,
i ∈ [n], such that the mapping Fa is Lipschitz continuous and
strongly monotone on Ωa with the constants LFa and µFa
respectively (see also Remark 3). Thus, we can apply the results from [10] discussed in the preceding section to distributed
Nash equilibrium seeking in the game Γ(n, {Ji }, {Ωi }, G).
We start with adapting the process (23) to V I(Ωa , Fa ) in
(26) with the mapping Fa (x) = (I−W )x+ΛF̃(x). Analogous
to notations in Subsection IV-A, we use the upper index to
denote the iteration index. By writing down the kth iteration
for each row in the estimation matrix xk we get the following
Algorithm 1.

To accelerate GRANE, we apply the updates in (25) to
the augmented game mapping Fa . To set up the accelerated
procedure, agents need to update not only the matrix xk ,
but also an auxiliary estimation matrix yk . The matrix y0
is initialized in Ωa . Note that, according to the definition of
the functions ψ and Ψ in (24), the updates of xk and y k+1 in
(25) are equivalent to
)
k 
1 X i i λi
i
λ y − g(y )
x =PQ
S k i=0
µ


1
y k+1 =PQ xk − g(xk ) ,
L
k

(

Pk
k
t
k+1
where, as before, λ0 = 1, S k =
= Sγ , µ
t=0 λ , λ
and L are the strong monotonicity and Lipschitz continuity
constants of the mapping g respectively, and γ = L
µ . Thus,
we conclude that the matrices xk and yk in the accelerated
procedure applied to the Nash equilibrium seeking problem in

the game Γ(n, {Ji }, {Ωi }, G) are updated as follows:
0

0

y ∈ Ωa , λ = 1, k = 0, 1, . . . ;
P
S k = kt=0 λt ;
k
λk+1 = γSF ;
a
n
io
Pk h
t
xk = PΩa S1k i=0 λt yt − µλF Fa (yt ) ;
oa
n
yk+1 = PΩa xk − L1F Fa (xk ) .

(27)

a

Analogously to (3) and (4), we define vectors y(i) and ỹ−i
in respect to the matrix y ∈ Ωa . Hence, the distributed
accelerated process can be presented by Algorithm 2 below.
Algorithm 2: Acc-GRANE
Set mixing matrix W ; λ0 = 1;
0
All players i ∈ [n] pick arbitrary initial y(i)
∈ Rn ,
0
where the ith coordinate of y(i) is from Ωi ;
for k = 0, 1, . . ., all players i ∈ [n] do
Pk
S k = t=0 λt ;
k
λk+1 = γSF ;
a
Pk
t
xki = PΩi { S1k t=0 [λt yit − µλF ((1 − wii )yit
a
P
t
t
wij ỹ(j)i
− αi ∇i Ji (yit , ỹ−i
))]};
+
j∈Ni

for l = {1, · · · , i − 1, i + 1, · · · , n}
Pk
t
t
+ µλF
x̃k(i)l = S1k t=0 [λt ỹ(i)l

a

P

j∈Ni

t
λwij ỹ(j)l
];

end for;
P
wij x̃k(j)i
yik+1 = PΩi {xki − L1F [(1 − wii )xki +
a

j∈Ni

−αi ∇i Ji (xki , x̃k−i )]};
for l = {1, · · · , i − 1, i + 1, · · · , n}
P
k+1
wij x̃k(j)l ;
y(i)l
= x̃k(i)l + L1F
a

j∈Ni

end for;
Pk
Output ỹk = S1k t=0 λt yt ;
end for.

Similarly to GRANE, Acc-GRANE does not require players to
have any prior information on the action sets of other players
in the game. Taking into account (26), Lemmas 1, 2, and
Theorems 3, 6, we obtain the following theorem.
Theorem 8. Let us consider the game Γ(n, {Ji }, {Ωi }, G) for
which Assumptions 1-4 hold. Then there exists the unique Nash
equilibrium x∗ in Γ. Moreover, given αi , i ∈ [n], such that
µFa > 0, the matrix sequence of outputs {ỹk } generated by
the algorithm Acc-GRANE satisfies


k
2
exp
−
0.5µFa kỹk − x∗ k2Fro ≤ F (y0 ) · γF
,
a
γ Fa + 1
L

where γFa = µFFa , x∗ is the Nash equilibrium matrix, and
a
F (y0 ) = supy∈Ωa {hFa (y), y0 − yi + 0.5µFa ky0 − yk2Fro }.
As it has been pointed out in Remark 3, the results of Theorems 7 and 8 apply only to the class of games with strongly
monotone
√ mappings that additionally satisfy the condition
µF > n − 1L−i for all i, implying a restrictive structure
of cost functions. To set up the GRANE for a broader class
of games, we use Lemma 3 to get the following result.

Theorem 9. Let us consider the game Γ(n, {Ji }, {Ωi }, G)
for which Assumptions 1, 3, 4, and 5 hold. Let each action
set Ωi , i ∈ [n], be compact. Then there exists the unique
Nash equilibrium x∗ in Γ. Moreover, given αi = α > 0,
i ∈ [n], such that µr,Fa > 0 in Lemma 3, and the stepsize
µ a
k
λ = Lr,F
2 , the estimation matrix sequence {x } generated by
Fa
the algorithm GRANE satisfies


k
kxk − x∗ k2Fro ≤ exp − 2 ,
γr
L

Fa
where γr = µr,F
and x∗ is the Nash equilibrium matrix.
a

Proof. According to Theorem 4, there exists a Nash equilibrium x∗ in the game Γ(n, {Ji }, {Ωi }, G) with compact action
sets and satisfying Assumptions 1. Moreover, it can be shown
that under Assumption 5 the Nash equilibrium is unique.
Indeed, due to Theorem 1, any Nash equilibrium x∗ ∈ Ω
solves V I(Ω, F), namely for any x ∈ Ω
hF(x∗ ), x − x∗ i ≥ 0.
Let us assume there exists another Nash equilibrium y ∗ ∈ Ω.
Then, the inequality above implies
hF(x∗ ), y ∗ − x∗ i ≥ 0,

hF(y ∗ ), x∗ − y ∗ i ≥ 0.

Hence, hF(x∗ ) − F(y ∗ ), x∗ − y ∗ i ≤ 0, which together with
Assumption 5 implies x∗ = y ∗ .
According to the previous discussion, the distributed setting
of the GRANE presented in Algorithm 1 can be expressed in
terms of updates of estimation matrices follows:
x0 = x ∈ Ωa ,

xk+1 = PΩa {xk − λFa (xk )},

k≥0

Moreover, since the Nash equilibrium matrix x∗ solves
V I(Ωa , Fa ) (see Proposition 1), we conclude that for any
λ>0
x∗ = PΩa {x∗k − λFa (x∗k )}
Thus, we get the following estimation for the distance to x∗ ∈
Ωa :
kxk+1 − x∗ k2Fro ≤ kxk − λFa (xk ) − x∗ + λFa (x∗ )k2Fro
= kxk − x∗ k2Fro

+ λ2 kFa (xk ) − Fa (x∗ )k2Fro

− 2λhFa (xk ) − Fa (x∗ ), xk − x∗ i.

(28)

Next, according to Lemma 3 and Remark 4, there exists α > 0
such that Fa is restricted strongly monotone in respect to x∗
with some µr,Fa > 0 and, hence,
λhFa (xk ) − Fa (x∗k ), xk − x∗ i ≥ µr,Fa kxk − x∗ k2Fro .
Thus, taking into account Lemma 1, we obtain from (28) that
kxk+1 − x∗ k2Fro ≤ (1 + LF 2 λ2 − 2µr,Fa λ)kxk − x∗ k2Fro .

µ

a
Hence, under the optimal choice of λ = Lr,F
2 , we conclude
Fa
that


1
kxk+1 − x∗ k2Fro ≤ 1 − 2 kxk − x∗ k2Fro ,
γr

and, thus, the result follows.
C. Discussion
In this section, we study how the functional conditions (Lipschitz constants, strong convexity, etc.), the graph topology
(algebraic connectivity), and the ratio parameter α affect the
convergence speed of the algorithms.
As illustrated in the above results, to reach ǫ-accuracy,
GRANE requires O(γr2 log(1/ǫ)) iterations (Theorem 9) in
the case of the restricted strongly monotone augmented
game mapping Fa with the constant µr,Fa , while AccGRANE is applicable in the case of the strongly monotone augmented game mapping Fa with the constant µFa
2
and needs O(γFa log(2F (y0 )) + log(γF
/µFa ) + log(1/ǫ) )
a
(Theorem 8), where we usually consider log(2F (y0 )) and
2
log(γF
/µFa ) to be negligible compared to log(1/ǫ). Thus, the
a
major factor that impacts the convergence rates/complexities
L Fa
and LFa /µFa respectively.
is γr and γFa equal to µr,F
a
First, let us consider the constant γFa defining the convergence rate of Acc-GRANE. We assume that Λ = αI and
denote H = maxi {L−i }. Then the condition number can be
expressed as follows:

αLF +σmax {I−W }
√
,
γFa = max
λ̃min {I−W }−0.5α( µ2F +H 2 −µF )
o
αLF +σmax {I−W }
√
.
α(µ −H n−1)/n
F

By restricting
to a smaller class of problem where H ≤
√
0.5µF / n − 1, we are able to obtain that
n
αLF +σmax {I−W }
γFa ≤ max
,
λ̃min {I−W }−αµFo
/(16(n−1))
(29)
αLF +σmax {I−W }
.
αµF /(2n)

applicaNote that in Lemma 2, Remark 3, and Theorem 8, the √
ble class of games is restricted to those with H ≤ µF / n − 1.
In the following, we discuss the results under different choices
{I−W }
of α. Let us denote C = 16(n−1)λ̃µmin
.
F
C
If we choose α = 9 , then
9 λmax {I−W }
F
γFa ≤ 2n L
,
µF + 8 λ̃
{I−W }
min

(30)

where γF , LF /µF can be understood as the condition number of the game mapping F and γG ,
λmax {I − W }/λ̃min {I − W } is strongly dependent on the
algebraic connectivity of the graph. When W is chosen in
the form of W = I − tŁ where Ł is the Laplacian matrix
of the graph G and t ∈ (0, 2/λmax{Ł}), we have γG =
λmax {Ł}/λ̃min {Ł} which coincides with the conventional
condition number of the Laplacian. An unpleasant comment
for (30) is that the number of nodes has a linear multiplicative
effect on the functional condition number γF , which implies
either the bound is not tight or the algorithm may suffer
slow convergence when the number of nodes becomes large.

Nonetheless an inspiring observation on (30) is that the condition number γFa is upper bounded by the weighted sum of γG
and γF . This is very different from what many other decentralized algorithms illustrate in the literature. For example, in
reference [19] for consensus optimization employing ADMM,
the analogous complexity derived under our notation would be
O((γG2 + γG γF ) log(1/ǫ)) where a multiplicative coupling of
γG and γF is noticed. More examples of such multiplicative
coupling can be found in Table II of reference [6].
By (29), if we choose α = rC where r ∈ 0, 19 , then
1 n λmax {I−W }
F
γFa ≤ 2n L
µF + 8r n−1 λ̃min {I−W } ;

If we choose α = rC where r ∈ 91 , 1 , then

1 λmax {I−W }
r
F
.
16n L
γFa ≤ 1−r
µF + 1−r λ̃
{I−W }
min

(31)

(32)

Note that the right-hand-sides of (31) and (32) are both larger
than the right-hand-side of (30). We can see that for any
absolute constant r ∈ (0, 1), we have γFa = O(nγF + γG ).
Furthermore, too large α or too small α can both lead to poor
scalability and slow convergence while a theoretically optimal
α is provided as α = C9 .
Similarly to the discussion above, we can obtain the following estimation for the constant γr from Theorem 9. Indeed,
under the choice of the parameters β and α as in Remark 4,
o
n
+σmax {I−W } αLF +σmax {I−W }
,
,
γr ≤ max αLFαµ
/2n
r,F
λ̃
{I−W }
a

min

which implies that

{I−W }
F
.
+ λλ̃max{I−W
γr ≤ 2n µLr,F
}
a

min

Thus, analogously to the analysis of the constant γFa , we
conclude that γr = O(nγr + γG ) and, hence, the number of
players, condition number of the initial game mapping, and
connectivity of the communication graph contribute the most
to the convergence rate of GRANE.
V. S IMULATION R ESULTS
Let us consider a class of games that we have discussed in
Remark 3. Specifically, we have players {1, 2, . . . , 20} and
each player i’s objective is to minimize the cost function
2
Ji (xi , x−i ) = fi (xi ) +
Pli (x−i )xi , where fi (xi ) = 0.5ai xi +
bi xi and li (x−i ) =
j6=i cij xj . Each player i is imposed
with a randomly generated box constraint for its own strategy.
The local cost function is in general dependent on actions
of all players, but the underlying communication graph is
a randomly generated tree graph. For simplicity, we choose
αi = α for all i. We randomly select ai , bi , and cij for all
possible i and j but manipulate the data P
so that cij = −cji
2
0.5
) > 0.
and µFa = α
(min
{a
}
−
((n
−
1)
max
{
i
i
i
j6=i cij })
n
Thus, according to Theorem 8, the accelarated gradient algorithm, namely Acc-GRANE, can be applied to learn the
Nash equilibrium in the game under consideration. Convergence curves for GRANE and Acc-GRANE are provided in
Fig. 1. The Nash equilibrium x∗ is computed using centralized
gradient play method with over 12000 iterations. We use
this x∗ as our reference and define the relative error as

kxk − x∗ k2Fro /kxk − x0 k2Fro . The convergence of GRANE is
slow due to the small step-size and the small parameter α.
The small parameter α and specific settings for the coefficients ai , cij , i, j = 1, . . . , 20, are chosen to guarantee
that µFa > 0 and, thus, Acc-GRANE is applicable. To relax
these assumptions on the cost functions and choose a larger
α, we refer to the results in Lemma 3 and Theorem 9. These
results allow us to choose α as in Remark 4 and to apply
GRANE to the game with any ai , cij , i, j = 1, . . . , 20, such
that mini ai > 0. The implementation of GRANE for different
settings of the cost functions and the corresponding parameter
α are demonstrated in Fig. 2. As we can see, in contrast
to the run of GRANE applied to the strongly monotone
augmented mapping Fa (see Fig. 1, where the relative error
does not change significantly after 500 iterations), the relative
error of GRANE applied to the restricted strongly monotone
augmented mapping Fa decreases with time.

Relative Error

100

10-1

R EFERENCES
10-2
Acc-GRANE, α = 4.2e − 04
Acc-GRANE, α = 1.3e − 03
Acc-GRANE, α = 2.5e − 03
GRANE, α = 1.8e − 07
GRANE, α = 1.6e − 06
GRANE, α = 6.3e − 06

10-3

10-4

0

500

1000

1500

2000

2500

3000

k
Fig. 1. Plots of the normalized residual kxk − x∗ kFro /kx0 − x∗ kFro .
Different α is set to observe the performance under different 1/LFa .

eplacements
0

GRANE

Relative Error

1

k
2000
4000
6000
8000
10000

the case in which players do not have the full information of joint actions but can exchange their estimates with
neighbors through a decentralized communication network.
To let the networked system reach the Nash equilibrium
at a geometric rate, a decentralized gradient play algorithm
is introduced based on the investigation of the conditions
for a Nash equilibria. Moreover, by leveraging the idea of
an accelerated approach for solving variational inequalities,
we have obtained a version of the gradient play algorithm
that guaratees a faster convergence to the Nash equilibrium,
due to a better dependence on the condition number. The
presented accelerated algorithm is applicable to a restricted
class of games for which the augmented game mapping is
strongly monotone. To apply the decentralized gradient play
algorithm to a broader class of games, we consider the case
of the restricted strongly monotone augmented game mapping
and demonstrated geometric convergence of the procedure
to the Nash equilibrium. Future works can be devoted to
the investigation of modifications for the accelerated algorithm to make it applicable in games without assumption on
strongly monotone augmented game mappings. Another future
direction is to adapt the procedures to settings that do not
require knowledge of the strong monotonicity constant and
the Lipschitz continuity constant of the game mapping.

0.5

0.1
0.01
Fig. 2. Plots of the normalized residual kxk − x∗ kFro /kx0 − x∗ kFro .
Different α is set to observe the performance under different 1/LFa .

VI. C ONCLUSION
In this paper, we have studied a class of games with
(restricted) strongly monotone mappings. We have considered

[1] T. Alpcan and T. Başar. Distributed Algorithms for Nash Equilibria of
Flow Control Games. In Advances in Dynamic Games, pages 473–498.
Springer, 2005.
[2] A. E. Brouwer and W. H. Haemers. Spectra of Graphs. New York, NY,
2012.
[3] P. Frihauf, M. Krstić, and T. Başar. Nash equilibrium seeking in
noncooperative games. Automatic Control, IEEE Transactions on,
57(5):1192–1207, 2012.
[4] J. Koshal, A. Nedić, and U. Shanbhag. A Gossip Algorithm for
Aggregative Games on Graphs. In Decision and Control (CDC), 2012
IEEE 51st Annual Conference on, pages 4840–4845. IEEE, 2012.
[5] N. Li and J. Marden. Designing Games for Distributed Optimization.
IEEE Journal of Selected Topics in Signal Processing, 7(2):230–242,
2013.
[6] Z. Li, W. Shi, and M. Yan. A decentralized proximal-gradient method
with network independent step-sizes and separated convergence rates.
arXiv preprint arXiv:1704.07807, 2017.
[7] J. R. Marden, G. Arslan, and J. S. Shamma. Cooperative control and
potential games. Trans. Sys. Man Cyber. Part B, 39(6):1393–1407,
December 2009.
[8] J. R. Marden and J. S. Shamma. Revisiting log-linear learning:
Asynchrony, completeness and payoff-based implementation. Games
and Economic Behavior, 75(2):788 – 808, 2012.
[9] Yu. Nesterov. Introductory Lectures on Convex Optimization: A Basic
Course, volume 87. Springer, 2004.
[10] Yu. Nesterov and L. Scrimali. Solving strongly monotone variational
and quasi-variational inequalities. Discrete and Continuous Dynamical
Systems - A, 31(4):1383–1396, 2006.
[11] D. Paccagnan, M. Kamgarpour, and J. Lygeros. On aggregative and
mean field games with applications to electricity markets. In 2016
European Control Conference (ECC), pages 196–201, June 2016.
[12] J.-S. Pang and F. Facchinei. Finite-dimensional variational inequalities
and complementarity problems : vol. 1. Springer series in operations
research. Springer, New York, Berlin, Heidelberg, 2003.
[13] S. Perkins, P. Mertikopoulos, and D. S. Leslie. Mixed-strategy learning
with continuous action sets. IEEE Transactions on Automatic Control,
62(1):379–384, Jan 2017.
[14] W. Saad, H. Zhu, H. V. Poor, and T. Başar. Game-theoretic methods
for the smart grid: An overview of microgrid systems, demand-side
management, and smart grid communications. IEEE Signal Processing
Magazine, 29(5):86–105, 2012.

[15] F. Salehisadaghiani and L. Pavel. Distributed Nash equilibrium seeking:
A gossip-based algorithm. Automatica, 72:209–216, 2016.
[16] F. Salehisadaghiani, W. Shi, and L. Pavel. An admm approach to the
problem of distributed nash equilibrium seeking. CoRR, 2017.
[17] G. Scutari, S. Barbarossa, and D. P. Palomar. Potential games: A
framework for vector power control problems with coupled constraints.
In 2006 IEEE International Conference on Acoustics Speech and Signal
Processing Proceedings, volume 4, pages 241–244, May 2006.
[18] W. Shi, Q. Ling, G. Wu, and W. Yin. EXTRA: An Exact First-Order
Algorithm for Decentralized Consensus Optimization. SIAM Journal on
Optimization, 25(2):944–966, 2015.
[19] W. Shi, Q. Ling, K. Yuan, G. Wu, and W. Yin. On the Linear
Convergence of the ADMM in Decentralized Consensus Optimization.
IEEE Transactions on Signal Processing, 62(7):1750–1761, 2014.
[20] M. Stanković, K. Johansson, and D. Stipanović. Distributed Seeking of
Nash Equilibria with Applications to Mobile Sensor Networks. IEEE
Transactions on Automatic Control, 57(4):904–919, 2012.
[21] T. Tatarenko. Proving convergence of log-linear learning in potential
games. In American Control Conference (ACC), 2014, pages 972–977,
June 2014.
[22] T. Tatarenko. Independent log-linear learning in potential games with
continuous actions. IEEE Transactions on Control of Network Systems,
PP(99):1–1, 2017.
[23] T. Tatarenko and M. Kamgarpour. Learning generalized nash equilibria
in a class of convex games. IEEE Transactions on Automatic Control,
pages 1–1, 2018.
[24] M. Zhu and S. Martı́nez. Distributed coverage games for energy-aware
mobile sensor networks. SIAM J. Control and Optimization, 51(1):1–27,
2013.

