# Methods for Solving Generalized Nash Equilibrium

Authors: Biao Qu; Jing Zhao
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

The generalized Nash equilibrium problem (GNEP) is an extension of the standard Nash equilibrium problem (NEP), in which each player's strategy set may depend on the rival player's strategies. In this paper, we present two descent type methods. The algorithms are based on a reformulation of the generalized Nash equilibrium using Nikaido-Isoda function as unconstrained optimization. We prove that our algorithms are globally convergent and the convergence analysis is not based on conditions guaranteeing that every stationary point of the optimization problem is a solution of the GNEP.


---

## Body

## 1. Introduction

The generalized Nash equilibrium problem (GNEP for short) is an extension of the standard Nash equilibrium problem (NEP for short), in which the strategy set of each player depends on the strategies of all the other players as well as on his own strategy. The GNEP has recently attracted much attention due to its applications in various fields like mathematics, computer science, economics, and engineering [1–11]. For more details, we refer the reader to a recent survey paper by Facchinei and Kanzow [3] and the references therein.Let us first recall the definition of the GNEP. There areN players labelled by an integer v=1,…,N. Each player v controls the variables xv∈Rnv. Let x=(x1⋯xn)T be the vector formed by all these decision variables, where n:=n1+n2+⋯+nv. To emphasize the vth player variable within the vector x, we sometimes write x=(xv,x-v)T∈Rn, where x-v denotes all the other player's variables. In the games, each player controls the variables xv and tries to minimize a cost function θv(xv,x-v) subjects to the constraint (xv,x-v)T∈X with x-v given as exogenous, where X is a common strategy set. A vector x*:=(x*,1,…,x*,N)T is called a solution of the GNEP or a generalized Nash equilibrium, if for each player v=1,…,N, x*,v solves the following optimization problem with x*,-v being fixed:
(1)minxvθv(xv,x*,-v),s.t.(xv,x*,-v)∈X.IfX is defined as the Cartesian product of certain sets Xv∈Rnv, that is, X=X1×X2×⋯×XN, then the GNEP reduces to the standard Nash equilibrium problem.Throughout this paper, we can make the following assumption.Assumption 1.
(a) The setX is nonempty, closed, and convex.
(b) The utility functionθv is continuously differentiable and, as a function of xv alone, convex.A basic tool for both the theoretical and the numerical solution of (generalized) Nash equilibrium problems is the Nikaido-Isoda function defined as(2)Ψ(x,y)=∑v=1N‍[θv(xv,x-v)-θv(yv,x-v)].Sometimes also the name Ky-Fan function can be found in the literature, see [12, 13]. In the following, we state a definition which we have taken from [9].Definition 1.
x
* is a normalized Nash equilibrium of the GNEP, if maxyΨ(x*,y)=0 holds, where Ψ(x,y) denotes the Nikaido-Isoda function defined as (2).In order to overcome the nondifferentiable property of the mappingΨ(x,y), von Heusinger and Kanzow [8] used a simple regularization of the Nikaido-Isoda function. For a parameter α>0, the following regularized Nikaido-Isoda function was considered:
(3)Ψα(x,y)=∑v=1N‍[θv(xv,x-v)-θv(yv,x-v)]-α2∥x-y∥2.
Since under the given Assumption 1, Ψα(x,y) is strongly concave in y, the maximization problem(4)maxyΨα(x,y),s.t.y∈X
has a unique solution for each x, denoted by yα(x).The corresponding value function is then defined by(5)Vα(x)=maxyΨα(x,y)=Ψα(x,yα(x)).Letβ>α>0 be a given parameter. The corresponding value function is then defined by
(6)Vβ(x)=maxyΨβ(x,y)=Ψβ(x,yβ(x)).Define(7)Vαβ(x)=Vα(x)-Vβ(x).In [8], the following important properties of the function Vαβ(x) have been proved.Theorem 2.
The following statements hold:(a)
Vαβ(x)≥0 for any x∈Rn;(b)
x* is a normalized Nash equilibrium of the GNEP if and only if Vαβ(x*)=0;(c)
Vαβ(x) is continuously differentiable on Rn and that
(8)∇Vαβ(x)=∇Vα(x)-∇Vβ(x)=∑v=1N[∇θv(yβ(x)v,x-v)-∇θv(yα(x)v,x-v)]+(∇x1θ1(yα(x)1,x-1)-∇x1θ1(yβ(x)1,x-1)⋮∇xNθN(yα(x)N,x-N)-∇xNθN(yβ(x)N,x-N))-α(x-yα(x))+β(x-yβ(x)).From Theorem2, we know that the normalized Nash equilibrium of the GNEP is precisely the global minima of the smooth unconstrained optimization problem (see [5]) as
(9)minx∈RnVαβ(x)
with zero optimal value.In this paper, we develop two new descent methods for finding a normalized Nash equilibrium of the GNEP by solving the optimization problem (9). The key to our methods is a strategy for adjusting α and β when a stationary point of Vαβ(x) is not a solution of the GNEP. We will show that our algorithms are globally convergent to a normalized Nash equilibrium under appropriate assumption on the cost function, which is not stronger than the one considered in [8].The organization of the paper is as follows. In Section2, we state the main assumption underlying our algorithms and present some examples of the GNEP satisfying it. In Section 3, we derive some useful properties of the function Vαβ(x). In Section 4, we formally state our algorithms and prove that they are both globally convergent to a normalized Nash equilibrium.


