Generalized Nash Equilibrium Problem by the Alternating Direction
Method of Multipliers

arXiv:1703.08509v1 [cs.GT] 24 Mar 2017

Farzad Salehisadaghiani, and Lacra Pavel
Abstract— In this paper, the problem of finding a generalized
Nash equilibrium (GNE) of a networked game is studied.
Players are only able to choose their decisions from a feasible
action set. The feasible set is considered to be a private linear
equality constraint that is coupled through decisions of the
other players. We consider that each player has his own private
constraint and it has not to be shared with the other players.
This general case also embodies the one with shared constraints
between players and it can be also simply extended to the case
with inequality constraints. Since the players don’t have access
to other players’ actions, they need to exchange estimates of
others’ actions and a local copy of the Lagrangian multiplier
with their neighbors over a connected communication graph.
We develop a relatively fast algorithm by reformulating the
conservative GNE problem within the framework of inexactADMM. The convergence of the algorithm is guaranteed under
a few mild assumptions on cost functions. Finally, the algorithm
is simulated for a wireless ad-hoc network.

I. I NTRODUCTION
The problem of finding a generalized Nash equilibrium
(GNE) has recently drawn many attentions due to its applicability in various networked games with coupling constraints
such as power grids [1], optical networks [2] and wireless
communication networks [3].
In such games, each player aims to minimize his cost
function by taking a proper action in response to other
players. Each player’s feasible decision set is dependent on
other players’ actions. We are interested in seeking a GNE,
which is a point that no player can unilaterally deviate his
local action to minimize his cost function.
Due to similarities between this problem and distributed
consensus optimization problems (DCOPs), we aim to employ an efficient, robust and fast optimization technique
referred to as the alternating direction method of multipliers
(ADMM) to find a GNE of a multi-player game. The key
differences between DCOP and GNE problem is that in a
DCOP each agent desires to minimize a global objective by
controlling a full vector optimization variable. However, in a
GNE problem, we have a set of local optimization problems
assigned to each player who controls only his action (which
is an element of a full vector). This leads to have a suboptimization problem associated to each player such that
each of them is dependent on the other players’ actions.
Related Works. Our work is related to the literature on
(generalized) Nash games such as [4]–[7] and DCOPs such
as [8], [9]. (G)NE seeking in distributed networked games
The authors are with the Department of Electrical and Computer Engineering, University of Toronto, Toronto, ON M5S 3G4, Canada (emails: farzad.salehisadaghiani@mail.utoronto.ca,
pavel@ece.utoronto.ca).

has recently attracted an increased interest due to many realworld applications. To name only a few, [10], [11].
In [10], the problem of finding GNE is studied in a
networked game. A gradient-based algorithm is designed
over a complete communication graph. Convergence proof
is analyzed in the presence of delay and dynamic change.
Similar to [1], the problem of seeking a GNE is discussed
in [12] for the games that players have access to all players’
actions on which their cost depends on. Thus, they exchange
only local multipliers not the estimates of others’ actions.
A Nash game with a coupled constraint is considered in
[13]. A variational inequality related approach is used to
compute a GNE of the game. The authors in [14] solve a
quadratic GNE problem with linear shared coupled constraint
using Lemkes method.
Recently, there has been a widespread research on GNE
seeking in aggregative games [1], [13], [14]. Quadratic aggregative games with affine and convex coupling constraints
are studied in [15], [16]. A coordination scheme belonging
to a class of asymmetric projection algorithm is presented
in [15] and its convergence to a GNE is then discussed.
A model-free dynamic control law, based on monotone
operator, is proposed in [16] to ensure the global convergence
to a GNE.
ADMM algorithms, which are in the scope of this paper,
have been developed in 70’s to find an efficient way to
obtain an optimal point of distributed optimization problems
(DOPs) [17], [18]. After the re-introduction of this method
in [18], ADMM has become widely used to locate optimal
points of DOPs as a robust and fast technique [19], [20].
An inexact-ADMM algorithm is proposed in [8] for DCOPs
with an affine equality constraint. In [21], we develop a
methodology to relate a distributed NE problem with no
coupled constraint to a DCOP using augmentation technique.
It is shown that an NE problem can be treated as a set of suboptimization problems with an augmented equality constraint
for the estimates of the players.
Contributions. Motivated by ADMM methods designed
for DCOPs, we develop a relatively fast algorithm for GNE
problems within the framework of inexact-ADMM. Players
are only aware of their own cost functions (which are not
in the form of aggregative but general game), problem data
(which is related to a private coupled equality constraint for
each player) and action set of all players (they are not aware
of the others’ actions). We reformulate the conservative GNE
problem into the corresponding Lagrange dual problem and
then we augment it using local estimates of players’ actions
as well as local copies of Lagrange multipliers. We derive a

set of GNE conditions using the associated KKT conditions
and finally we develop an inexact-ADMM algorithm based
on the augmented Lagrange function which is related to each
player. The convergence proof of the algorithm to a GNE of
the game is then provided under a few mild assumptions on
players’ cost functions.
The paper is organized as follows. The problem statement
and assumptions are provided in Section II. In Section III,
an inexact-ADMM-like algorithm is derived. Convergence of
the proposed algorithm to a GNE of the game is discussed
in Section IV. Simulation results are illustrated in Section V
and concluding remarks are presented in Section VI.
II. P ROBLEM S TATEMENT
Consider V = {1, . . . , N } as a set of N players that seek
a GNE of a networked game with individual linear coupled
constraints. The game is denoted by G and defined as follows:
• Ωi ⊂ R: Action set of player i, ∀i ∈ V ,
Q
N
• Ω=
i∈V Ωi ⊂ R : Action set of all players,
• Ji : Ω → R: Cost function of player i, ∀i ∈ V .
The game G(V, Ωi , Ji ) is defined over the set of players,
V , the action set of player i ∈ V , Ωi and the cost function
of player i ∈ V , Ji .
The players’ actions are denoted as follows:
• x = (xi , x−i ) ∈ Ω: All players actions,
• xi ∈ Ωi : Player i’s action, ∀i ∈ V ,
Q
• x−i ∈ Ω−i :=
j∈V \{i} Ωj :All players’ actions except i.
The local data of player i is given as Ai := [Aii , [Aij ]j6=i ] ∈
Rm×N with Aii ∈ Rm , and bi ∈ Rm . Note that in this work,
we are interested in a more general case in which each player
has access only to his own private constraint which has not
to be shared with the other players.
Assumption 1. 1 There exists a positive semi-definite matrix
B i ∈ Rm×m for all i ∈ V such that,
Aii ∈ ker(B i − Im ), Aij ∈ ker(B i ) j 6= i.

