# Constructive Proof of the Existence of Nash Equilibrium in a Finite Strategic Game with Sequentially Locally Nonconstant Payoff Functions

Authors: Yasuhito Tanaka
Journal: ISRN Computational Mathematics
 (2012)

---

## Abstract

We will constructively prove the existence of a Nash
equilibrium in a finite strategic game with sequentially locally nonconstant
payoff functions. The proof is based on the existence of approximate Nash
equilibria which is proved by Sperner's lemma. We follow the Bishop-style
constructive mathematics.


---

## Body

## 1. Introduction

It is often said that Brouwer’s fixed-point theorem cannot be constructively proved.Refernce [1] provided a constructive proof of Brouwer’s fixed-point theorem. But it is not constructive from the viewpoint of constructive mathematics á la Bishop. It is sufficient to say that one-dimensional case of Brouwer’s fixed-point theorem, that is, the intermediate value theorem, is nonconstructive. See [2] or [3]. On the other hand, in [4] Orevkov constructed a computably coded continuous function f from the unit square to itself, which is defined at each computable point of the square, such that f has no computable fixed point. His map consists of a retract of the computable elements of the square to its boundary followed by a rotation of the boundary of the square. As pointed out by Hirst in [5], since there is no retract of the square to its boundary, Orevkov’s map does not have a total extension.The existence of a Nash equilibrium in a finite strategic game also cannot be constructively proved. Sperner’s lemma which is used to prove Brouwer’s theorem, however, can be constructively proved. Some authors have presented a constructive (or an approximate) version of Brouwer’s theorem using Sperner’s lemma. See [3, 6]. Thus, Brouwer’s fixed-point theorem can be constructively proved in its constructive version. Also van Dalen in [3] states a conjecture that a uniformly continuous function f from a simplex to itself, with property that each open set contains a point x such that x≠f(x), which means |x-f(x)|>0, and also at every point x on the boundaries of the simplex x≠f(x), has an exact fixed point. We call such a property of functions local nonconstancy. Further, we define a stronger property sequential local nonconstancy. In another paper [7], we have constructively proved Dalen’s conjecture with sequential local nonconstancy.In this paper, we present a proof of the existence of a Nash equilibrium in a finite strategic game with sequentially locally nonconstant payoff functions. In the next section, we present Sperner’s lemma for ann-dimensional simplex whose constructive proof is omitted indicating references. In Section 3, we present a proof of the existence of a Nash equilibrium in a finite strategic game with sequentially locally nonconstant payoff functions. The proof is based on the existence of approximate Nash equilibria which is proved by Sperner’s lemma. We follow the Bishop-style constructive mathematics according to [2, 8, 9].


## 2. Sperner’s Lemma

LetΔ denote an n-dimensional simplex. n is a finite natural number. For example, a 2-dimensional simplex is a triangle. Let us partition or triangulate the simplex. Figure 1 is an example of partitioning (triangulation) a 2-dimensional simplex. In a 2-dimensional case, we divide each side of Δ in m equal segments and draw the lines parallel to the sides of Δ. m is a finite natural number. Then, the 2-dimensional simplex is partitioned into m2 triangles. We consider partition of Δ inductively for cases of higher dimension. In a 3-dimensional case, each face of Δ is a 2-dimensional simplex, and so it is partitioned into m2 triangles in the above-mentioned way, and draw the planes parallel to the faces of Δ. Then, the 3-dimensional simplex is partitioned into m3 trigonal pyramids. And this is similar to cases of higher dimension.Figure 1
Partition and labeling of 2-dimensional simplex.LetK denote the set of small n-dimensional simplices of Δ constructed by partition. Vertices of these small simplices of K are labeled with the numbers 0,1,2,…,n subject to the following rules. (1)
The vertices ofΔ are, respectively, labeled with 0 to n. We label a point (1,0,…,0) with 0, a point (0,1,0,…,0) with 1, a point (0,0,1…,0) with 2,…, and a point (0,…,0,1) with n. That is, a vertex whose kth coordinate (k=0,1,…,n) is 1 and all other coordinates are 0 is labeled with k.(2)
If a vertex ofK is contained in an n-1-dimensional face of Δ, then this vertex is labeled with some number which is the same as the number of one of the vertices of that face.(3)
If a vertex ofK is contained in an n-2-dimensional face of Δ, then this vertex is labeled with some number which is the same as the number of one of the vertices of that face, and so on for cases of lower dimension.(4)
A vertex contained inside ofΔ is labeled with an arbitrary number among 0,1,…,n.A small simplex ofK which is labeled with the numbers 0,1,…,n is called a fully labeled simplex. Sperner’s lemma is stated as follows.Lemma 1 (Sperner’s lemma).
If one labels the vertices ofK following the rules (1)~(4), then there are an odd number of fully labeled simplices, and so there exists at least one fully labeled simplex.Proof.
About constructive proofs of Sperner’s lemma, see [10] or [11].Sincen and partition of Δ are finite, the number of small simplices constructed by partition is also finite. Thus, we can constructively find a fully labeled n-dimensional simplex of K through finite steps.