## 2. Main Assumption

In order to construct algorithms and guarantee the convergence of them, we give the following assumption.Assumption 2.
For anyβ>α>0 and x∈Rn, if yα(x)≠yβ(x), we have
(10)∑v=1N‍(∇θv(yβ(x)v,x-v)-∇θv(yα(x)v,x-v))T·(yβ(x)-yα(x))≥∑v=1N(∇xvθv(yβ(x)v,x-v)-∇xvθv(yα(x)v,x-v))T·(yβ(x)v-yα(x)v).
We next consider three examples which satisfy Assumption2.Example 3.
Let us consider the case in which all the cost functions are separable, that is,(11)θv(x)=fv(xv)+gv(x-v),
where fv:Rnv→R is convex and gv:Rn-nv→R. A simple calculation shows that, for any y∈Rn, we have
(12)∑v=1N(∇xvθv(yβ(x)v,x-v)-∇xvθv(yα(x)v,x-v))T∑·(yβ(x)v-yα(x)v)∑=∑v=1N(∇fv(yβ(x)v)-∇fv(yα(x)v))T(yβ(x)v-yα(x)v),∑v=1N(∇θv(yβ(x)v,x-v)-∇θv(yα(x)v,x-v))T∑·(yβ(x)v-yα(x)v)∑=∑v=1N(∇fv(yβ(x)v)-∇fv(yα(x)v))T(yβ(x)v-yα(x)v).
Hence Assumption2 holds.Example 4.
Consider the case where the cost functionθv(x) is quadratic, that is,
(13)θv(x)=12(xv)TAvvxv+∑μ=1,μ≠vN‍(xv)TAvμxμ
For v=1,…,N. We have
(14)∑v=1N(∇xvθv(yβ(x)v,x-v)-∇xvθv(yα(x)v,x-v))T∑·(yβ(x)v-yα(x)v)=∑v=1N‍〈yβ(x)v-yα(x)v,Avv(yβ(x)v-yα(x)v)〉,∑v=1N‍(∇θv(yβ(x)v,x-v)-∇θv(yα(x)v,x-v))T∑·(yβ(x)-yα(x))=〈(A11A21⋯A1NA21A22⋯A2N⋮⋮⋱⋮A1NA2N⋯ANN)yβ(x)-yα(x),∑12345(A11A21⋯A1NA21A22⋯A2N⋮⋮⋱⋮A1NA2N⋯ANN)yβ(x)-yα(x)〉.
Therefore, if the matrix(15)(0A12⋯A1NA210⋯A2N⋮⋮⋱⋮AN1AN2⋯0)
is positive semidefinite, Assumption 2 is satisfied.In the following example, we show the relationship between our assumption and the one considered in [8] as follows.For anyβ>α>0, a given x∈Rn with yα(x)≠yβ(x), the inequality (16)∑v=1N‍(∇θv(yβ(x)v,x-v)-∇θv(yα(x)v,x-v))T×(yβ(x)-yα(x))>0
holds.Example 5.
Consider the GNEP withN=2 as
(17)X={x∈Rn:x1≥1,x2≥1,x1+x2≤10}
and the cost function θ1(x)=x1x2 and θ2(x)=-x1x2. The point x*=(1,9)T is the unique normalized Nash equilibrium. For any y∈R2, we have
(18)∑v=1N‍(∇θv(yβ(x)v,x-v)-∇θv(yα(x)v,x-v))T·(yβ(x)-yα(x))=0,∑v=1N(∇xvθv(yβ(x)v,x-v)-∇xvθv(yα(x)v,x-v))T·(yβ(x)v-yα(x)v)=0.
Therefore Assumption2 holds, but (16) does not hold for any β>α>0.


