# Neural Network to Solve Concave Games

Authors: Zixin Liu; Nengfa Wang
Journal: International Journal of Computer Games Technology
 (2014)

---

## Abstract

The issue on neural network method to solve concave games is concerned. Combined with variational inequality, Ky Fan inequality, and projection equation, concave
games are transformed into a neural network model. On the basis of the Lyapunov stable theory, some stability results are also given. Finally, two classic games’ simulation results are given to
illustrate the theoretical results.


---

## Body

## 1. Introduction

Recently, game theory has attracted considerable attention due to its extensive applications in economics, political science, and psychology, as well as logic and biology [1–5]. It has been widely recognized as an important tool in many fields.For game theory, the existence and stability of Nash equilibrium point are the most concerned problems. In past decades, these problems have been widely researched. Up to now, many excellent papers and monographs can be found, such as [6–11]. However, most previously established theory results are difficult to be adopted in practical applications, since the existence results only tell us that, for a given game, the Nash equilibrium point exists, but they do not tell us what it is or how we can calculate it.As is well known, the solving problem of Nash equilibrium point is as important as the existence and stability problems. In order to compute the Nash equilibrium point for a given game, all kinds of optimal algorithms and experiments have been derived in [12–15]. Among these methods, computer technique is one of the most popular ones. For a given game, by utilizing a computer programme to simulate the players, Nash equilibrium point can be approximately solved through computer logic calculation. However, when the quantity of players is large, the computation complexity and converge analysis must be considered.Conversely, projection neural network for solving optimization problems has its distinctly superior. This point is elaborated in [16–18]. The first is that it has parallel computing ability. The second is that the solution naturally exists. The last is that it can be implemented by circuits easily. One natural question is, for a given game, whether we can compute the Nash equilibrium point by neural network. This idea motivates this study.Combined with concave game theory, projection equation theory, variational inequality, Ky Fan inequality, and neural network method, we first established the relationship between neural network and concave games and pointed out that the equilibrium point of the constructed neural network is the Nash equilibrium point of our concerned game. Then, by using the Lyapunov stable theory, we analyzed the stability of the established neural network. Finally, two classic games are presented to illustrate the validity of the main results.


## 2.N-Person Noncooperative Games

Consider a typicaln-person noncooperative game as follows: let N={1,2,…,n} be the set of players. For each i∈N, Xi, a metric space, denotes the strategy set and fi:X=Πi=1nXi→ℝ is the payoff function of ith player, respectively.For eachi∈N, denote i^=N∖{i}. For n-person noncooperative games, one of the most important problem is to research whether there exists x*=(x1*,x2*,…,xn*)∈X such that, ∀i∈N, fi(xi*,xi^*)=max⁡ui∈Xifi(ui,xi^*), where x* is called the Nash equilibrium point. And another problem is, if x* exists, what it is. To further discussion, the following basic assumptions, definitions, and lemmas are needed.Assumptions. We have(1)
∀i∈N, strategy set Xi∈ℝmi is nonempty, closed, and convex.(2)
∀i∈N, payoff function fi:X=Πi=1nXi→ℝ is continuously differentiable, and, ∀xi^∈Xi^,  ui→fi(ui,xi^) is concave on Xi.Definition 1.
LetC be a convex subset of linear space 𝔼, ∀x1,x2∈C, ∀λ∈(0,1); if function f:C→ℝ satisfies
(1)f(λx1+(1-λ)x2)≥min⁡{f(x1),f(x2)},
then f is said to be quasiconcave.Definition 2.
LetX be a Hausdorff topological space, f:X→ℝ is a functional, x∈X, and if, ∀ɛ>0, there exists open neighborhood U(x) of x such that ∀x′∈U(x),
(2)f(x)<f(x′)+ɛ,
then functional f is said to be lower semicontinuous.Remark 3.
Obviously, functionf  being concave means that it is quasiconcave; functional f  being continuous means that it is lower semicontinuous.Lemma 4 (Ky Fan inequality).
LetX be a nonempty convex compact subset of Hausdorff linear topological space 𝔼; f:X×X→ℝ satisfies the following.(1)
∀x∈X,y→f(x,y) is lower semicontinuous on X.(2)
∀y∈X,x→f(x,y) is quasiconcave on X.(3)
∀x∈X,f(x,x)≤0.
Then, there existsy*∈X such that, ∀x∈X, f(x,y*)≤0.Lemma 5.
LetX∈ℝn be a nonempty, closed, and convex subset of ℝn, and function f:X→ℝ is continuously differentiable and concave; then, ∀x,y∈X,
(3)f(y)≤f(x)+〈∇f(x),y-x〉,
where ∇f(x)=(∂f/∂x1,∂f/∂x2,∂f/∂xn).From Lemma5, the following results are obvious.Lemma 6.
LetX∈ℝn be a nonempty, closed, and convex subset of ℝn, and function f:X→ℝ is continuously differentiable and concave, x*∈X; then, f(x*)=max⁡x∈Xf(x) if and only if  ∀x∈X the following variational inequality holds:
(4)〈∇f(x*),x-x*〉≤0.Remark 7.
N-person noncooperative game is called a concave one if the payoff function fi:X→ℝ is continuous, and, ∀xi^∈Xi^,ui→fi(ui,xi^) is concave on Xi. For concave game, there exists a special equivalence relation among the Brouwer fixed-point theory and variational inequality problem [19]; this relationship provides the theoretical basis to solve the Nash equilibrium point for concave game by neural networks.