(1)

Player i’s feasible strategy set is then denoted by
Xi (x−i ) := {xi ∈ Ωi |Ai x = bi }2 .
The game is played such that for a given x−i ∈ Ω−i ,
each player i ∈ V aims to minimize his own cost function
selfishly w.r.t. xi subject to a private equality constraint.
(
minimize Ji (xi , x−i )
xi
(2)
s.t.
xi ∈ Xi (x−i ).
Each optimization problem is run by a particular player i at
the same time with other players. Note that (2) can simply
accommodate inequality constraints Ai x ≥ bi by adding a
slack variable y ≥ 0 and rewrite the inequality constraint as
Ai x−y = bi . Note that the constraint y ≥ 0 can be enforced
by a convex indicator function.
1 Derivation of the algorithm is not dependent on Assumption 1. Simulations for various cases for matrix Ai , even the ones that do not satisfy this
assumption, verify that the algorithm works even without considering this
assumption. However, this assumption is used at the convergence proof.
2 This case contains games with shared constraints for which Ax = b for
all i ∈ V and m ≥ N

An NE of a game is defined as follows:
Definition 1. Consider an N -player game G(V, Ωi , Ji ), each
player i minimizing the cost function Ji : Ω → R. A vector
x∗ = (x∗i , x∗−i ) ∈ Ω is called a GNE of this game if
Ji (x∗i , x∗−i ) ≤ Ji (xi , x∗−i ) ∀xi ∈ Xi (x∗−i ), ∀i ∈ V.

(3)

An NE lies at the intersection of all solutions of the set
(2). The key challenges are two-fold. First, each optimization
problem in (2) is dependent on the solution of the other
simultaneous problems; second, the solutions are coupled
through a linear constraint.
Since this game is distributed, no player is aware of the
actions, cost functions and constraints of the other players.
Thus, each player i maintains an estimate of the other
players’ actions. We define a few notations, in the following,
for players’ estimates.
i
i
i
• x = (xi , x−i ) ∈ Ω: Player i’s estimate of all players
actions,
i
• xi ∈ Ωi : Player i’s estimate of his own action which is
i
indeed his action,
Q i.e., xi = xi ∀i ∈ V ,
i
• x−i ∈ Ω−i :=
j∈V \{i} Ωj : Player i’s estimate of all
other players’ actions except his action,
T
1T
, . . . , xN ]T ∈ ΩN : Augmented vector of
• x = [x
estimates of all players’ actions
Note that all players’ actions can be interchangeably represented as x = (xii )i∈V .
We assume that the cost function Ji , the action set Ω and
the problem data Ai , bi are the only information available to
player i. Thus, the players exchange their estimates in order
to update their actions. An undirected communication graph
GC (V, E) is defined with E ⊆ V × V denoting the set of
communication links between the players. (i, j) ∈ E if and
only if players i and j exchange estimates. In the following,
we have a few definitions for GC :
• Ni := {j ∈ V |(i, j) ∈ E}: Set of neighbors of i in GC ,
• H := [hij ]i,j∈V : Adjacency matrix associated with GC
where hij = 1 if (i, j) ∈ E and hij = 0 otherwise,
• D := diag{|N1 |, . . . , |NN |}: Degree matrix associated
with GC .
The following assumption is used for GC .
Assumption 2. GC is a connected graph.
We aim to link game (2) to a set of optimization problems
whose solutions can be based on the ADMM. Game (2) is
equivalently represented as the following problem for i ∈ V .
(
min Ji (xi , x−i )
xi ∈Ωi
(4)
s.t. Ai x = bi .
Let λ ∈ Rm be the joint Lagrange dual variable associated
with the linear constraint Ai x = bi ∀i ∈ V . The Lagrange
dual problem of (4) can be written as follows for i ∈ V .
n
maxm min Ji (xi , x−i ) + λT (Ai x − bi ).
(5)
λ∈R xi ∈Ωi

Note that we are interested in computing a variational
GNE of the game since we assumed a common Lagrange

multiplier λ for each player in (5). Using the estimates
of the actions xi and the local copies of the Lagrange
dual variables λi for i ∈ V , we reformulate (5) so that
the objective function is separable (the estimates are also
interpreted as the local copies of x). Moreover, the slack
variables tls |{l∈V, s∈Nl } ∈ Ω and pls |{l∈V, s∈Nl } ∈ Rm are
employed to enforce that the local copies are equivalent.

T

Ji(xii , xi−i )+IΩi (xii )+λi (Ai xi −bi )
max
min


i
i
m
ls
ls

λ ∈R ,p xi ∈Ωi ,t





s.t.
xl = tls ∀l ∈ V, ∀s ∈ Nl ,
xs = tls











∀l ∈ V, ∀s ∈ Nl ,

l

ls

∀l ∈ V, ∀s ∈ Nl ,

s

ls

∀l ∈ V, ∀s ∈ Nl ,

λ =p

λ =p

(6)
i
0
if
x
∈
Ω
i
i
is an indicator function
where IΩi (xii ) :=
∞ otherwise
of the feasibility constraint xii ∈ Ωi . Note that the solution
of (6) is equivalent to that of (5), i.e., xii = xi , λi = λ
for all i ∈ V . The ADMM is then employed to solve (6)
in a distributed manner. A characterization of the NE for
game (2) could be obtained by finding the KKT conditions on
(6). Let {uls , v ls , wls , z ls }l∈V,s∈Nl with uls , v ls ∈ RN and
wls , z ls ∈ Rm be the Lagrange multipliers associated with
the four constraints in (6), respectively. The corresponding
Lagrange function for player i, ∀i ∈ V is as follows:


Li xii , {tls , uls , v ls }, λi , {pls , wls , z ls }
(

T

:= Ji (xii , xi−i ) + IΩi (xii ) + λi (Ai xi − bi )
XX
T
T
+
uls (xl − tls ) + v ls (xs − tls ),
l∈V s∈Nl

−

XX

T

T

wls (λl − pls ) + z ls (λs − pls ).

(7)

l∈V s∈Nl
∗

∗

∗

∗

∗

∗

Let (xi , λi )i∈V and {uls , v ls , wls , z ls }l∈V, s∈Nl be a
pair
and dual optimal
to (6). Let denote
P of primal
P solution
ij
ji
i
ij
u
+
v
:=
U
and
w
+ z ji := W i for
j∈Ni
j∈Ni
notational simplicity. The KKT conditions are summarized
as follows for i ∈ V, j ∈ Ni :

∗
∗
∗T
∗
∇i Ji (xi ) + ∂IΩi (xii ) + λi Aii + Uii = 0,



Ai xi ∗ − bi − W i ∗ = 0 ,
m
(8)
i∗
j∗
i∗
j∗

x
=
x
,
λ
=
λ
,


 ij ∗
∗
∗
∗
u + v ij = 0N , wij + z ij = 0m ,
where ∇i Ji (·) is gradient of Ji w.r.t. xi and ∂i IΩi (·) is a
∗
subgradient of IΩi at xi . By (8) and Assumption 2, x1 =
N∗
∗
1∗
N∗
∗
. . . = x := x and λ = . . . = λ := λ . Then, the GNE
of (2), x∗ , satisfies the following equations ∀i ∈ V, j ∈ Ni :

∗
∗
∗T i
i∗

∇i Ji (x ) + ∂IΩi (xi ) + λ Ai + Ui = 0,
∗
(9)
Ai x∗ − bi − W i = 0m ,

∗
∗
 ij
ij
ij ∗
ij ∗
u + v = 0N , w + z = 0m .
In the following, we state a few assumptions for the existence
of a GNE.

Assumption 3. For every i ∈ V ,
• Ωi ⊂ R is compact and convex
• Xi (x−i ) is non-empty for every x−i
1
• Ji (xi , x−i ) is C in xi , jointly continuous in x and
convex in xi , for every x−i .
The convexity of Ωi implies that the indicator function IΩi
is convex. This yields that there exists at least one bounded
subgradient ∂IΩi .
Assumption 4. Let F : ΩN → RN , F (x) := [∇i Ji (xi )]i∈V
be the pseudo-gradient vector (game map) where x :=
T
T
[x1 , . . . , xN ]T ∈ ΩN . F is cocoercive ∀x ∈ ΩN and
y ∈ ΩN , i.e.,
(F (x) − F (y))T (x − y) ≥ σF kF (x) − F (y)k2 , (10)
where σF > 0.
III. D ISTRIBUTED I NEXACT-ADMM A LGORITHM
Our objective is to find an ADMM-like algorithm for
computing a GNE of G(V, Ωi , Ji ) using only imperfect
information over the communication graph GC (V, E).
The algorithm is elaborated in the following steps:
1- Initialization Step: Each player i ∈ V maintains an
initial estimate for all players’ actions, xi (0) ∈ Ω and an
initial Lagrange multiplier, λi (0) ∈ Rm . The initial values
of uij (0), v ij (0), wij (0) and z ij (0) are all set to be zero for
all i ∈ V , j ∈ Ni .
2- Communication Step: At iteration T (k), each player
i ∈ V exchanges his previous estimate of the other players’
actions xi (k − 1) and his dual Lagrange multiplier λi (k − 1)
with his neighbors j ∈ Ni .
3- Action Update Step: At this moment all players update
their actions, estimates and Lagrange multiplier via the
ADMM. For each player i ∈ V , let the augmented Lagrange
function associated with (6) be as follows:


Lai xii , {tls , uls , v ls }, λi , {pls , wls , z ls }
T

:= Ji (xii , xi−i ) + IΩi (xii ) + λi (Ai xi − bi )
XX
T
T
+
uls (xl − tls ) + v ls (xs − tls )
l∈V s∈Nl

−

XX

T

T

wls (λl − pls ) + z ls (λs − pls )

l∈V s∈Nl

cXX
+
(kxl − tls k2 + kxs − tls k2 )
2
l∈V s∈Nl
cXX
−
(kλl − pls k2 + kλs − pls k2 ),
2

(11)

l∈V s∈Nl

where c > 0 is a scalar coefficient. Consider the ADMM
algorithm associated with (6) based on (11):
The dual Lagrange multipliers uij , v ij , wij , z ij update
rules ∀i ∈ V, j ∈ Ni are as follows:

c
uij (k) = uij (k − 1) + xi (k − 1) − xj (k − 1) , (12)
2

c
v ij (k) = v ij (k − 1) + xj (k − 1) − xi (k − 1) , (13)
2

c
ij
ij
w (k) = w (k − 1) + λi (k − 1) − λj (k − 1) , (14)
2

z ij (k) = z ij (k − 1) +


c j
λ (k − 1) − λi (k − 1) .
2

(15)

as follows:
n
xii (k) = arg min
max
Ji (xii , xi−i (k − 1)) + IΩi (xii )
i
i
xi

The update rule for the slack variable tij ∈ RN , ∀i ∈
V, j ∈ Ni , which is based on (11), is as follows:

a
i
ls
ls
ls
tij (k) = arg min
L
i x (k − 1), {t , u (k), v (k)},
tij

λi (k − 1), {pls (k − 1), wls (k), z ls (k)}
n
− (uij (k) + v ij (k))T tij
= arg min
tij
o
c
+ (kxi (k − 1) − tij k2 + kxj (k − 1) − tij k2 )
2
1
1
= (uij (k) + v ij (k)) + (xi (k − 1) + xj (k − 1)).(16)
2c
2
The initial conditions uij (0) = v ij (0) = 0N ∀i ∈ V, j ∈ Ni
along with (12) and (13) suggest that uij (k) + v ij (k) = 0N
∀i ∈ V, j ∈ Ni , k > 0. Then, (16) yields,
tij (k) =

xi (k − 1) + xj (k − 1)
.
2

(17)

Similarly the update rule for pij ∈ Rm ∀i ∈ V, j ∈ Ni is
represented as the following:
λi (k − 1) + λj (k − 1)
.
(18)
2
The local estimate update for all i ∈ V is a min-max
optimization problem based on (11).

a
xii (k) = arg min
max
L
xii , {tls (k), uls (k), v ls (k)}, λi ,
i
xii ∈R λi ∈Rm

{pls (k), wls (k), z ls (k)}
n
= arg min
max
Ji (xii , xi−i (k − 1)) + IΩi (xii )
i
i
pij (k) =

xi

T

T

+Uii (k)T xii − W i (k)T λi
X
xi (k − 1) + xji (k − 1)
+c
xii − i
2
λi −

j∈Ni

λi (k − 1) + λj (k − 1)
2

j∈Ni
iT

2o

∀i ∈ V.

(19)

xii −

λ

xii (k − 1) + xji (k − 1)
2

2

+ Uii (k)T xii

(20)



Aii xii + Ai−i xi−i (k − 1) − bi − W i (k)

o
X
+c
(λi (k − 1) + λj (k − 1)) − c|Ni |kλi k2
+λ

j∈Ni

Substituting back (22) into (21), we obtain,
n
xii (k) = arg min
Ji (xii , xi−i (k − 1)) + IΩi (xii )
i
xi

+c

X
j∈Ni

+

1
4c|Ni |

xii (k − 1) + xji (k − 1) 2
+ Uii (k)T xii
2
X
c
(λi (k − 1) + λj (k − 1))

xii −

j∈Ni

i

−W (k) + Aii xii + Ai−i xi−i (k − 1) − bi

2o

.

(23)

T
nh
Aii  i i
∇i Ji (xi (k − 1)) +
A x (k − 1)
2c|Ni |
xi
iT
X
−bi − W i (k) + c
(λi (k − 1) + λj (k − 1))
.
j∈Ni

xi

X

Only the third line of (21) is dependent on λi which is the
maximization variable. Thus, to maximize (21) w.r.t. λi , we
let λi (k) be as follows:
1  i i
λi (k) =
A x (k) + Ai−i xi−i (k − 1) − bi
2c|Ni | i i
X λi (k − 1) + λj (k − 1) 
.
(22)
−W i (k) + 2c
2

xii (k) = arg min
i

In the derivation of (19), we used (17) and (18). The next
min-max problem is equivalent in the sense that its solutions
for xii and λi are equivalent to the solutions of (19).
n
xii (k) = arg min
max
Ji (xii , xi−i (k − 1)) + IΩi (xii )
i
i
+c

xii −

2

j∈Ni

X

X

We simplify (23) by using a proximal first-order approximation for Ji (xii , xi−i (k − 1)) and the last term in (23) around
xi (k − 1); thus using inexact ADMM it follows:

−λi bi + λi Aii xii + λi Ai−i xi−i (k − 1)

−c

xii (k − 1) + xji (k − 1) 2
+ Uii (k)T xii
2
j∈Ni
1 h X i
(λ (k − 1) + λj (k − 1))
−c|Ni | λi −
c
2c|Ni |
j∈Ni
i 2
i
i i
i
−W (k) + Ai xi + A−i xi−i (k − 1) − bi
X
1
+
c
(λi (k − 1) + λj (k − 1))
4c|Ni |
j∈Ni
2o
.
(21)
−W i (k) + Aii xii + Ai−i xi−i (k − 1) − bi
+c

λ

T

λ

∀i ∈ V.

j∈Ni

For the last two lines of (20), we complete the squared term

βi i
kx − xii (k − 1)k2 + IΩi (xii )
2 i
o
X
xi (k − 1) + xji (k − 1) 2
+c
xii − i
+ Uii (k)T xii , (24)
2
.(xii

−

xii (k

− 1)) +

j∈Ni

where βi > 0 is a penalty factor for the proximal first-order
approximation for i ∈ V . We obtain an equivalent problem
to (24) in the following such that its gradient w.r.t. xii is
equivalent to that of (24).
n

αi i
−1
i
xii (k) = arg min
I
(x
)
+
x
−
α
βi xii (k − 1)
Ω
i
i
i
2 i
xii

−∇i Ji (xi (k − 1)) − Uii (k) + c

X

(xii (k − 1) + xji (k − 1))

j∈Ni
T
Aii

1:



Ai xi (k − 1) − bi − W i (k)
2c|Ni |
 2 o
X
,
λi (k − 1) + λj (k − 1)
+c

−

Algorithm 1 ADMM Algorithm

2:
3:

(25)

4:

j∈Ni

where αi := βi + 2c|Ni |. Let proxag [s] := arg minx {g(x) +
− sk2 } be the proximal operator for the non-smooth
i
function g. Note that proxα
IΩi [s] = TΩi [s] where TΩi : R →
Ωi is an Euclidean projection. Then for each player i, ∀i ∈ V
we obtain,
h

xii (k) = TΩi αi−1 γi xii (k − 1) − ∇i Ji (xi (k − 1)) − Uii (k)
a
2 kx

5:
6:
7:

initialization xi (0) ∈ Ω, λi (0) ∈ Rm , U i (0) = 0N and
W i (0) = 0m ∀i ∈ V
for k = 1, 2, . . . do
for each player i ∈ V do
players i, j ∀j ∈ Ni exchange xi (k − 1),
xj (k − 1), λi (k − 1)Pand λj (k − 1).
U i (k) = U i (k−1)+c j∈Ni (xi (k−1)−xj (k−1))
P
i
j
W i (k) = W ih(k−1)+c
j∈Ni (λ (k−1)−λ (k−1))

xii (k) = TΩi αi−1 γi xii (k −1)−∇i Ji (xi (k −1))
P
−Uii (k) + c j∈Ni xji (k − 1)

T
Aii
Ai−i xi−i (k − 1) − bi − W i (k)
− 2c|N
i|
i
P
+c j∈Ni λi (k − 1) + λj (k − 1)

1
λi (k) = 2c|N
Aii xii (k) + Ai−i xi−i (k − 1) − bi
i|

i
j
P
(k−1)
−W i (k) + 2c j∈Ni λ (k−1)+λ
2

T

Aii  i i
A x (k − 1) − bi − W i (k)
2c|Ni | −i −i
j∈Ni
i
X
+c
λi (k − 1) + λj (k − 1)
,
(26)

+c

X

xji (k − 1) −

8:

xi−i (k) =
10:
end for
11: end for

P

9:

j∈Ni
T

1
where γi := βi + c|Ni | − 2c|N
Aii Aii .
i|
Eventually, after updating his action and dual Lagrange
multiplier, each player i takes average of the received information with his estimate and updates his estimate as follows:

1
1 X j
1
xi−i (k) = xi−i (k−1)+
U i (k),
x−i(k−1) −
2
|Ni |
2c|Ni | −i
j∈Ni
|
{z
}
{z
}
|
RECEIVED INFORMATION

PENALTY TERM

(27)
where c > 0 is a scalar coefficient which is also used in (11).
Note that in (27), the penalty term is associated with the
difference between the estimates of the neighboring players
(Equations (12), (13)).
Then the ADMM algorithm is represented as in Algorithm 1.
IV. C ONVERGENCE P ROOF
Theorem 1. Let βi > 0 be player i’s penalty factor of
the approximation in the inexact ADMM Algorithm 1 which
satisfies
1
σF >
,
(28)
kAi k2
2βi − c|Ni i |
where σF is a positive constant for the cocoercive property
of F , Aii is player i’s problem data and Ni is the number of
neighbors of player i. Under Assumptions 1-4, the sequence
{xi (k)} ∀i ∈ V , generated by Algorithm 1 converges to x∗
NE of game (2).
Proof . From step 7 in Algorithm 1, we obtain the following optimality condition:

+2c

X
j∈Ni

xii (k) −

j∈Ni

xj−i (k−1))
|Ni |

−

i
U−i
(k−1)
2c|Ni |

xii (k − 1) + xji (k − 1) 
= 0 ∀i ∈ V,
2

Adding and subtracting Aii xii (k) from the second line of (29)
and using (22), it leads to
T

∇i Ji (xi (k − 1)) + ∂i IΩi (xii (k)) + Aii λi (k)
+δi (xii (k) − xii (k − 1)) + Uii (k)
(30)
j

i
X
x (k − 1) + xi (k − 1)
+2c
= 0 ∀i ∈ V,
xii (k) − i
2
j∈Ni

T

1
Aii Aii . Adding the first Nash
where δi := βi − 2c|N
i|
condition (9) and multiplying by (xii (k) − x∗i ), we obtain,

T
∇i Ji (xi (k − 1)) − ∇i Ji (x∗ ) (xii (k − 1) − x∗i )

T
+ ∇i Ji (xi (k − 1)) − ∇i Ji (x∗ ) (xii (k) − xii (k − 1))

T
+ ∂i IΩi (xii (k)) − ∂i IΩi (x∗i ) (xii (k) − x∗i )

T
+ λi (k) − λ∗ Aii (xii (k) − x∗i )
(31)

+δi (xii (k) − xii (k − 1))T (xii (k) − x∗i )


∗ T
+ Uii (k) − Uii
(xii (k) − x∗i )
X
xi (k − 1)+xji (k − 1)T i
+2c
xii (k)− i
(xi (k)−x∗i ) = 0
2
j∈Ni

∇i Ji (xi (k − 1)) + βi (xii (k) − xii (k − 1)) + ∂i IΩi (xii (k))
T
Ai  i i
+ i
A x (k − 1) − bi − W i (k)
(29)
2c|Ni |

X
+c
(λi (k − 1) + λj (k − 1)) + Uii (k)
j∈Ni

On the other hand, from (22) we obtain,
0m = −Aii xii (k) − Ai−i xi−i (k − 1) + bi
X
λi (k) + λj (k)
+W i (k) + 2c
λi (k) −
2
j∈Ni

X

+c

(λi (k) + λj (k) − λi (k − 1) − λj (k − 1)),(32)

j∈Ni
i

i

Note that by (14) and (15), W (k + 1) = W (k) +
i
j
P
(k)
2c j∈Ni λi (k) − λ (k)+λ
. Then, We add the second
2
Nash condition (9) to (32). Moreover, using Assumption 1,
there exists a matrix B i such that we multiply into (32) and
then multiply the result by (λi (k) − λ∗ ).
T

0 = −(xii (k) − x∗i )T Aii (λi (k) − λ∗ )


∗ T iT
B (λi (k) − λ∗ )
+ W i (k + 1) − W i
X
+c
(λi (k) + λj (k) − λi (k − 1) − λj (k − 1))T
.B

(λi (k) − λ∗ ).

j∈Ni
iT
i

(λ (k) − λ∗ )
X
(λi (k) + λj (k) − λi (k − 1) − λj (k − 1))T
+c

.B

j∈Ni

(33)

(λi (k) − λ∗ ).
T
X
xi (k) + xj (k) − xi (k − 1) − xj (k − 1)
+c

.B

The second and third terms are bounded as follows:

T
∇i Ji (xi (k − 1))−∇i Ji (x∗ ) (xii (k)−xii (k − 1)) ≥ (37)
ρ
−1
k∇i Ji (xi (k − 1))−∇i Ji (x∗ )k2 − kxii (k)−xii (k − 1)k2 ,
2ρ
2

(∂IΩi (xii (k)) − ∂IΩi (x∗i ))T (xii (k) − x∗i ) ≥ 0.

1
1
kF (x(k − 1)) − F (x∗ )k2 − kx(k) − x(k − 1)k2M1
2ρ
2
+(x(k) − x(k − 1))T diag((δi ei eTi )i∈V )(x(k) − x∗ )
X X ij
∗
ji ∗ T i
∗
+
(ui (k + 1)+viji (k + 1)−uij
i −vi ) (xi (k)−xi)
−

j∈Ni

(λi (k) − λ∗ )
(34)
j

i
X
T
x (k − 1)+xi (k − 1)
(xii (k)−x∗i ) = 0.
+2c
xii (k)− i
2
j∈Ni

The last equation that we need to add it to (34) is the one
associated with xi−i , (27), and multiplied by (xi−i − x∗−i ).

XX

ji
T
i
∗
(uij
−i (k + 1) + v−i (k + 1)) (x−i (k) − x−i )

i∈V j∈Ni

2
T
+ (w(k + 1) − w∗ )T diag((B i )i∈V )(w(k + 1) − w(k))
c
+c(λ(k) − λ(k − 1))T ((D + H) ⊗ Im )
.((D + H) ⊗ IN )(x(k) − x∗ ) ≤ 0,

(39)
∗T

(35)

Adding (35) to (34), and using (12) and (13) for simplification, we obtain,

T
∇i Ji (xi (k − 1)) − ∇i Ji (x∗ ) (xii (k − 1) − x∗i )

T
+ ∇i Ji (xi (k − 1)) − ∇i Ji (x∗ ) (xii (k) − xii (k − 1))

T
+ ∂i IΩi (xii (k)) − ∂i IΩi (x∗i ) (xii (k) − x∗i )
+δi (xii (k) − xii (k − 1))T (xii (k) − x∗i )
X ij
∗
ji ∗ T i
∗
+
(ui (k + 1)+viji (k + 1)−uij
i −vi ) (xi (k)−xi )
j∈Ni
j∈Ni

+

T

j∈Ni

ji
T
i
∗
(uij
−i (k + 1) + v−i (k + 1)) (x−i (k) − x−i )

i∈V j∈Ni

.diag((B i )i∈V )(λ(k) − λ∗ ) + c(x(k) − x(k − 1))T

i
U−i
(k)T (xi−i (k) − x∗−i )
X
xi (k − 1) + xj−i (k − 1) T
+2c
xi−i (k) − −i
2

X

(38)

Using (37) and (38) in (36) and summing over i ∈ V , we
obtain,
T

F (x(k − 1)) − F (x∗ ) (x(k − 1) − x∗ )

iT

+

(36)

for any ρ > 0 ∀i ∈ V . By the convexity of IΩi (Assumption 3), we have for the third term,

+δi (xii (k) − xii (k − 1))T (xii (k) − x∗i )


∗ T
+ Uii (k) − Uii
(xii (k) − x∗i )

∗
T
+ W i (k + 1) − W i )T B i (λi (k) − λ∗ )
X
+c
(λi (k) + λj (k) − λi (k − 1) − λj (k − 1))T .

.(xi−i (k) − x∗−i ) = 0.

iT

j∈Ni

Adding (33) to (31), it yields,

T
∇i Ji (xi (k − 1)) − ∇i Ji (x∗ ) (xii (k − 1) − x∗i )

T
+ ∇i Ji (xi (k − 1)) − ∇i Ji (x∗ ) (xii (k) − xii (k − 1))

T
+ ∂i IΩi (xii (k)) − ∂i IΩi (x∗i ) (xii (k) − x∗i )

.B

∗

∗

(wij (k + 1) + z ji (k + 1) − wij − z ji )T

.(xii (k) − x∗i ) = 0.

j∈Ni
iT

X

+

∗T

where M1 := diag((ρei eTi )i∈V ), x∗ = [x1 , . . . , xN ]T ,
T
∗T
T
∗T
λ = [λ1 , . . . , λN ]T and P
λ∗ = [λ1 , . . . , λN ]T . Moreover, w = (wi )i∈V ∈ Rm i∈V |Ni | and wi =P(wij )j∈Ni ∈
∗
Rm|Ni | and also w∗ = (wi )i∈V ∈ Rm i∈V |Ni | and
∗
∗
wi = (wiij )j∈Ni ∈ Rm|Ni | .
We bound
the first term using
TAssumption 4,

∗
F (x(k − 1)) − F (x ) (x(k − 1) − x∗ )
≥ σF kF (x(k − 1)) − F (x∗ )k2 .

(40)

We also simplify the fourth and the fifth lines in
(39).
GC is P
an undirected
graph, for any {aij },
P Since
P
P
a
=
a
. Then,
ij
ji
i∈V
i∈V
j∈Ni
i
X
X j∈N
∗
ij
ji
ij ∗
(ui (k + 1)+vi (k + 1)−ui −viji )T(xii (k)−x∗i )
i∈V j∈Ni

+

XX
i∈V j∈Ni

ji
T
i
∗
(uij
−i (k + 1) + v−i (k + 1)) (x−i (k) − x−i )

=

XX

+

XX

∗

ij T
i
∗
(uij
i (k + 1) − ui ) (xi (k) − xi )

i∈V j∈Ni
∗

(viij (k + 1) − viij )T (xji (k) − x∗i )

i∈V j∈Ni

+

XX

T
i
∗
uij
−i (k + 1) (x−i (k) − x−i )

i∈V j∈Ni

+

XX

ij
(k + 1)T (xj−i (k) − x∗−i ).
v−i

(41)

i∈V j∈Ni

Note that by (12) and (13) as well as the initial conditions for
Lagrange multipliers uij (0) = v ij (0) = 0N ∀i ∈ V, j ∈ Ni ,
we obtain,
uij (k) + v ij (k) = 0N

∀i ∈ V, j ∈ Ni , k > 0.

(42)

Substituting
and using (9), we obtain,
X X ij(42) into (41)
∗ T
j
i
(ui (k + 1) − uij
i ) (xi (k) − xi (k))
i∈V j∈Ni

+

XX

j
T
i
uij
−i (k + 1) (x−i (k) − x−i (k))

i∈V j∈Ni

=

∗
2 X X ij
T
ij
ij
(u (k + 1) − uij
i ei ) (u (k + 1) − u (k))
c
i∈V j∈Ni

2
:= (u(k + 1) − u∗ )T (u(k + 1) − u(k)),
c

(43)

P

i
ij
where u = (ui )i∈V ∈ RN i∈V |Ni | and
P u = (u )j∈N∗i ∈
|N
|
N
∗
i∗
N |Ni |
i
i∈V
and ui =
R
and also u = (u )i∈V ∈ R
ij ∗
(ui )j∈Ni ⊗ ei ∈ RN |Ni | . Using (40) and (43), for ρ = 2σ1F
(39) becomes,
1
− kx(k) − x(k − 1)k2M1
2
+(x(k) − x(k − 1))T M2 (x(k) − x∗ )
∗

T

+(λ(k) − λ(k − 1)) Q(λ(k) − λ )
2
+ (u(k + 1) − u∗ )T (u(k + 1) − u(k))
c
2
+ (w(k + 1) − w∗ )T B(w(k + 1) − w(k)) ≤ 0, (44)
c


where M2 := diag (δi ei eTi )i∈V + c((D + H) ⊗ IN ), B :=
T

o
1
1
+ ku(k + 1) − u∗ k2 + kw(k + 1) − w∗ k2B ≤
c
c
n1
1
∗ 2
kx(k − 1) − x kM2 + kλ(k − 1) − λ∗ k2Q
2
2
o
1
1
∗ 2
+ ku(k) − u k + kw(k) − w∗ k2B
c
c
1
1
− kx(k) − x(k − 1)k2M2 −M1 − kλ(k) − λ(k − 1)k2Q
2
2
1
1
2
− ku(k + 1) − u(k)k − kw(k + 1) − w(k)k2B . (47)
c
c
By the condition (28), M2 − M1  0. Then (47) implies the
following two results:
1) 12 kx(k) − x∗ k2M2 + 12 kλ(k) − λ∗ k2Q + 1c ku(k + 1) −
u∗ k2 + 1c kw(k + 1) − w∗ k2B → θ, for some θ ≥ 0,