## 3. Properties ofVαβ(x)

Lemma 6.
For anyβ>α>0 and x∈Rn, we have
(19)Vαβ(x)≥β-α2∥x-yβ(x)∥2+α2∥yα(x)-yβ(x)∥2,(20)Vαβ(x)≤β-α2∥x-yα(x)∥2-β2∥yα(x)-yβ(x)∥2.Proof.
Sinceyα(x) satisfies the optimality condition, then
(21)∑v=1N[∇xvθv(yα(x)v,x-v)-α(xv-yα(x)v)]T·(yβ(x)v-yα(x)v)≥0.
In a similar way, it follows thatyβ(x) satisfies
(22)∑v=1N[∇xvθv(yβ(x)v,x-v)-β(xv-yβ(x)v)]T·(yα(x)v-yβ(x)v)≥0.
Sinceθv(x) as a function of xv alone is convex, we have
(23)∑v=1N‍[θv(yβ(x)v,x-v)-θv(yα(x)v,x-v)]-α(x-yα(x))T(yβ(x)-yα(x))≥0,(24)∑v=1N‍[θv(yα(x)v,x-v)-θv(yβ(x)v,x-v)]-β(x-yβ(x))T(yα(x)-yβ(x))≥0
respectively. Thus, using the definition of Vαβ(x) and (23), we have
(25)Vαβ(x)=∑v=1N‍[θv(yα(x)v,x-v)-θv(yβ(x)v,x-v)]+β2∥x-yβ(x)∥2-α2∥x-yα(x)∥2≥α(x-yα(x))T(yβ(x)-yα(x))+β2∥x-yβ(x)∥2-α2∥x-yα(x)∥2=α(x-yα(x))T(yβ(x)-yα(x))+β2∥x-yβ(x)∥2-α2∥x-yβ(x)+yβ(x)-yα(x)∥2=β-α2∥x-yβ(x)∥2+α2∥yα(x)-yβ(x)∥2.
Similarly, using the definition ofVαβ(x) and (24), we have
(26)Vαβ(x)≤β-α2∥x-yα(x)∥2-β2∥yα(x)-yβ(x)∥2.
The proof is complete.Lemma 7.
AssumeX is bounded. For any β>α>0 and x∈Rn, we have
(27)limsupβ′→∞,α′→0Vα′β′(x)β′-α′≤Vαβ(x)β-α.Proof.
We have from (19) that
(28)2Vαβ(x)β-α≥∥x-yβ(x)∥2+αβ-α∥yα(x)-yβ(x)∥2≥∥x-yβ(x)∥2.
By the definition ofVαβ(x), we have
(29)2Vα′β′β′-α′=2∑v=1N‍[θv(yβ′(x)v,x-v)-θv(yα′(x)v,x-v)]β′-α′-α′∥x-yα′(x)∥2+β′∥x-yβ′(x)∥2β′-α′.
Sinceyα(x)∈X,yβ(x)∈X and X is bounded, we get that
(30)limsupβ′→∞,α′→0Vα′β′(x)β′-α′≤12∥x-yβ(x)∥2≤Vαββ-α.
This completes the proof.Equation (8) and Assumption 2 yield
(31)Vαβ(x)T(yβ(x)-yα(x))=∑v=1N‍[∇θv(yβ(x)v,x-v)-∇θv(yα(x)v,x-v)]T∑v=1N‍·(yβ(x)-yα(x))+(∇x1θ1(yα(x)1,x-1)-∇x1θ1(yβ(x)1,x-1)⋮∇xNθN(yα(x)N,x-N)-∇xNθN(yβ(x)N,x-N))T·(yβ(x)-yα(x))-[α(x-yα(x))-β(x-yβ(x))]T·(yβ(x)-yα(x))≥-[α(x-yα(x))-β(x-yβ(x))]T·(yβ(x)-yα(x))=:eαβ(x)≥0,
where nonnegativity of eαβ(x) follows from the inequalities (23) and (24). In particular, either eαβ(x) is above a tolerance ε>0, in which case yα(x)-yβ(x) is a direction of sufficient descent for Vαβ(x) at x or else, as we show in the lemma below, and x is an approximate solution of the GNEP with accuracy depending on ε, α, β. This result will lead to our methods.Lemma 8.
For anyβ>α>0 and x∈Rn, we have
(32)∥x-yβ(x)∥≤2Vαβ(x)β-α,(33)γαβ(x)≤Vα(x)≤γαβ(x)+eαβ(x)+α2∥yα(x)-yβ(x)∥2,
where γαβ(x)=∑v=1N‍[θv(xv,x-v)-θv(yβ(x)v,x-v)]-(α/2)∥x-yβ(x)∥2.Proof.
Inequality (32) follows immediately from (19) in Lemma 6.
The definition ofVα(x) implies that
(34)Vα(x)≥∑v=1N‍[θv(xv,x-v)-θv(yβ(x)v,x-v)]-α2∥x-yβ(x)∥2,
which proves the first inequality in (33).
Sinceeαβ(x) is the sum of the nonnegative quantity (∑v=1N‍[θv(yβ(x)v,x-v)-θv(yα(x)v,x-v)]-α(x-yα(x))T·(yβ(x)-yα(x))) with another nonnegative quantity (see (23) and (24)), we have
(35)eαβ(x)≥∑v=1N‍[θv(yβ(x)v,x-v)-θv(yα(x)v,x-v)]-α(x-yα(x))T(yβ(x)-yα(x)).
Thus,(36)Vα(x)≤γαβ(x)+eαβ(x)+α2∥yα(x)-yβ(x)∥2,
which is the second inequality in (33). This completes the proof.