## 3. The Equivalence between Concave Games and Variational Inequalities

In this section, we will point out that any concave game can be transformed into a variational inequality problem equivalently, and we will utilize Ky Fan inequality to prove the existence of the Nash equilibrium point.Theorem 8.
∀
i
∈
N, strategy set Xi∈ℝmi is nonempty, closed, and convex, payoff function fi:X=Πi=1nXi→ℝ is continuously differentiable, and, ∀xi^∈Xi^,ui→fi(ui,xi^) is concave on Xi. Then, x*=(x1*,x2*,…,xn*)∈X is the Nash equilibrium point of concave game if and only if x* is a solution of the following variational inequality, namely:
(5)∀x∈X,〈∇f(x*),x-x*〉≤0.Proof.
∀
i
∈
N,  ∀xi∈Xi, set x¯=(xi,xi^*), and then x¯∈X, since 〈∇f(x*),x-x*〉≤0; from Lemma 6, we have fi(xi*,xi^*)=max⁡x∈Xfi(x,xi^*). Conversely, if x*=(x1*,x2*,…,xn*)∈X is the Nash equilibrium of concave game, then, ∀i∈N, fi(xi*,xi^*)=max⁡x∈Xfi(x,xi^*); from Lemma 6, we have, ∀x∈X,〈∇f(x*),x-x*〉≤0. This completes the proof.Remark 9.
This proof is similar to the convex situation in [20]. In fact, from [20], one can obtain this result directly. Here, for the readability, we still give out the proof details.Remark 10.
From Theorem8, one can see that the Nash equilibrium point problem of a concave game is equivalent to a variational inequality problem. In order to solve the Nash equilibrium point of a concave game, we only need to solve the related variational inequality.Theorem 11.
∀
i
∈
N, strategy set Xi∈ℝmi is nonempty, closed, and convex, payoff function fi:X=Πi=1nXi→ℝ is continuously differentiable, and, ∀xi^∈Xi^,ui→fi(ui,xi^) is concave on Xi. Then, there exists x*=(x1*,x2*,…,xn*)∈X, such that,
(6)∀x∈X,〈∇f(x*),x-x*〉≤0.
Namely, the Nash equilibrium point of the concerned concave game exists.Proof.
∀
x
,
y
∈
X, define
(7)φ(x,y)=〈-∇f(x),x-y〉.
Sincefi:X=Πi=1nXi→ℝ is continuously differentiable, then it is easy to check that,(1)
∀y∈X,  x→φ(x,y)=〈-∇f(x),x-y〉 is continuous on X;(2)
∀x∈X,  y→φ(x,y)=〈-∇f(x),x-y〉 is concave on X;(3)
∀x∈X,  φ(x,x)=〈-∇f(x),0〉=0.
From Lemma4, there exist x*=(x1*,x2*,…,xn*)∈X such that, ∀x∈X, we have φ(x*,x)=〈-∇f(x*),x*-x〉≤0; namely, ∀x∈X, 〈∇f(x*),x-x*〉≤0, and this completes the proof.Remark 12.
From Theorem11, one can see that if Xi and fi satisfy assumptions (1) and (2), the solution of the variational inequality in Theorem 11 exists, which means that the Nash equilibrium point of our concerned concave game exists. Combined with Theorems 8 and 11, we can construct neural network model to solve concave game problems.


## 4. Neural Network Model for Concave Games

### 4.1. Neural Network Model Construction