x(k) − x(k − 1) → 0N 2

λ(k) − λ(k − 1) → 0
mN
2)
.
u(k + 1) − u(k) → 0N Pi∈V |Ni |



w(k + 1) − w(k) → 0m Pi∈V |Ni |
Result
1
implies
that
the
sequences
{xi (k)}, {λi (k)}, {uij (k)} and {wij (k)} (similarly
{v ij (k)} and {z ij (k)}) are bounded and have limit points
denoted by x̄i , λ̄i , ūij and w̄ij (v̄ ij and z̄ ij ), respectively.
Then, we obtain,
1
1
θ = kx̄(k) − x∗ k2M2 + kλ̄(k) − λ∗ k2Q
2
2
1
1
∗ 2
+ kū(k + 1) − u k + kw̄(k + 1) − w̄∗ k2B (48)
c
c
Result 2 along with (12) and (14) yield ∀i ∈ V, j ∈ Ni ,
x̄i = x̄j := x̄, λ̄i = λ̄j := λ̄
Moreover, by (42) we arrive at,
ūij + v̄ ij = 0N

∀i ∈ V, j ∈ Ni .

c((D + A) ⊗ IN ) = c((D (2I − LN )D ) ⊗ IN ),
1

1

1

(45)

1
(a(k) − a(k − 1)) M (a(k) − a ) = ka(k) − a∗ k2M
2
1
1
2
+ ka(k) − a(k − 1)kM − ka(k − 1) − a∗ k2M .
(46)
2
2
Then (44) becomes,
n1
1
kx(k) − x∗ k2M2 + kλ(k) − λ∗ k2Q
2
2
∗

