# Equivalence between the Existence of an Approximate Equilibrium in a Competitive Economy and Sperner's Lemma: A Constructive Analysis

Authors: Yasuhito Tanaka
Journal: ISRN Applied Mathematics
 (2011)

---

## Abstract

Brouwer's fixed point theorem cannot be constructively proved, so the existence of an equilibrium in a competitive economy also cannot be constructively proved. On the other hand, Sperner's lemma which
is used to prove Brouwer's theorem is constructively proved. Some authors
have presented a constructive (or an approximate) version of Brouwer's fixed
point theorem using Sperner's lemma. In this paper, I prove the existence of
an approximate equilibrium in a competitive economy directly by Sperner's
lemma. Also I show that the existence of an approximate equilibrium leads to
Sperner's lemma. I follow the Bishop style constructive mathematics according
to Bishop and Bridges (1985), Bridges and Richman (1987), and Bridges and Vîţă (2006).


---

## Body

## 1. Introduction

It is often demonstrated that Brouwer’s fixed point theorem cannot be constructively proved. Thus, the existence of an equilibrium in a competitive economy also cannot be constructively proved. On the other hand, however, Sperner’s lemma which is used to prove Brouwer’s theorem is constructively proved. Some authors have presented a constructive (or an approximate) version of Brouwer’s fixed point theorem using Sperner’s lemma. Thus, Brouwer’s fixed point theorem can be constructively proved in its constructive version. See [1, 2]. Using this theorem, we can prove the existence of an approximate equilibrium in a competitive economy.Then, can we prove the existence of an approximate equilibrium directly by Sperner’s lemma?This paper presents such a proof and also shows that the existence of an approximate equilibrium leads to Sperner’s lemma. An approximate equilibrium in a competitive economy is a state such that excess demand for each good is smaller thanε for each ε>0.In the next section, the proof of Sperner’s lemma will be presented. This proof is a standard constructive proof. In Section3, the existence of an approximate equilibrium in a competitive exchange economy will be proved using Sperner’s lemma. In Section 4, it will be shown that the existence of an approximate equilibrium leads to Sperner’s lemma. I follow the Bishop style constructive mathematics according to Bishop and Bridges [3], Bridges and Richman [4], and Bridges and Vîţă [5].


## 2. Sperner’s Lemma

To prove Sperner’s lemma, we use the following simple result of graph theory, the Handshaking lemma (For another constructive proof of Sperner’s lemma, see [6].). A graph refers to a collection of vertices and a collection of edges that connect pairs of vertices. Each graph may be undirected or directed. Figure 1 is an example of an undirected graph. Degree of a vertex of a graph is defined to be the number of edges incident to the vertex, with loops counted twice. Each vertex has odd degree or even degree. Let v denotes a vertex and V denotes the set of all vertices.Figure 1
Example of graph.Lemma 2.1 (the Handshaking lemma).
Every undirected graph contains an even number of vertices of odd degree, that is, the number of vertices that have an odd number of incident edges must be even.It is a simple lemma. But for completeness of arguments we provide a proof.Proof.
Prove this lemma by double counting. Letd(v) be the degree of vertex v. The number of vertex-edge incidences in the graph may be counted in two different ways: by summing the degrees of the vertices or by counting two incidences for every edge. Therefore,
(2.1)∑v∈Vd(v)=2e,
where e is the number of edges in the graph. The sum of the degrees of the vertices is therefore an even number. It could happen if and only if an even number of the vertices had odd degree.LetΔ denotes 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 2 is an example of partition (triangulation) of 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 also 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, so it is partitioned into m2 triangles in the way above mentioned, and draw the planes parallel to the faces of Δ. Then, the 3-dimensional simplex is partitioned into m3 trigonal pyramids, and similarly for cases of higher dimension.Figure 2
Partition and labeling of 2-dimensional simplex.LetK denotes 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 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,…,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 a vertex 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 a vertex 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. Now, let us prove Sperner’s lemma.Lemma 2.2 (Sperner’s lemma).
If one labels the vertices ofK following above rules (1)~(4), then there are an odd number of fully labeled simplices. Thus, there exists at least one fully labeled simplex.Proof.
See the appendix.


## 3. Approximate Equilibrium in a Competitive Exchange Economy