To proceed, we first introduce an important lemma as follows.Lemma 13 (see [21]).
Letf:ℝn→ℝn be continuous function, and Ω is subset of ℝn; then x* satisfies 〈f(x*),x-x*〉≥0 for all x∈ℝn if and only if x* is the fixed point of equation x=PΩ(x-αf(x)), where α is arbitrary positive constant and PΩ(x-αf(x)) is projection operator defined by
(8)PΩ(u)=argmin⁡v∈Ω∥u-v∥.On the basis of Theorems8 and 11 and Lemma 13, we can construct the following neural network to solve the Nash equilibrium point of our concerned concave game:
(9)dx(t)dt=-x(t)+PX(x(t)+α∇f(x(t))),
where x(t)∈ℝn is the state vector, X=Πi=1nXi, ∇f(x(t))=(∇x1(t)f1(x(t)),∇x2(t)f2(x(t)),…,∇xn(t)fn(x(t))), and fi:X→ℝ is the payoff function of ith player.Remark 14.
From Lemma13, one can see that x* is an equilibrium point of system (9) if and only if it is a Nash equilibrium point of our concerned concave games; notice Theorem 11; one can obtain that the equilibrium point of system (9) exists. Thus, if the equilibrium point of system (9) is asymptotically stable, we can solve the Nash equilibrium point through neural network (9), which can be implemented by electric circuit. This means that Nash equilibrium point can be solved by electric circuit.Remark 15.
If functionf is convex and α<0, system (9) becomes a typical projection neural network model, which is widely researched in [22–25]. Similar to [24], we will give the stability analysis as follows.


### 4.2. Stability Analysis