i

A x̄ − b −

X

ij

w̄ + z̄ ji = 0m .

(52)

j∈Ni

1

where L := D − H, D 2 , D− 2 and LN := D− 2 LD− 2 are
the Laplacian of GC , the square root and reciprocal square
root of D and the normalized Laplacian of GC , respectively.
1
Since D  0, D− 2 exist, it is shown in that λmax (LN ) ≤ 2.
Then (45) yields that c((D + H) ⊗ IN )  0. This concludes
M2  0. Moreover, by Assumption 1, B  0. We use the
following inequality in (44) for every {a(k)} and M  0:
T

j∈Ni
i

1
2

(50)

Similarly, w̄ij + z̄ ij = 0m ∀i ∈ V, j ∈ Ni . Result 2 also
implies that by (49), (30) and (32):
X ij
∇i Ji (x̄) + ∂IΩi (x̄i ) +
(ūi + ṽiji ) = 0, (51)

diag((B i )i∈V ) and Q := c((D + H) ⊗ IN )B. Note that,
1
2

(49)

Comparing (49)-(52) with (9), it follows ∀i ∈ V, j ∈ Ni ,
x̄i = x∗ (x̄ = x∗ ), λ̄i = x∗ (λ̄ = λ∗ ),
ij

ij ∗

ū = u