## 4. Two Methods for Solving the GNEP

In this section, we introduce two methods for solving the GNEP, motivated by the D-gap function scheme for solving monotone variational inequalities [14, 15]. We first formally describe our methods below and then analyze their convergence using Lemma 8.Algorithm 9.
Choose an arbitrary initial pointx0∈Rn, and any β0>α0>0. Choose any sequences of numbers εk>0, ηk≥0, λk∈[0,1), k=1,2,…, such that
(37)limk→∞εk=limk→∞ηk1-λk=0,∑k=1∞‍(1-λk)=∞.
Fork=1,2,…, we iterate the following.
Iteration k. Choose any 0<αk≤(1/2)αk-1. Choose any βk≥2βk-1 and x-k∈Rn satisfying
(38)Vαkβk(x-k)βk-αk≤ηk+λkVαk-1βk-1(xk-1)βk-1-αk-1.
Apply a descent method to the unconstrained minimization of the functionVαkβk, with x-k as the starting point and using yαk-yβk as a safeguard descent direction at x, until the method generates an x∈Rn satisfying eαkβk(x)≤εk. The resulting x is denoted by xk.Theorem 10.
AssumeX is bounded. Let {xk,αk,βk,εk,ηk,λk}k=0,1,2,… be generated by Algorithm 9. Then {xk} is bounded; βk→∞;αk→0; and every cluster point of {xk} is a normalized Nash equilibrium of the GNEP.Proof.
Denoteak=Vαkβk(xk)/(βk-αk). By (38), we have ak≤ηk+λkak-1 for k=1,2,… and it follows from (37) that ak→0 ([16], Lemma 3). For each k∈{1,2,…}, we have from Lemma 8 that (32) and (33) hold with α=αk, β=βk, x=xk. This together with eαk,βk(xk)≤εk and ∥yαk(xk)-yβk(xk)∥≤diam(X) yields
(39)∥xk-yβk(xk)∥≤2ak,γk≤Vαk(xk)≥γk+εk+αkdiam(X)22,
where γk=∑v=1N[θv(xk,v,xk,-v)-θv(yβkv(xk),xk,-v)]-(α/2)∥xk-yβk(xk)∥2 and diam(X)=maxx,y∈X∥x-y∥. Since ak→0, the first inequality in (39) implies {xk} is bounded. Moreover, this also implies rk→0.
Sinceαk→0, the last two inequalities in (39) yield Vαk(xk)→0. Since for each y∈X, we have Vαk(xk)≥Ψ(x,y)-(αk/2)∥xk-y∥2, and this yields 0≥Ψ(x∞,y) for each cluster point x∞ of {xk}. Thus, each cluster point x∞ is a normalized Nash equilibrium of the GNEP. This completes the proof.Algorithm 11.
Choose anyx0∈Rn, any β0>α0, and two sequences of nonnegative numbers ρk,ηk,k=1,2… such that
(40)ηk+ρk>0∀k,∑k=1∞‍ρk<∞,∑k=1∞‍ηk<∞.
Choose any continuous functionϕ:R+→R+ with ϕ(t)=0⇔t=0. For k=1,2,…, we iterate the following.
Iteration k. Choose any 0<αk≤(1/2)αk-1 and then choose βk≥2βk-1 satisfying
(41)Vαkβk(xk-1)βk-αk≤(1+ρk)Vαk-1βk-1(xk-1)βk-1-αk-1+ηk.
Apply a descent method to the unconstrained minimization of the functionVαkβk(xk) with xk-1 as the starting point. We assume the descent method has the property that the amount of descent achieved at x per step is bounded away from zero whenever x is bounded and ∥∇Vαkβk(x)∥ is bounded away from zero. Then, either the method in a finite number of steps generates an x satisfying
(42)∥∇Vαkβk(x)∥≤ϕ(Vαkβk(x)βk-αk),
which we denote by xk, or else Vαkβk(x) must decrease towards zero, in which case any cluster point of x solves the GNEP.Theorem 12.
AssumeX is bounded. Let {xk,αk,βk,ρk,ηk}k=0,1,2,… be generated by Algorithm 11. (a)
Supposexk is obtained for all k. Then, {xk}is bounded; βk→∞; αk→0, and every cluster point of {xk} is a normalized Nash equilibrium of the GNEP.(b)
Supposexk is not obtained for some k. Then, the descent method generates a bounded sequence of x with Vαkβk(x)→0 so every cluster point of x solves the GNEP.Proof.
(a) Since  we use a descent method at iterationk to obtain xk from xk-1, then Vαkβk(xk)≤Vαkβk(xk-1), so (41) yields
(43)Vαkβk(xk)βk-αk≤(1+ρk)Vαk-1βk-1(xk-1)βk-1-αk-1+ηk.
Denoteak=Vαkβk(xk)/(βk-αk). This can then be written as ak≤(1+ρk)ak-1+ηk for k=1,2,…. Using ak≥0 and (41), it follows that the sequence {ak} converges to some a-≥0 ([16], Lemma 2). Since (32) implies
(44)∥xk-yβk(xk)∥≤2ak,∀k
the sequence {xk} is bounded.
We claim thata-=0. Suppose the contrary. Then for all k sufficiently large, it holds that ak≥a-/2. Then,
(45)a-2≤∑v=1N‍[θv(yβkv(xk),xk,-v)-θv(yαkv(xk),xk,-v)]βk-αk-(αk/2)∥xk-yαk(xk)∥2+(βk/2)∥xk-yβk(xk)∥2βk-αk
Since, by the construction of the algorithm,βk→∞ and αk→0, and {xk} is bounded (as are yαk(xk) and yβk(xk)), we get
(46)0<a-2≤liminfk→∞∥xk-yβk(xk)∥2.
Thenlimk→∞∥xk-yβk(xk)∥βk=∞, so
(47)limk→∞∥∇Vαk,βk(xk)∥=∞.
Sincexk satisfies (42), ∥∇Vαk,βk(xk)∥≤ϕ(ak)for all k, this contradicts convergence of {ϕ(ak)} (recall that ϕ is a continuous function). Hence, a-=0. For each k∈{1,2,…}, we have from Lemma 8 that (33) holds with α=αk, β=βk, x=xk and from the fact eαβ(x)≥0 that
(48)eαkβk(xk)≤εk:=∇Vαkβk(xk)T(yβk(xk)-yαk(xk)).
This, together with∥yαk(xk)-yβk(xk)∥≤diam(X), yields
(49)γk≤Vα(x)≤γk+εk+αkdiam(X)22,
where γk=∑v=1N‍[θv(xk,v,xk,-v)-θv(yβk(xk)v,xk,-v)]-(αk/2)∥xk-yβk(xk)∥2 and diam(X)=maxx,y∈X∥x-y∥. Since ak→0, (44) implies {xk}is bounded. Moreover, (44) implies γk→0. Also, we have ∥∇Vαkβk(xk)∥≤ϕ(ak)→0, soεk→0.
From the facts thatαk→0, (49), γk→0 and εk→0, we get Vαk(xk)→0. Since for each y∈X, we have from the definition of Vα(x) that
(50)Vαk(xk)≥Ψ(x,y)-αk2∥xk-y∥2,
which yields 0≥Ψ(x∞,y) for each cluster point x∞ of {xk}. Thus, each cluster point x∞ is a normalized Nash equilibrium of the GNEP.
(b) It is easy to proof thatVαkβk(x)→0. Hence x∞ is a normalized Nash equilibrium of the GNEP.
The proof is completed.



---

*Source: 762165-2013-02-14.xml*