Setx* as the equilibrium point (also the Nash equilibrium point) of system (9), and let y(t)=x(t)-x*; then system (9) can be transformed into
(10)dy(t)dt=-y(t)+PX(y(t)+x*+α∇f(y(t)+x*))-PX(x*+α∇f(x*)).Lemma 16 (see [21]).
LetΩ be a closed convex set of ℝn; then projection operator satisfies
(11)(υ-PΩ(υ))T(PΩ(υ)-x)≥0,υ∈ℝn,x∈Ω,∥PΩ(u)-PΩ(υ)∥≤∥u-υ∥,u,υ∈ℝn,
where ∥·∥ denotes L2(ℝn) norm.Theorem 17.
Under assumptions(1) and(2), the state vector of system (9) globally asymptotically converges to the Nash equilibrium point.Proof.
SetX* as the equilibrium point set of system (9); obviously, X*⊂X. If state vector x(t)=x*∈X*, then the conclusion holds naturally. Without loss of generality, we assume that x(t)∉X*. In this case, construct the Lyapunov function as follows:
(12)V(y(t))=α(f(x*)-f(y(t)+x*)).
Since,∀i∈N, fi(xi*,xi^*)=max⁡x∈Xfi(x,xi^*), we have V(y(t))≥0,  V(0)=0. The time derivative of V(y(t)) along the trajectory of system (10) is given as
(13)V˙(y(t))=〈-α∇f(y(t)+x*),dy(t)dt〉.
Notice thatx*=PX(x*+α∇f(x*)); it follows that
(14)V˙(y(t))=〈-α∇f(y(t)+x*),dy(t)dt〉=〈-α∇f(y(t)+x*),-y(t)-x*fff+PX(y(t)+x*+α∇f(y(t)+x*))〉.
Sincex(t)=y(t)+x*∈X, denote PX(y(t)+x*+α∇f(y(t)+x*))=PX(u(t)), where u=y(t)+x* + α∇f(y(t)+x*), (14) can be rewritten as
(15)V˙(y(t))=〈-α∇f(y(t)+x*),dy(t)dt〉=〈-α∇f(y(t)+x*),PX(u(t))-x(t)〉=〈-u(t)+x(t),PX(u(t))-x(t)〉=-〈u(t)-PX(u(t)),PX(u(t))-x(t)〉-〈PX(u(t))-x(t),PX(u(t))-x(t)〉.
Notice thatx(t)∉X*; we have -〈PX(u(t))-x(t),PX(u(t))-x(t)〉<0, and additionally, from Lemma 16, we have -〈u(t)-PX(u(t)),PX(u(t))-x(t)〉<0; thus, V˙(y(t))<0. On the basis of the Lyapunov stable theory, one can obtain that the state vector of system (9) globally asymptotically converges to the Nash equilibrium point. This completes the proof.Remark 18.
For convex optimization problems, projection neural network has similar property. Compared with previous work, our Lyapunov function sufficiently uses the property of Nash equilibrium point; thus, it is more simple and the proof is more concise. The reason is that, in our proof, the value ofυ in Lemma 13 is set more appropriately.Remark 19.
Similar to the proof of [23], we can obtain the following propositions.Proposition 20.
For any initial valuex0∈X, the solution x(t,x0) of system (9) is unique, bounded, and x(t,x0)∈X.Proposition 21.
If the domain of payoff functionf is ℝn and continuous, under assumptions(1) and(2), for any initial value x0∉X⊂ℝn, there exists T>0 such that for all t>T, the solution x(t,x0) of system (9) satisfies x(t,x0)∈X.Remark 22.
Proposition20 means that, for any initial value in the strategy set X, the solution through this initial value is unique and bounded, and the strategy set X is an invariant set. Proposition 21 means that the strategy set X is attractive.Remark 23.
On the basis of Propositions20 and 21, we can further show that the equilibrium point of system (9) is not only globally asymptotically stable but also approximately exponentially stable.Theorem 24.
If the domain of payoff functionf is ℝn and continuous, under assumptions(1) and(2), when α>0 is sufficiently small, then the state vector of system (9) approximately exponentially converges to the Nash equilibrium point, and the approximate convergence exponent is 1.Proof.
From system (9), one can obtain
(16)d(x(t)-x*)dt=(x*-x(t))+PX(x(t)+α∇f(x(t)))-PX(x*+α∇f(x*)).
Set the initial value of system (9) as x0, and by differential theory and Lemma 13, we have
(17)∥x(t)-x*∥≤e-(t-t0)∥x0-x*∥+∫t0t‍e-(t-s)∥PX(x(s)+α∇f(x(s)))aaaaaaaaaaaaa-PX(x*+α∇f(x*))(x(s)+α∇f(x(s)))∥ds≤e-(t-t0)∥x0-x*∥+∫t0t‍e-(t-s)∥PX(x(s)+α∇f(x(s)))aaaaaaaaaaaaa-PX(x*+α∇f(x(s)))∥ds+∫t0t‍e-(t-s)∥PX(x*+α∇f(x(s)))aaaaaaaaaaaaa-PX(x*+α∇f(x*))(x*+α∇f(x(s)))∥ds≤e-(t-t0)∥x0-x*∥+∫t0t‍e-(t-s)∥x(s)-x*∥ds+α∫t0t‍e-(t-s)∥∇f(x(s))-∇f(x*)∥ds.
Ifx0∈X, from Proposition 20, we have x(t)∈X. Notice assumptions (1) and (2); one can obtain that ∥∇f(x(s))-∇f(x*)∥ is bounded, which can be assumed as M. In this case, we have
(18)∥x(t)-x*∥≤e-(t-t0)∥x0-x*∥+αM+∫t0t‍e-(t-s)∥x(s)-x*∥ds.
By Gronwall-Bellman inequality, whenα is sufficiently small, one can obtain that
(19)∥x(t)-x*∥≤e-(t-t0)∥x0-x*∥e+αeM≈e∥x0-x*∥e-(t-t0),
which means that, when x0∈X and α is sufficiently small, the state vector of system (9) approximately exponentially converges to the Nash equilibrium point, and the approximate convergence exponent is 1.
Ifx0∉X, from Proposition 21, there exists T>0 such that, ∀t>T, x(t)∈X. In this case, we have
(20)∥x(t)-x*∥≤e-(t-t0)∥x0-x*∥+∫t0t‍e-(t-s)∥x(s)-x*∥ds+∫t0T‍αe-(t-s)∥∇f(x(s))-∇f(x*)∥ds+∫Tt‍αe-(t-s)∥∇f(x(s))-∇f(x*)∥ds.
Sincef is continuous on ℝn, under assumptions (1) and (2), by Proposition 21, there exist positive constants M1,M2 such that ∫t0T‍αe-(t-s)∥∇f(x(s))-∇f(x*)∥ds≤αM1, ∫Tt‍αe-(t-s)∥∇f(x(s))−∇f(x^*)∥ds≤αM2. Thus, we have
(21)∥x(t)-x*∥≤e-(t-t0)∥x0-x*∥+α(M1+M2)+∫t0t‍e-(t-s)∥x(s)-x*∥ds.
By Gronwall-Bellman inequality, whenα is sufficiently small, one can obtain that
(22)∥x(t)-x*∥≤e-(t-t0)∥x0-x*∥e+αe(M1+M2)≈e∥x0-x*∥e-(t-t0),
which means that, when x0∉X and α is sufficiently small, the state vector of system (9) still approximately exponentially converges to the Nash equilibrium point, and the approximate convergence exponent is 1. This completes the proof.Remark 25.
For system (9), when it is used to convex optimization problem, Theorem 24  does not require that ∇2f exists, and ∇2f>0 and ∥∇2f∥  local bounded. Thus, the conditions of Theorem 24 are weaker than those derived in literature [24].