∗

(ū = u ), w̄

ij

=w

ij ∗

(53)
∗

(w̄ = w ).

This completes the proof.

(54)


V. S IMULATION R ESULTS
In this section, we simulate our algorithm for a wireless
ad-hoc network (WANET). Consider a WANET with 16
nodes and 16 multi-hop communication links as in Fig. 1 (a).
There are 15 users who aim to transfer data from a source to
a destination. Solid line represents a link Lj , j ∈ {1, . . . , 16}
and dashed line displays a path Ri , i ∈ {1, . . . , 15} that is
assigned to user i to transfer data. Each link Lj has a positive

1
12
R7 L8 R6
R14 L9
R8

13

3
L10

L15

L11
R10
L12
9

L6

L14

R9
16

14

L4

L13

15

2

11

13

3

4

10

4

R3
5

R11

1

R4

L5

R15
L16

12
R5

11

10

VI. C ONCLUSIONS

2
L7

9

14

5

8

7

6

15 R13

8

R2

L3

L1

R12 L2 R1

6

7

Fig. 1: (a) Wireless Ad-Hoc Network (left). (b) Communication graph GC (right).
9
8
7
User Flow Rate

6
5
4
3
2
1
0

500

1000

1500

2000

Iteration

Fig. 2: Flow rates of users 1, 3, 5, 15. GNE points are
represented by black stars.
capacity Cj > 0 that restricts the users’ data flow . The data
flow of user i is denoted by xi such that 0 ≤ xi ≤ 10. For
each user i, a cost function Ji is defined as in [7]:
X
κ
P
Ji (xi , x−i ) :=
−χi log(xi +1),
Cj − w:Lj ∈Rw xw
j:Lj ∈Ri