## 3. Nash Equilibrium in Strategic Game

Letp=(p0,p1,…,pn) be a point in an n-dimensional simplex Δ, and consider a function φ from Δ to itself. Denote the ith components of p and φ(p) by pi and φi(p) or φi.The definition of local nonconstancy of functions is as follows.Definition 2 (local nonconstancy of functions).
(1) At a pointp on the faces (boundaries) of a simplex φ(p)≠p, this means that φi(p)>pi or φi(p)<pi for at least one i.
(2) In any open set inΔ, there exists a point p such that φ(p)≠p.Next, by reference to the notion ofsequentially at most one maximum in [12], we define the property of sequential local nonconstancy.First, we recapitulate the compactness (total boundedness with completeness) of a set in constructive mathematics.Δ is compact in the sense that for each ɛ>0, there exists a finitely enumerable ɛ-approximation to Δ (a set S is finitely enumerable if there exist a natural number N and a mapping of the set {1,2,…,N} onto S). An ɛ-approximation to Δ is a subset of Δ such that for each p∈Δ, there exists q in that ɛ-approximation with |p-q|<ɛ. Each face (boundary) of Δ is also a simplex, and so it is compact. According to Corollary  2.2.12 of [9], we have the following result.Lemma 3.
For eachɛ>0, there exist totally bounded sets H1,H2,…,Hn, each of diameter less than or equal to ɛ, such that Δ=⋃i=1nHi.The definition of sequential local nonconstancy is as follows.Definition 4 (sequential local nonconstancy of functions).
There existsɛ¯ with the following property. For each ɛ>0 less than ɛ¯, there exist totally bounded sets H1,H2,…,Hm, each of diameter less than or equal to ɛ, such that Δ=⋃i=1mHi, and if for all sequences (pn)n≥1, (qn)n≥1 in each Hi, |φ(pn)-pn|→0 and |φ(qn)-qn|→0, then |pn-qn|→0.We show the following lemma.Lemma 5.
Letφ be a uniformly continuous and sequentially locally nonconstant function from Δ to itself. Assume that infp∈Hiφ(p)=0 for Hi⊂Δ defined above. If the following property holds: for each ɛ>0, there exists δ>0 such that if p,q∈Hi, |φ(p)-p|<δ, and |φ(q)-q|<δ, then |p-q|≤ɛ, then there exists a point r∈Hi such that φ(r)=r.Proof.
Choose a sequence(pn)n≥1 in Hi such that |φ(pn)-pn|→0. Compute N such that |φ(pn)-pn|<δ for all n≥N. Then, for m,n≥N, we have |pm-pn|≤ɛ. Since ɛ>0 is arbitrary, (pn)n≥1 is a Cauchy sequence in Hi and converges to a limit r∈Hi. The continuity of φ yields |φ(r)-r|=0, that is, φ(r)=r.Now, we look at the problem of the existence of a Nash equilibrium in a finite strategic game according to [13]. A Nash equilibrium of a finite strategic game is a state where all players choose their best responses to strategies of other players.Consider ann-players strategic game with m pure strategies for each player. n and m are finite natural numbers not smaller than 2. Let Si be the set of pure strategies of player i, and denote each of his pure strategies by sij. His mixed strategy is defined as a probability distribution over Si and is denoted by pi. Let pij be a probability that player i chooses sij, then we must have ∑j=1mpij=1 for all i. A combination of mixed strategies of all players is called a profile. It is denoted by p. Let πi(p) be the expected payoff of player i at profile p, and let πi(sij,p-i) be his payoff when he chooses a strategy sij at that profile, where p-i denotes a combination of mixed strategies of players other than i at profile p. πi(p) is written as follows:(1)πi(p)=πi(pi,p-i)=∑{j:pij>0}pijπi(sij,p-i).
Assume that the values of payoffs of all players are finite, then since pure strategies are finite, and expected payoffs are linear functions about probability distributions over the sets of pure strategies of all players, πi(p) is uniformly continuous about p.For eachi and j, let(2)vij=pij+max⁡(πi(sij,p-i)-πi(p),0),
and define the following function:(3)ψij(p)=vijvi1+vi2+⋯+vim,
where ∑j=1mψij=1 for all i. Let ψi(p)=(ψi1,ψi2,…,ψim), ψ(p)=(ψ1,ψ2,…,ψn). Since each ψi is an m-dimensional vector such that the values of its components are between 0 and 1, and the sum of its components is 1, it represents a point on an m-1-dimensional simplex. ψ(p) is a combination of vectors ψi’s. It is a vector, such that its components are components of ψi(p) for all players. Thus, it is a vector with n×m components, but since the number of independent components is n(m-1), the range of ψ is the n-times product of m-1-dimensional simplices. It is convex, and homeomorphic to an n(m-1)-dimensional simplex. p=(p1,p2,…,pn) is also a vector with n×m components, and the number of its independent components is n(m-1).Let us consider a homeomorphism between ann(m-1)-dimensional simplex and the space of players’ mixed strategies which is denoted by P. Figure 2 depicts an example of a case of two players with two pure strategies for each player. Vertices D, E, F, and G represent states where two players choose pure strategies, and points on edges DE, EF, FG, and GD represent states where one player chooses a pure strategy. Vertices of the simplex and points on faces (simplices whose dimension is lower than n(m-1)) of the simplex correspond to the points on faces of P. For example, in Figure 2, A, B and C  correspond, respectively, to I, J, and H. On the other hand, each vertex of P, D, E, F, and G corresponds, respectively, to itself on a face of the simplex which contains it.Figure 2
Homeomorphism between simplex and combination of strategies.Next, we assume the following condition.Definition 6 (sequential local nonconstancy of payoff functions).
There existsɛ¯ with the following property. For each ɛ>0 less than ɛ¯, there exist totally bounded sets H1,H2,…,Hm, each of diameter less than or equal to ɛ, such that P=⋃i=1mHi, and if for all sequences (pn)n≥1, (qn)n≥1 in each Hi, max(πi(sij,(pn)-i)-πi(pn),0)→0, max(πi(sij,(qn)-i)-πi(qn),0)→0 for all sij∈Si for all i, then |pn-qn|→0.By the sequential local nonconstancy of payoff functions we obtain the following result.For eachɛ>0 less than ɛ¯, there exist totally bounded sets H1,H2,…,Hm, each of diameter less than or equal to ɛ, such that P=⋃i=1mHi, and if for all sequences (pn)n≥1, (qn)n≥1 in each Hi, |ψ(pn)-pn|→0 and |ψ(qn)-qn|→0, then |pn-qn|→0.Thus,ψ is sequentially locally nonconstant.Let us replacen by n(m-1). We show the following theorem.Theorem 7.
In any finite strategic game with sequentially locally nonconstant payoff functions, there exists a Nash equilibrium.Proof.
Let us prove this theorem through some steps.
(1) First we show that we can partition ann(m-1)-dimensional simplex Δ, so that the conditions for Sperner’s lemma are satisfied. We partition Δ according to the method in the proof of Sperner’s lemma and label the vertices of simplices constructed by partition of Δ. It is important how to label the vertices contained in the faces of Δ. Let K be the set of small simplices constructed by partition of Δ, let p=(p0,p1,…,pn(m-1)) be a vertex of a simplex of K, and denote the ith coordinate of ψ(p) by ψi or ψi(p). We label a vertex p according to the following rule:
(4)ifpk+τ>ψk,welabelpwithk.τ is an arbitrary positive number. If there are multiple k’s which satisfy this condition, we label p conveniently for the conditions for Sperner’s lemma to be satisfied.
For example, letp be a point contained in an n(m-1)-1-dimensional face of Δ such that pi=0 for one i among 0,1,2,…,n(m-1). With τ>0, we have fi>0 or fi<τ (in constructive mathematics for any real number x we can not prove that x≥0 or x<0, that, x>0, x=0, or x<0. But for any distinct real numbers x, y, and z such that x>z, we can prove that x>y or y>z). When ψi>0, from ∑j=0n(m-1)pj=1, ∑j=0n(m-1)ψj=1, and pi=0,
(5)∑j=0,j≠in(m-1)pj>∑j=0,j≠in(m-1)ψj.
Then, for at least one j (denote it by k), we have pk>ψk, and we label p with k, where k is one of the numbers which satisfy pk>ψk. Since ψi>pi=0, i does not satisfy this condition. Assume that ψi<τ. pi=0 implies ∑j=0,j≠in(m-1)pj=1. Since ∑j=0,j≠in(m-1)ψj≤1, we obtain
(6)∑j=0,j≠in(m-1)pj≥∑j=0,j≠in(m-1)ψj.
Then, for a positive number τ, we have
(7)∑j=0,j≠in(m-1)(pj+τ)>∑j=0,j≠in(m-1)ψj.
There is at least one j(≠i) which satisfies pj+τ>ψj. Denote it by k, and we label p with k. k is one of the numbers other than i such that pk+τ>ψk is satisfied. i itself satisfies this condition (pi+τ>ψi). But, since there is a number other than i which satisfies this condition, we can select a number other than i. We have proved that we can label the vertices contained in an n(m-1)-1-dimensional face of Δ such that pi=0 for one i among 0,1,2,…,n(m-1) with the numbers other than i. By similar procedures, we can show that we can label the vertices contained in an n(m-1)-2-dimensional face of Δ such that pi=0 for two i’s among 0,1,2,…,n(m-1) with the numbers other than those i’s, and so on.
Consider the case wherepi=pi+1=0. We see that when ψi>0 or ψi+1>0,
(8)∑j=0,j≠i,i+1n(m-1)pj>∑j=0,j≠i,i+1n(m-1)ψj,
and so for at least one j(denote it by k), we have pk>ψk, and we label p with k. On the other hand, when ψi<τ and ψi+1<τ, we have
(9)∑j=0,j≠i,i+1n(m-1)pj≥∑j=0,j≠i,i+1n(m-1)ψj.
Then, for a positive number τ, we have
(10)∑j=0,j≠i,i+1n(m-1)(pj+τ)>∑j=0,j≠i,i+1n(m-1)ψj.
Thus, there is at least one j(≠i,i+1) which satisfies pj+τ>ψj. Denote it by k, and we label p with k.
Next, consider the case wherepi=0 for all i other than n(m-1). If for some i  ψi>0, then we have pn(m-1)>ψn(m-1) and label p with n(m-1). On the other hand, if ψj<τ for all j≠n(m-1), then we obtain pn(m-1)≥ψn(m-1). It implies pn(m-1)+τ>ψn(m-1). Thus, we can label p with n(m-1).
Therefore, the conditions for Sperner’s lemma are satisfied, and there exists an odd number of fully labeled simplices inK.
(2) Suppose that we partitionΔ sufficiently fine so that the distance between any pair of the vertices of simplices of K is sufficiently small. Let δn(m-1) be a fully labeled n(m-1)-dimensional simplex of K, and let p0,p1,… and pn(m-1) be the vertices of δn(m-1). We name these vertices so that p0,p1,…,pn(m-1) are labeled, respectively, with 0, 1,…, n(m-1). The values of ψ at these vertices are ψ(p0),ψ(p1),… and ψ(pn(m-1)). The jth coordinates of pi and ψ(pi),i=0,1,…,n(m-1), are, respectively, denoted by pji and ψj(pi). About p0, from the labeling rules, we have p00+τ>ψ0(p0). About p1, also from the labeling rules, we have p11+τ>ψ1(p1). Since n and m are finite, by the uniform continuity of ψ there exists δ>0 such that if |pi-pj|<δ, then |ψ(pi)-ψ(pj)|<ɛ/2n(m-1)[n(m-1)+1] for ɛ>0 and i≠j. |ψ(p0)-ψ(p1)|<ɛ/2n(m-1)[n(m-1)+1] means ψ1(p1)>ψ1(p0)-ɛ/2n(m-1)[n(m-1)+1]. On the other hand, |p0-p1|<δ means that p10>p11-δ. We can make δ satisfy δ<ɛ/2n(m-1)[n(m-1)+1]. Thus, from
(11)p10>p11-δ,p11+τ>ψ1(p1),ψ1(p1)>ψ1(p0)-ɛ2n(m-1)[n(m-1)+1],
we obtain
(12)p10>ψ1(p0)-δ-τ-ɛ2n(m-1)[n(m-1)+1]>ψ1(p0)-ɛn(m-1)[n(m-1)+1]-τ.
By similar arguments, for each i other than 0,
(13)pi0>ψi(p0)-ɛn(m-1)[n(m-1)+1]-τ.
For i=0, we have
(14)p00>ψ0(p0)-τ.
Adding (13) and (14) side by side except for some i (denote it by k) other than 0,
(15)∑j=0,j≠kn(m-1)pj0>∑j=0,j≠kn(m-1)ψj(p0)-[n(m-1)-1]ɛn(m-1)[n(m-1)+1]-n(m-1)τ.
From ∑j=0n(m-1)pj0=1, ∑j=0n(m-1)ψj(p0)=1, we have 1-pk0>1-ψk(p0)-([n(m-1)-1]ɛ/(n(m-1)[n(m-1)+1]))-n(m-1)τ, which is rewritten as
(16)pk0<ψk(p0)+[n(m-1)-1]ɛn(m-1)[n(m-1)+1]+n(m-1)τ.
Since (13) implies pk0>ψk(p0)-ɛ/(n(m-1)[n(m-1)+1])-τ, we have
(17)ψk(p0)-ɛn(m-1)[n(m-1)+1]-τ<pk0<ψk(p0)+[n(m-1)-1]ɛn(m-1)[n(m-1)+1]+n(m-1)τ.
Thus,
(18)|pk0-ψk(p0)|<[n(m-1)-1]ɛn(m-1)[n(m-1)+1]+n(m-1)τ
is derived. On the other hand, adding (13) from 1 to n(m-1) yields
(19)∑j=1n(m-1)pj0>∑j=1n(m-1)ψj(p0)-ɛn(m-1)+1-n(m-1)τ.
From ∑j=0n(m-1)pj0=1, ∑j=0n(m-1)ψj(p0)=1, we have
(20)1-p00>1-ψ0(p0)-ɛn(m-1)+1-n(m-1)τ.
Then, from (14) and (20), we get
(21)|p00-ψ0(p0)|<ɛn(m-1)+1+n(m-1)τ.
From (18) and (21), we obtain the following result:
(22)|pi0-ψi(p0)|<ɛn(m-1)+1+n(m-1)τ∀i.
Thus,
(23)|p0-ψ(p0)|<ɛ+n(m-1)[n(m-1)+1]τ.
Since ɛ and τ are arbitrary, we have infp∈Δ|ψ(p)-p|=0.
(3) Since, by Lemma3,  Δ=∑i=1nHi, where each Hi is a totally bounded set whose diameter is less than or equal to ɛ, we have infp∈Hi|ψ(p)-p|=0 for at least one Hi. Choose a sequence (rn)n≥1 such that |ψ(rn)-rn|→0 in such Hi. In view of Lemma 5, it is enough to prove that the following condition holds.
For eachɛ>0, there exists δ>0 such that if p,q∈Hi, |ψ(p)-p|<δ, and |ψ(q)-q|<δ, then |p-q|≤ɛ.
Assume that the set(24)T={(p,q)∈Hi×Hi:|p-q|≥ɛ}
is nonempty and compact (see Theorem  2.2.13 of [9]). Since the mapping (p,q)→max(|ψ(p)-p|,|ψ(q)-q|) is uniformly continuous, we can construct an increasing binary sequence (λn)n≥1 such that
(25)λn=0⟹inf⁡(p,q)∈Tmax⁡(|ψ(p)-p|,|ψ(q)-q|)<2-n,λn=1⟹inf⁡(p,q)∈Tmax⁡(|ψ(p)-p|,|ψ(q)-q|)>2-n-1.
It suffices to find n such that λn=1. In that case, if |ψ(p)-p|<2-n-1, |ψ(q)-q|<2-n-1, we have (p,q)∉T and |p-q|≤ɛ. Assume that λ1=0. If λn=0, choose (pn,qn)∈T such that max(|ψ(pn)-pn|,|ψ(qn)-qn|)<2-n, and if λn=1, set pn=qn=rn. Then, |ψ(pn)-pn|→0 and |ψ(qn)-qn|→0, so |pn-qn|→0. Computing N such that |pN-qN|<ɛ, we must have λN=1. We have completed the proof of the existence of a point which satisfies ψ(p)=p.
(4) Denote one of the points which satisfyψ(p)=p by p̃=(p̃1,p̃2,…,p̃n) and the components of p̃i by p̃ij. Then, we have
(26)ψij=p̃ij,∀i,j.
By the definition of ψij,
(27)p̃ij+max⁡(πi(sij,p̃-i)-πi(p̃),0)1+∑k=1mmax⁡(πi(sik,p̃-i)-πi(p̃),0)=p̃ij.
Let λ=∑k=1mmax(πi(sik,p̃-i)-πi(p̃),0), then
(28)max⁡(πi(sij,p̃-i)-πi(p̃),0)=λp̃ij,
where p̃-i denotes a combination of mixed strategies of players other than i at profile p̃.
Sinceπi(p̃)=∑{j:p̃ij>0}p̃ijπi(sij,p̃i), it is impossible that max(πi(sij,p̃-i)-πi(p̃),0)=πi(sij,p̃-i)-πi(p̃)>0 for all j satisfying p̃ij>0. Thus, λ=0, and max(πi(sij,p̃-i)-πi(p̃),0)=0 holds for all sij’s whether p̃ij>0 or not, and it holds for all players. Then, strategies of all players in p̃ are the best responses to each other, and a state where all players choose these strategies is a Nash equilibrium.Consider two examples. See a game in Table1. It is an example of the so-called Prisoners’ Dilemma. Pure strategies of players 1 and 2 are X and Y. The left-side number in each cell represents the payoff of player 1, and the right-side number represents the payoff of player 2. Let pX and 1-pX denote the probabilities that player 1 chooses, respectively, X and Y, and qX and 1-qX denote the probabilities for player 2. Denote the expected payoffs of players 1 and 2 by π1(pX,qX) and π2(pX,qX), then (29)π1(pX,qX)=2pXqX+3(1-pX)qX+(1-pX)(1-qX)=1-pX+2qX,π2(pX,qX)=2pXqX+3pX(1-qX)+(1-pX)(1-qX)=1-qX+2pX.
Denote the payoff of player 1 when he chooses X by π1(X,qX) and that when he chooses Y by π1(Y,qX). Do similarly for Player B, then(30)π1(Y,qX)=1+2qX>π1(pX,qX)foranyqX,pX>0,π2(pX,Y)=1+2pX>π2(pX,qX)foranypX,qX>0.Table 1
Example of game 1.
Player 2XYPlayer 1X2, 20, 3Y3, 01, 1Consider two sequences ofpX, (pX(m))m≥1 and (pX′(m))m≥1, such that pX(m)>0 and pX′(m)>0. If max(max(π1(X,qX),π1(Y,qX))-π1(pX(m),qX),0)=max(π1(Y,qX)-π1(pX(m),qX),0)→0 and max(max(π1(X,qX),π1(Y,qX))-π1(pX′(m),qX),0)=max(π1(Y,qX)-π1(pX′(m),qX),0)→0, then pX(m)→0, pX′(m)→0, and |pX(m)-pX′(m)|→0.Consider two sequences ofqX, (qX(m))m≥1 and (qX′(m))m≥1, such that qX(m)>0 and qX′(m)>0. If max(max(π2(pX,X),π2(pX,Y))-π2(pX,qX(m)),0)=max(π2(pX,Y)-π2(pX,qX(m)),0)→0 and max(max(π2(pX,X),π2(pX,Y))-π2(pX,qX′(m)),0)=max(π2(pX,Y)-π2(pX,qX′(m)),0)→0, then qX(m)→0, qX′(m)→0, and |qX(m)-qX′(m)|→0.Therefore, the payoff functions are sequentially locally nonconstant.Let us consider another example. See a game in Table2. It is an example of the so-called Battle of the Sexes Game. Notations are the same as those in the previous example. The expected payoffs of players are as follows: (31)π1(pX,qX)=2pXqX+(1-pX)(1-qX)=1+pX(3qX-1)-qX,π1(X,qX)=2qX,π1(Y,qX)=1-qX,π2(pX,qX)=pXqX+2(1-pX)(1-qX)=2+qX(3pX-2)-2pX,π2(pX,X)=pX,π2(pX,Y)=2-2pX.
Then, (i)
whenqX>1/3, π1(X,qX)>π1(pX,qX) for pX<1,(ii)
whenqX<1/3, π1(Y,qX)>π1(pX,qX) for pX>0,(iii)
whenpX>2/3, π2(pX,X)>π2(pX,qX) for qX<1,(iv)
whenpX<2/3, π2(pX,Y)>π2(pX,qX) for qX>0.Table 2
Example of game 2.
Player 2XYPlayer 1X2, 10, 0Y0, 01, 2Consider sequences(pX(m))m≥1, (pX′(m))m≥1, (qX(m))m≥1, and (qX′(m))m≥1. (1)
WhenpX>2/3, qX>1/3, if max(π1(X,qX)-π1(pX(m),qX),0)→0 and max(π1(X,qX)-π1(pX′(m),qX),0)→0, then pX(m)→1, pX′(m)→1, and |pX(m)-pX′(m)|→0.
Ifmax(π2(pX,X)-π2(pX,qX(m)),0)→0 and max(π2(pX,X)-π2(pX,qX′(m)),0)→0, then qX(m)→1, qX′(m)→1, and |qX(m)-qX′(m)|→0.(2)
WhenpX<2/3, qX<1/3, if max(π1(Y,qX)-π1(pX(m),qX),0)→0 and max(π1(Y,qX)-π1(pX′(m),qX),0)→0, then pX(m)→0, pX′(m)→0, and |pX(m)-pX′(m)|→0.
Ifmax(π2(pX,Y)-π2(pX,qX(m)),0)→0 and max(π2(pX,Y)-π2(pX,qX′(m)),0)→0, then qX(m)→0, qX′(m)→0, and |qX(m)-qX′(m)|→0.(3)
WhenpX<2/3, qX>1/3, there exist no pair of sequences (pX(m))m≥1 and (qX(m))m≥1 such that max(π1(X,qX)-π1(pX(m),qX),0)→0 and max(π2(pX,Y)-π2(pX,qX(m)),0)→0.(4)
WhenpX>2/3, qX<1/3, there exist no pair of sequences (pX(m))m≥1 and (qX(m))m≥1 such that max(π1(Y,qX)-π1(pX(m),qX),0)→0 and max(π2(pX,X)-π2(pX,qX(m)),0)→0.(5)
When(2/3)-ɛ<pX<(2/3)+ɛ, (1/3)-ɛ<qX<(1/3)+ɛ with 0<ɛ<1/3, if max(π1(X,qX)-π1(pX(m),qX),0)→0, max(π1(Y,qX)-π1(pX(m),qX),0)→0, max(π2(pX,X)-π2(pX,qX(m)),0)→0, and max(π2(pX,Y)-π2(pX,qX(m)),0)→0, then (pX(m),qX(m))→(2/3,1/3) for all sequences (pX(m))m≥1 and (qX(m))m≥1.
The payoff functions are sequentially locally nonconstant.


## 4. Concluding Remarks

In this paper, we have presented a constructive procedure to prove the existence of Nash equilibrium in finite strategic games from the viewpoint of constructive mathematics á la Bishop, that is, mathematics based on intuitionistic logic. As a future research program, we are studying the following themes:(1)
an application of the method of this paper to economic theory, in particular, the problem of the existence of an equilibrium in competitive economy with excess demand functions which have the property that is similar to sequential local nonconstancy;(2)
a generalization of the result of this paper to Kakutani’s fixed-point theorem for multivalued functions with property of sequential local nonconstancy and its application to economic theory.For other researches about computability of Nash equilibrium, see [14–18].



---

*Source: 459459-2011-11-24.xml*