## 4.1. Neural Network Model Construction

To proceed, we first introduce an important lemma as follows.Lemma 13 (see [21]).
Letf:ℝn→ℝn be continuous function, and Ω is subset of ℝn; then x* satisfies 〈f(x*),x-x*〉≥0 for all x∈ℝn if and only if x* is the fixed point of equation x=PΩ(x-αf(x)), where α is arbitrary positive constant and PΩ(x-αf(x)) is projection operator defined by
(8)PΩ(u)=argmin⁡v∈Ω∥u-v∥.On the basis of Theorems8 and 11 and Lemma 13, we can construct the following neural network to solve the Nash equilibrium point of our concerned concave game:
(9)dx(t)dt=-x(t)+PX(x(t)+α∇f(x(t))),
where x(t)∈ℝn is the state vector, X=Πi=1nXi, ∇f(x(t))=(∇x1(t)f1(x(t)),∇x2(t)f2(x(t)),…,∇xn(t)fn(x(t))), and fi:X→ℝ is the payoff function of ith player.Remark 14.
From Lemma13, one can see that x* is an equilibrium point of system (9) if and only if it is a Nash equilibrium point of our concerned concave games; notice Theorem 11; one can obtain that the equilibrium point of system (9) exists. Thus, if the equilibrium point of system (9) is asymptotically stable, we can solve the Nash equilibrium point through neural network (9), which can be implemented by electric circuit. This means that Nash equilibrium point can be solved by electric circuit.Remark 15.
If functionf is convex and α<0, system (9) becomes a typical projection neural network model, which is widely researched in [22–25]. Similar to [24], we will give the stability analysis as follows.


## 4.2. Stability Analysis