where κ > 0 and χi > 0 are network-wide known and userspecific parameters, respectively.
The problem is to find a GNE of the game which is played
over a communication graph GC (depicted in Fig. 1 (b)). We
assume a common constraint x1 + x3 + x5 = 14 between the
players. It is straightforward to check the Assumptions 2,3
and 4 on GC and the cost functions. The users’ flow rate and
the dual Lagrange multipliers (they converge to 0) as well
as the normalized error are shown in Fig. 2 and Fig. 3 for
χi = 15 ∀i ∈ {1, . . . , 15} and Cj = 15 ∀j ∈ {1, . . . , 16}.
2

0

λi

−2

−4

−6

−8
0

500

1000

1500

2000

Iteration

Fig. 3: Dual Lagrange multipliers for users 1, 3, 5, 15.
0

Normalized Error ||x(k)−x*||/||x*||

10

−2

10

−4

10

−6

10

0

500

1000

1500

2000

Iteration

Fig. 4: Normalized error of the users’ data flow.

A distributed GNE seeking algorithm is designed within
the framework of inexact-ADMM. Each player is only aware
of his own cost function, problem data and action set of
all players. Each player exchanges the estimates of other
players’ actions along with the local copy of his Lagrange
multiplier with his communication neighbors. An inexactADMM algorithm is then derived to find a GNE of the game.
Convergence of the algorithm is then provided under mild
conditions on cost functions.
R EFERENCES
[1] M. Zhu and E. Frazzoli, “Distributed robust adaptive equilibrium
computation for generalized convex games,” Automatica, vol. 63, pp.
82–91, 2016.
[2] L. Pavel, “An extension of duality to a game-theoretic framework,”
Automatica, vol. 43, no. 2, pp. 226–237, 2007.
[3] Z. Han, Game theory in wireless and communication networks: theory,
models, and applications. Cambridge University Press, 2012.
[4] T. Alpcan and T. Başar, “Distributed algorithms for Nash equilibria
of flow control games,” in Advances in Dynamic Games. Springer,
2005, pp. 473–498.
[5] F. Facchinei and C. Kanzow, “Generalized Nash equilibrium problems,” Annals of Operations Research, vol. 175, no. 1, pp. 177–211,
2010.
[6] A. Fischer, M. Herrich, and K. Schönefeld, “Generalized Nash equilibrium problems-recent advances and challenges,” Pesquisa Operacional, vol. 34, no. 3, pp. 521–558, 2014.
[7] F. Salehisadaghiani and L. Pavel, “Distributed Nash equilibrium seeking by gossip in games on graphs,” in Decision and Control (CDC),
2016 IEEE 55th Conference on. IEEE, 2016, pp. 6111–6116.
[8] T.-H. Chang, M. Hong, and X. Wang, “Multi-agent distributed optimization via inexact consensus admm,” IEEE Transactions on Signal
Processing, vol. 63, no. 2, pp. 482–497, 2015.
[9] B. Johansson, “On distributed optimization in networked systems,”
Ph.D. Dissertation, 2008.
[10] F. Parise, B. Gentile, S. Grammatico, and J. Lygeros, “Network
aggregative games: Distributed convergence to Nash equilibria,” in
2015 54th IEEE Conference on Decision and Control (CDC). IEEE,
2015, pp. 2295–2300.
[11] F. Salehisadaghiani and L. Pavel, “Distributed Nash equilibrium seeking: A gossip-based algorithm,” Automatica, vol. 72, pp. 209–216,
2016.
[12] P. Yi and L. Pavel, “A distributed primal-dual algorithm for computation of generalized nash equilibria with shared affine coupling constraints via operator splitting methods,” arXiv preprint
arXiv:1703.05388, 2017.
[13] H. Yin, U. V. Shanbhag, and P. G. Mehta, “Nash equilibrium problems
with scaled congestion costs and shared constraints,” IEEE Transactions on Automatic Control, vol. 56, no. 7, pp. 1702–1708, 2011.
[14] D. A. Schiro, J.-S. Pang, and U. V. Shanbhag, “On the solution of
affine generalized Nash equilibrium problems with shared constraints
by lemkes method,” Mathematical Programming, pp. 1–46, 2013.
[15] D. Paccagnan, B. Gentile, F. Parise, M. Kamgarpour, and J. Lygeros,
“Distributed computation of generalized Nash equilibria in quadratic
aggregative games with affine coupling constraints,” in Decision and
Control (CDC), 2016 IEEE 55th Conference on. IEEE, 2016, pp.
6123–6128.
[16] S. Grammatico, “Aggregative control of competitive agents with coupled quadratic costs and shared constraints,” in Decision and Control
(CDC), 2016 IEEE 55th Conference on. IEEE, 2016, pp. 3597–3602.
[17] D. P. Bertsekas and J. N. Tsitsiklis, Parallel and Distributed Computation: Numerical Methods. Athena Scientific, Belmont, Massachusetts,
1997.
[18] S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein, “Distributed
optimization and statistical learning via the alternating direction
method of multipliers,” Foundations and Trends R in Machine Learning, vol. 3, no. 1, pp. 1–122, 2011.
[19] B. He and X. Yuan, “On the o(1/n) convergence rate of the douglasrachford alternating direction method,” SIAM Journal on Numerical
Analysis, vol. 50, no. 2, pp. 700–709, 2012.

[20] E. Wei and A. Ozdaglar, “Distributed alternating direction method of
multipliers,” in 2012 IEEE 51st IEEE Conference on Decision and
Control (CDC). IEEE, 2012, pp. 5445–5450.
[21] F. Salehisadaghiani and L. Pavel, “Distributed Nash equilibrium seeking via the alternating direction method of multipliers,” accepted in
IFAC World Congress, 2017.