Consider a competitive exchange economy. There aren+1 goods X0,X1,…,Xn. n is a finite natural number. The prices of the goods are denoted by pi(≥0),i=0,1,…,n. Let p¯=p0+p1+⋯+pn, and define(3.1)p¯i=pip¯,i=0,1,…,n.
Replace p¯0,p¯1,…,p¯n, respectively, by p0,p1,…,pn. Then,(3.2)p0+p1+⋯+pn=1.
Thus, p=(p0,p1,…,pn) represents a point on an n-dimensional simplex. Since consumers’ demand (excess demand) for each good in a competitive exchange economy is determined by relative prices of the goods, such notation yields no loss of generality. We denote the vector of excess demands for the goods when the vector of prices is p by f(p)=(f1,f2,…,fn). Then, the following relation must hold:(3.3)pf(p)=p0f0+p1f1+⋯+pnfn=0(Walraslaw)fi is equal to the sum of excess demands of all consumers for the good Xi. By the budget constraint for each consumer, in a competitive economy the sum of excess demands of all consumers for each good must be 0. Adding the budget constraints for all consumers yields (3.3).We assume that the excess demand functionf(p) is uniformly continuous about the prices of the goods. Uniform continuity of f(p) means that for any p, p′ and ε>0, there exists δ>0 such that (3.4)If|p′-p|<δ,then|f(p′)-f(p)|<εδ depends on neither p nor p′. Uniform continuity of demand functions implies that a slight price change yields only a slight demand change.Consider the following function from the set of price vectorsp=(p0,p1,…,pn) to the set of n+1 tuples of real numbers v=(v0,v1,…,vn):(3.5)vi=pi+max⁡(fi,0)∀i.
With this, we define a function from an n-dimensional simplex Δ to itself φ(p)=(φ0,φ1,…,φn) as follows:(3.6)φi=1v0+v1+⋯+vnvi,∀i.
Since φi≥0,i=0,1,…,n and(3.7)φ0+φ1+⋯+φn=1,(φ0,φ1,…,φn) represents a point on Δ. By the uniform continuity of f, φ is also uniformly continuous.Now, we show the following.Theorem 3.1.
In a competitive exchange economy, if the excess demand functions for the goods are uniformly continuous about their prices, then there exists an approximate equilibrium and one can constructively find the prices at the approximate equilibrium.Proof.
(1)  First, we show that we can partitionΔ, which is the domain and range of φ, so that the conditions for Sperner’s lemma are satisfied. We partition Δ according to the method in the proof of Sperner’s lemma (see the appendix) 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 Δ, p=(p0,p1,…,pn) a vertex of a simplex of K, and denote the ith component of φ(p) by φi. Then, we label a vertex p according to the following rule:
(3.8)Ifpk>φkorpk+τ>φk,welabelpwithk,
where τ is a positive number. If there are multiple k’s which satisfy this condition, we label p conveniently for the conditions of Sperner’s lemma to be satisfied. We do not randomly label the vertices.
For example, letp be a point contained in an n-1-dimensional face of Δ such that pi=0 for one i among 0,1,2,…,n (the ith component of its coordinates is 0). With τ>0, we have φi>0 or φi<τ (In constructive mathematics for any real number x, we cannot prove that x≥0 or x<0, nor that x>0 or 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=0npj=1, ∑j=0nφj=1 and pi=0, we have
(3.9)∑j=0,j≠inpj>∑j=0,j≠inφ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, i does not satisfy this condition. When φi<τ, pi=0 implies ∑j=0,j≠inpj=1. Since ∑j=0,j≠inφj≤1, we obtain
(3.10)∑j=0,j≠inpj≥∑j=0,j≠inφj.
Then, for a positive number τ, we have
(3.11)∑j=0,j≠in(pj+τ)>∑j=0,j≠inφj.
Thus, 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-1-dimensional face of Δ such that pi=0 for one i among 0,1,2,…,n with the numbers other than i. By similar procedures, we can show that we can label the vertices contained in an n-2-dimensional face of Δ such that pi=0 for two i’s among 0,1,2,…,n with the numbers other than those i’s, and so on.
Consider the case wherepi=pi+1=0. By similar procedures, we see that when φi>0 or φi+1>0,
(3.12)∑j=0,j≠i,i+1npj>∑j=0,j≠i,i+1nφj.
Then, 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
(3.13)∑j=0,j≠i,i+1npj≥∑j=0,j≠i,i+1nφj.
Then, for a positive number τ, we have
(3.14)∑j=0,j≠i,i+1n(pj+τ)>∑j=0,j≠i,i+1nφj.
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. If for some iφi>0, then we have pn>φn, and label p with n. On the other hand, if φj<τ for all j≠n, then we obtain pn≥φn. It implies pn+τ>φn. Thus, we can label p with n.
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 small simplices is sufficiently small. Let p0,p1,…, and pn be the vertices of a fully labeled simplex. We name these vertices so that p0,p1,…,pn are labeled, respectively, with 0,1,…,n. The values of φ at theses vertices are φ(p0),φ(p1),…, and φ(pn). The ith components of p0 and φ(p0) are denoted by pi0 and φ(p0)i, and so on.
The uniform continuity ofφ implies that we can select δ>0 so that when the distance between p0 and p1 (|p0-p1|) is smaller than δ, the distance between φ(p0) and φ(p1) (|φ(p0)-φ(p1)|) is smaller than ɛ. We can make δ satisfying δ<ɛ (For example, for δ<1 and ɛ<1, if when |p0-p1|<δ we have |φ(p0)-φ(p1)|<ε, then we have |φ(p0)-φ(p1)|<ε also when |p0-p1|<δɛ<ɛ.). Suppose τ>0. About p0, from the labeling rules, we have p00+τ>φ(p0)0. About p1, also from the labeling rules we have p11+τ>φ(p1)1 which implies p11>φ(p1)1-τ. By the uniform continuity of φ, |p0-p1|<δ implies |φ(p0)-φ(p1)|<ɛ, which means φ(p1)1>φ(p0)1-ɛ. On the other hand, |p0-p1|<δ means p10>p11-δ. Thus, from
(3.15)p10>p11-δ,p11>φ(p1)1-τ,φ(p1)1>φ(p0)1-ɛ,
we obtain
(3.16)p10>φ(p0)1-δ-ɛ-τ>φ(p0)1-2ɛ-τ.
By similar arguments, for each i other than 0,
(3.17)pi0>φ(p0)i-2ɛ-τ.
For i=0, we have p00+τ>φ(p0)0. Then,
(3.18)p00>φ(p0)0-τ.
Adding (3.17) and (3.18) side by side except for some i (denote it by k) other than 0 yields
(3.19)∑j=0,j≠knpj0>∑j=0,j≠knφ(p0)j-2(n-1)ɛ-nτ.
From ∑j=0npj0=1, ∑j=0nφ(p0)j=1, we have 1-pk0>1-φ(p0)k-2(n-1)ɛ-nτ, which is rewritten as
(3.20)pk0<φ(p0)k+2(n-1)ɛ+nτ.
Since (3.17) implies pk0>φ(p0)k-2ɛ-τ, we have
(3.21)φ(p0)k-2ɛ-τ<pk0<φ(p0)k+2(n-1)ɛ+nτ.
Thus,
(3.22)|pk0-φ(p0)k|<2(n-1)ɛ+nτ
is derived. On the other hand, adding (3.17) from 1 to n yields
(3.23)∑j=1npj0>∑j=1nφ(p0)j-2nɛ-nτ.
From ∑j=0npj0=1, ∑j=0nφ(p0)j=1, we have
(3.24)1-p00>1-φ(p0)0-2nɛ-nτ.
Then, from (3.18) and (3.24), we get
(3.25)|p00-φ(p0)0|<2nɛ+nτ.
Since n is finite and ɛ and τ are positive numbers which may be arbitrarily small, 2nɛ+nτ and 2(n-1)ɛ+nτ may also be arbitrarily small. Replacing 2nɛ+nτ by ɛ, from (3.22) and (3.25) we obtain the following result:
(3.26)|pi0-φ(p0)i|<ɛ∀i.
All points contained in the fully labeled simplex of K satisfy this relation.
(3) Denote a point which satisfies (3.26) by p̃, and denote its ith component by p̃i. We have
(3.27)|p̃i-φi|<ɛ∀i.
Let us consider the relationship between the price and demand for each good in that case. From the definitions of φ and v, and ∑j=0nvj=1+∑j=0nmax(fj,0) (because ∑j=0np̃j=1), (3.27) means
(3.28)|p̃i+max⁡(fi,0)1+∑j=0nmax⁡(fj,0)-p̃i|=|max⁡(fi,0)-p̃i∑j=0nmax⁡(fj,0)1+∑j=0nmax⁡(fj,0)|<ɛ.
Let λ=∑j=0nmax(fj,0). Then, we have |(max(fi,0)-λp̃i)/(1+λ)|<ɛ. It is rewritten as
(3.29)|max⁡(fi,0)-λp̃i|<(1+λ)ɛ.
This means
(3.30)-(1+λ)ɛ+λp̃i<max⁡⁡(fi,0)<(1+λ)ɛ+λp̃i.
From ∑j=0np̃j=1, there is a k which satisfies p̃k>0. If for all such kmax(fk,0)=fk>0 holds, that is, excess demands for all goods with positive prices are positive, we cannot cancel out p̃kfk>0 because the price of any good cannot be negative and the Walras law (3.3) is violated (Even if we relax the Walras law to the following approximate Walras law, we can show essentially the same result: |pf(p)|=|p0f0+p1f1+⋯+pnfn|<ε, where ε is a positive number. If we have max(fk,0)=fk>0 for all k which satisfy pk>0, this inequality cannot be satisfied because the price of any good cannot be negative.). Therefore, λ as well as ɛ must be a positive number which may be arbitrarily small, and since p̃i is finite, (1+λ)ɛ+λp̃i is a real number which may also be arbitrarily small. There exists a number which is only slightly larger than (1+λ)ɛ+λp̃i. Replace (1+λ)ɛ+λp̃i by such a number, and denote it by ɛ. Then, for all i we have
(3.31)max⁡(fi,0)<ɛ.
This means that excess demand for each good is smaller than ɛ. Such a state is an approximate equilibrium. In the approximate equilibrium when pi>0, we must have fi>-ɛ for any ɛ>0 because if fi<0 we have pifi<0, and then the Walras law is violated. On the other hand, there may be excess supply (negative excess demand) for a good whose price is zero.


## 4. From the Existence of an Approximate Equilibrium to Sperner’s Lemma

In this section, we will derive Sperner’s lemma from the existence of an approximate equilibrium in a competitive economy. Let us partition ann-dimensional simplex Δ. Denote the set of small n-dimensional simplices of Δ constructed by partition by K. Vertices of these small simplices of K are labeled with the numbers 0,1,2,…,n similarly to the proof of Sperner’s lemma. Denote vertices of an n-dimensional simplex of K by x0,x1,…,xn, the jth component of xi by xji, and the label of xi by l(xi). Let τ be a positive number which is smaller than xl(xi)i for all xi, and define a function f(xi) as follows:(4.1)f(xi)=(f0(xi),f1(xi),…,fn(xi)),(4.2)fj(xi)={xji-τforj=l(xi),xji+τnforj≠l(xi).fj denotes the jth component of f. From the labeling rules xl(xi)i>0 for all xi, and so τ>0 is well defined. Since ∑j=0nfj(xi)=∑j=0nxji=1, we have(4.3)f(xi)∈Δ.
We extend f to all points in the simplex by convex combinations of its values on the vertices of the simplex. Let y be a point in the n-dimensional simplex of K whose vertices are x0,x1,…,xn. Then, y and f(y) are represented as follows:(4.4)y=∑i=0nλixi,f(y)=∑i=0nλif(xi),λi≥0,∑i=0nλi=1.
Let us show that f is uniformly continuous. Let y and y′ be distinct points in the same small n-dimensional simplex of K. They are represented as(4.5)y=∑i=0nλixi,y′=∑i=0nλi′xi,
and so(4.6)y-y′=∑i=0n(λi-λi′)xi,yj-yj′=∑i=0n(λi-λi′)xjiforeachj.
Then, we have(4.7)f(y)-f(y′)=∑i=0n(λi-λi′)f(xi),
and for each j,(4.8)fj(y)-fj(y′)=∑i=0n(λi-λi′)xji+∑i:j≠l(i)(λi-λi′)τn-∑i:j=l(i)(λi-λi′)τ=yj-yj′+∑i:j≠l(i)(λi-λi′)τn-∑i:j=l(i)(λi-λi′)τ.
Since τ is finite, appropriately selecting λi′ given λi for each i, we can make |fj(y)-fj(y′)| sufficiently small corresponding to the value of |yj-yj′| for each j, and so make |f(y)-f(y′)| sufficiently small corresponding to the value of |y-y′|. Thus, f is uniformly continuous.Now, usingf, we construct an excess demand function as follows:(4.9)zi(p)=fi(p)-piμ(p),i=0,1,…,n.p∈Δ and μ(p) is defined by(4.10)μ(p)=∑i=0npifi(p)∑i=0npi2.
Each zi(p) is uniformly continuous, and satisfies the Walras law as shown below. Multiplying pi (the ith component of p) to (4.9) for each i and adding them from 0 to n yields(4.11)∑i=0npizi=∑i=0npifi(p)-μ(p)∑i=0npi2=∑i=0npifi(p)-∑i=0npifi(p)∑i=0npi2∑i=0npi2=∑i=0npifi(p)-∑i=0npifi(p)=0.
Therefore, zi(p)’s satisfy the conditions for excess demand functions and there exists an approximate equilibrium. Let p*={p0*,p1*,…,pn*} be the price vector at the approximate equilibrium. Then, from max(zi,0)<ɛ (see (3.31)), we have fi(p*)-pi*μ(p*)<ɛ for all i, where ɛ is an positive number. Since it is impossible that at the approximate equilibrium zi<0 for i satisfying pi*>0 because of (4.11), we have zi=fi(p*)-pi*μ(p*)>-ɛ for such i. On the other hand, for i such that pi*=0, we have zi=fi(p*)≥0. Therefore,(4.12)-ɛ<fi(p*)-pi*μ(p*)<ɛ
is obtained. Adding this inequality side by side from 0 to n yields(4.13)-(n+1)ɛ<∑i=0nfi(p*)-μ(p*)∑i=0npi*<(n+1)ɛ.
From ∑i=0nfi(p*)=∑i=0npi*=1, we obtain(4.14)1-(n+1)ɛ<μ(p*)<1+(n+1)ɛ.
Further, from (4.12) and (4.14), we get(4.15)pi*-(n+1)ɛpi*-ɛ<fi(p*)<pi*+(n+1)ɛpi*+ɛ.
Since n and pi* are finite, (n+1)ɛpi*+ɛ is a positive real number which may be arbitrarily small. There exists a number which is only slightly larger than (n+1)ɛpi*+ɛ. Replace (n+1)ɛpi*+ɛ by such a number, and denote it by ɛ. Then, -ɛ<fi(p*)-pi*<ɛ, that is, (4.16)|fi(p*)-pi*|<ɛ
is derived. This relation holds for all i.Letγ>0 and p̃ be a point in V(p*,γ), where V(p*,γ) is a γ-neighborhood of p*. If γ is sufficiently small, uniform continuity of f means(4.17)|fi(p̃)-p̃i|<ɛ,
for any ɛ>0 and for all i. p̃i is the ith component of p̃. Let Δ* be a simplex of K which contains p̃, and p0,p1,…,pn be the vertices of Δ*. Then, p̃ and f(p̃) are represented as (4.18)p̃=∑i=0nλipi,f(p̃)=∑i=0nλif(pi),λi≥0,∑i=0nλi=1.
Equation (4.2) implies that if only one pk among p0,p1,…,pn is labeled with i, we have(4.19)|fi(p̃)-p̃i|=|∑j=0nλjpij+∑j=0,j≠kλjτn-λkτ-p̃i|=|(1n∑j=0,j≠kλj-λk)τ|<ɛ.pij is the ith component of pj.Sinceɛ may be arbitrarily small and τ>0, this means(4.20)1n∑j=0,j≠kλj-λk≈0
Equation (4.17) is satisfied with λk≈1/(n+1) for all k. On the other hand if no pj is labeled with i, we have(4.21)fi(p̃)=∑j=0nλjpij=pi*+(1+1n)τ,
and then (4.17) cannot be satisfied. Thus, for each i one and only one pj must be labeled with i. Therefore, Δ* must be a fully labeled simplex. We have completed the proof of Sperner’s lemma.


## 5. Concluding Remark

In this paper, I have presented a proof of the existence of an approximate equilibrium in a competitive economy directly by Sperner’s lemma from a viewpoint of constructive mathematics. In another paper [7], I apply this method to prove the existence of an approximate Nash equilibrium in a finite strategic game (a strategic game with a finite number of players and a finite number of pure strategies).



---

*Source: 384625-2011-05-05.xml*