Setx* as the equilibrium point (also the Nash equilibrium point) of system (9), and let y(t)=x(t)-x*; then system (9) can be transformed into
(10)dy(t)dt=-y(t)+PX(y(t)+x*+α∇f(y(t)+x*))-PX(x*+α∇f(x*)).Lemma 16 (see [21]).
LetΩ be a closed convex set of ℝn; then projection operator satisfies
(11)(υ-PΩ(υ))T(PΩ(υ)-x)≥0,υ∈ℝn,x∈Ω,∥PΩ(u)-PΩ(υ)∥≤∥u-υ∥,u,υ∈ℝn,
where ∥·∥ denotes L2(ℝn) norm.Theorem 17.
Under assumptions(1) and(2), the state vector of system (9) globally asymptotically converges to the Nash equilibrium point.Proof.
SetX* as the equilibrium point set of system (9); obviously, X*⊂X. If state vector x(t)=x*∈X*, then the conclusion holds naturally. Without loss of generality, we assume that x(t)∉X*. In this case, construct the Lyapunov function as follows:
(12)V(y(t))=α(f(x*)-f(y(t)+x*)).
Since,∀i∈N, fi(xi*,xi^*)=max⁡x∈Xfi(x,xi^*), we have V(y(t))≥0,  V(0)=0. The time derivative of V(y(t)) along the trajectory of system (10) is given as
(13)V˙(y(t))=〈-α∇f(y(t)+x*),dy(t)dt〉.
Notice thatx*=PX(x*+α∇f(x*)); it follows that
(14)V˙(y(t))=〈-α∇f(y(t)+x*),dy(t)dt〉=〈-α∇f(y(t)+x*),-y(t)-x*fff+PX(y(t)+x*+α∇f(y(t)+x*))〉.
Sincex(t)=y(t)+x*∈X, denote PX(y(t)+x*+α∇f(y(t)+x*))=PX(u(t)), where u=y(t)+x* + α∇f(y(t)+x*), (14) can be rewritten as
(15)V˙(y(t))=〈-α∇f(y(t)+x*),dy(t)dt〉=〈-α∇f(y(t)+x*),PX(u(t))-x(t)〉=〈-u(t)+x(t),PX(u(t))-x(t)〉=-〈u(t)-PX(u(t)),PX(u(t))-x(t)〉-〈PX(u(t))-x(t),PX(u(t))-x(t)〉.
Notice thatx(t)∉X*; we have -〈PX(u(t))-x(t),PX(u(t))-x(t)〉<0, and additionally, from Lemma 16, we have -〈u(t)-PX(u(t)),PX(u(t))-x(t)〉<0; thus, V˙(y(t))<0. On the basis of the Lyapunov stable theory, one can obtain that the state vector of system (9) globally asymptotically converges to the Nash equilibrium point. This completes the proof.Remark 18.
For convex optimization problems, projection neural network has similar property. Compared with previous work, our Lyapunov function sufficiently uses the property of Nash equilibrium point; thus, it is more simple and the proof is more concise. The reason is that, in our proof, the value ofυ in Lemma 13 is set more appropriately.Remark 19.
Similar to the proof of [23], we can obtain the following propositions.Proposition 20.
For any initial valuex0∈X, the solution x(t,x0) of system (9) is unique, bounded, and x(t,x0)∈X.Proposition 21.
If the domain of payoff functionf is ℝn and continuous, under assumptions(1) and(2), for any initial value x0∉X⊂ℝn, there exists T>0 such that for all t>T, the solution x(t,x0) of system (9) satisfies x(t,x0)∈X.Remark 22.
Proposition20 means that, for any initial value in the strategy set X, the solution through this initial value is unique and bounded, and the strategy set X is an invariant set. Proposition 21 means that the strategy set X is attractive.Remark 23.
On the basis of Propositions20 and 21, we can further show that the equilibrium point of system (9) is not only globally asymptotically stable but also approximately exponentially stable.Theorem 24.
If the domain of payoff functionf is ℝn and continuous, under assumptions(1) and(2), when α>0 is sufficiently small, then the state vector of system (9) approximately exponentially converges to the Nash equilibrium point, and the approximate convergence exponent is 1.Proof.
From system (9), one can obtain
(16)d(x(t)-x*)dt=(x*-x(t))+PX(x(t)+α∇f(x(t)))-PX(x*+α∇f(x*)).
Set the initial value of system (9) as x0, and by differential theory and Lemma 13, we have
(17)∥x(t)-x*∥≤e-(t-t0)∥x0-x*∥+∫t0t‍e-(t-s)∥PX(x(s)+α∇f(x(s)))aaaaaaaaaaaaa-PX(x*+α∇f(x*))(x(s)+α∇f(x(s)))∥ds≤e-(t-t0)∥x0-x*∥+∫t0t‍e-(t-s)∥PX(x(s)+α∇f(x(s)))aaaaaaaaaaaaa-PX(x*+α∇f(x(s)))∥ds+∫t0t‍e-(t-s)∥PX(x*+α∇f(x(s)))aaaaaaaaaaaaa-PX(x*+α∇f(x*))(x*+α∇f(x(s)))∥ds≤e-(t-t0)∥x0-x*∥+∫t0t‍e-(t-s)∥x(s)-x*∥ds+α∫t0t‍e-(t-s)∥∇f(x(s))-∇f(x*)∥ds.
Ifx0∈X, from Proposition 20, we have x(t)∈X. Notice assumptions (1) and (2); one can obtain that ∥∇f(x(s))-∇f(x*)∥ is bounded, which can be assumed as M. In this case, we have
(18)∥x(t)-x*∥≤e-(t-t0)∥x0-x*∥+αM+∫t0t‍e-(t-s)∥x(s)-x*∥ds.
By Gronwall-Bellman inequality, whenα is sufficiently small, one can obtain that
(19)∥x(t)-x*∥≤e-(t-t0)∥x0-x*∥e+αeM≈e∥x0-x*∥e-(t-t0),
which means that, when x0∈X and α is sufficiently small, the state vector of system (9) approximately exponentially converges to the Nash equilibrium point, and the approximate convergence exponent is 1.
Ifx0∉X, from Proposition 21, there exists T>0 such that, ∀t>T, x(t)∈X. In this case, we have
(20)∥x(t)-x*∥≤e-(t-t0)∥x0-x*∥+∫t0t‍e-(t-s)∥x(s)-x*∥ds+∫t0T‍αe-(t-s)∥∇f(x(s))-∇f(x*)∥ds+∫Tt‍αe-(t-s)∥∇f(x(s))-∇f(x*)∥ds.
Sincef is continuous on ℝn, under assumptions (1) and (2), by Proposition 21, there exist positive constants M1,M2 such that ∫t0T‍αe-(t-s)∥∇f(x(s))-∇f(x*)∥ds≤αM1, ∫Tt‍αe-(t-s)∥∇f(x(s))−∇f(x^*)∥ds≤αM2. Thus, we have
(21)∥x(t)-x*∥≤e-(t-t0)∥x0-x*∥+α(M1+M2)+∫t0t‍e-(t-s)∥x(s)-x*∥ds.
By Gronwall-Bellman inequality, whenα is sufficiently small, one can obtain that
(22)∥x(t)-x*∥≤e-(t-t0)∥x0-x*∥e+αe(M1+M2)≈e∥x0-x*∥e-(t-t0),
which means that, when x0∉X and α is sufficiently small, the state vector of system (9) still approximately exponentially converges to the Nash equilibrium point, and the approximate convergence exponent is 1. This completes the proof.Remark 25.
For system (9), when it is used to convex optimization problem, Theorem 24  does not require that ∇2f exists, and ∇2f>0 and ∥∇2f∥  local bounded. Thus, the conditions of Theorem 24 are weaker than those derived in literature [24].


## 5. Numerical Examples

In order to show the effectiveness of the technique proposed in this paper, we revisit two classic games as follows.Example 26 (Cournot competition).
Consider an industry comprised of two firms, and they choose output levelsqi,  i=1,2, and have cost function Ci(qi),  i=1,2. The firms’ products are assumed to be perfect substitutes (the homogeneous-goods case). Let Q=q1+q2 denote the aggregate industry output level; market demand for the perfect-substitutes case is a function of aggregate output and its inverse is denoted as P(Q). Thus, the firms’ profit functions can be written as
(23)π1(q1,q2)=q1P(Q)-C1(q1),π2(q1,q2)=q2P(Q)-C2(q2).
A Cournot equilibrium(q1*,q2*) means that
(24)q1*∈argmax⁡π1(q1,q2*)=q1P(q1+q2*)-C1(q1),q2*∈argmax⁡π2(q1*,q2)=q2P(q1*+q2)-C2(q2).For this game, the existence, uniqueness, and stability problems about the Cournot equilibrium have been deeply researched by many authors. Here, we are only concerned about how to calculate it when the special profit functions and parameters are given. In order to verify the technique established in this paper, we assume thatP(Q)=a-(q1+q2), C1(q1)=q1c,  C2(q2)=q2c, where a>c>0 are given positive constants and P(Q)>0. In this case, as is well known, the Nash equilibrium point is q1*=q2*=(1/3)(a-c) [26]. Obviously, the strategy set X=Πi=12Xi,  Xi={qi:0≤qi≤a},   i=1,2, is nonempty, closed, and convex, and profit functions πi(q1,q2),  i=1,2, satisfy assumption (2). By Section 4, we can construct the following neural network to solve the Nash equilibrium:
(25)dq(t)dt=-q(t)+PX(q(t)+α∇π(q(t))),
where q(t)=[q1(t),q2(t)]T is the state vector; PX(q(t)+α∇π(q(t)))=[PX1,PX2]T, where
(26)PX1=0.5|(1-2α)q1(t)-αq2(t)+α(a-c)|+a2-0.5|(1-2α)q1(t)-αq2(t)+α(a-c)-a|,PX2=0.5|(1-2α)αq2(t)-αq1(t)+α(a-c)|+a2-0.5|(1-2α)αq2(t)-αq1(t)+α(a-c)-a|.Ifa=100,  c=4, from q1*=q2*=(1/3)(a-c), we know that q1*=q2*=32. In what follows, we will show that for initial value q0∈X or q0∉X, neural network (25) approximately exponentially converges to the Nash equilibrium point. Set α=0.005,  q0=[1,5]T∈X; by simulation tool box, the simulation result is in Figure 1. From Figure 1, one can see that the state vector of neural network approximately exponentially converges to the Nash equilibrium point. Set q0=[-5,-3]T∉X; by simulation tool box, the simulation result is in Figure 2. From Figure 2, one can see that the state vector of neural network also approximately exponentially converges to the Nash equilibrium point.Figure 1
The state vector of system (25) with q0=[1,5]T∈X.Figure 2
The state vector of system (25) with q0=[-5,-3]T∉X.Additionally, ifP(Q),Ci(qi) are given general nonlinear functions such that πi(q1,q2) satisfies assumptions (1) and (2), in this case, to calculate the Nash equilibrium point directly is difficult. However, by using the technique established in this paper, we still can get one Nash equilibrium point through simulation tool box.Example 27 (Hotelling competition).
Consider the typical Hotelling game with two firms and a continuum of consumers. These consumers are distributed on a linear city of unit length according to a uniform density function. Each consumer is entitled to buy at most one unit of the commodity. Setpi,  Di(p1,p2),  i=1,2, which are the firm i's pricing strategy and demand function, respectively. x is the distance between the location of the consumer and store and t is the transportation cost coefficient. The production cost is assumed to be identical and equal to c per unit for both firms. Thus, the firms’ profit functions can be written as
(27)π1(p1,p2)=(p1-c)D1(p1,p2),π2(p1,p2)=(p2-c)D2(p1,p2).A Hotelling equilibrium(p1*,p2*) means that
(28)p1*∈argmax⁡π1(p1,p2*)=(p1-c)D1(p1,p2*),p2*∈argmax⁡π2(p1*,p2)=(p2-c)D2(p1*,p2).As is well known, if(29)D1(p1,p2)=p2-p1+t2t,D2(p1,p2)=p1-p2+t2t,
the Nash equilibrium point is p1*=p2*=c+t [27]. Obviously, the strategy set X=Πi=12Xi,  Xi={pi:c≤pi≤c+t},  i=1,2, is nonempty, closed, and convex, and profit functions πi(p1,p2),  i=1,2, satisfy assumption (2). By Section 4, we can construct the following neural network to solve the Nash equilibrium point:
(30)dp(t)dt=-p(t)+PX(p(t)+α∇π(p(t))),
where p(t)=[p1(t),p2(t)]T is the state vector; PX(p(t)+α∇π(p(t)))=[PX1,PX2]T, where
(31)PX1=0.5|(1-2α)p1(t)+αp2(t)+α(c+t)-c|-0.5|(1-2α)p1(t)+αp2(t)+(α-1)(c+t)|+2c+t2,PX2=0.5|αp1(t)+(1-2α)p2(t)+α(c+t)-c|-0.5|αp1(t)+(1-2α)p2(t)+(α-1)(c+t)|+2c+t2.Setα=0.005, c=2,  t=5; from p1*=p2*=c+t, we know that p1*=p2*=7. Similar to Example 26, when initial value p0∈X or p0∉X, neural network (30) still approximately exponentially converges to the Nash equilibrium point (p1*,p2*)T. The simulation results can be seen in Figures 3 and 4. From Figures 3 and 4, one can see that the state vector of neural network approximately exponentially converges to the Nash equilibrium point.Figure 3
The state vector of system (30) with q0=[3,5]T∈X.Figure 4
The state vector of system (30) with q0=[5,8]T∉X.Similarly, ifDi(p1,p2),  i=1,2, are given general nonlinear functions such that πi(q1,q2) satisfies assumptions (1) and (2), in this case, to calculate the Nash equilibrium directly is difficult. However, by using the technique established in this paper, we still can get one Nash equilibrium point through simulation tool box.Remark 28.
The numerical simulation examples show that the results established in this paper are both valid from theoretical and practical points of view. These results provide us a new technique to solve the Nash equilibrium point of concave game. This new technique establishes a bridge between the neural network method and game theory and expands the scientific applications area of neural network.Remark 29.
It is worth to be pointed out that, by using the neural network technique derived in this paper to solve the Nash equilibrium point, the initial strategy value can be out of the strategy set; this phenomenon can provide us a new computer algorithm to solve the Nash equilibrium point. This new method is different from the traditional computer logic calculation and simulation method, which requires that every step’s strategy values must be in the strategy set. And the new technique can reduce computation complexity significantly.Remark 30.
The results obtained in this paper show that, theoretically, the Nash equilibrium points of all kinds of concave game can be solved by neural network technique. However, when the payoff function does not satisfy assumption(2), for example, when the payoff function is only lower semicontinuous, upper semicontinuous, or quasi-continuous, how to use neural network technique to solve the Nash equilibrium point still needs to be deeply researched. And this is our future research direction.


## 6. Conclusion

The analysis results obtained in this paper imply that every concave game satisfying assumptions(1) and (2) can be equivalently transformed into a neural network model. There exists equivalence between the equilibrium point of neural network and the Nash equilibrium point of concave games. And the equilibrium point’s convergence is independent whether the initial value is in the strategy set or not. This means that concave games can be implemented by neural network, or even by hardware. Two classic games’ simulation results show that the results established in this paper are valid.



---

*Source: 249721-2014-03-10.xml*