FIXED POINT THEOREMS FOR DISCONTINUOUS MAPPINGS

Ludwig J. CROMME and Immo DIENER

Institut für Numerische und Angewandte Mathematik, D–3400 Göttingen, Lotzestra”se 16–18

Abstract. We prove a generalization of Brouwer’s famous fixed point theorem to discontinuous maps. The main result shows that for discontinuous functions on a compact convex domain X one can always find a point x ∈ X such that ∥x − f(x)∥ is less than a certain measure of discontinuity. Applications to artificial neural nets, economic equilibria, and analysis are given.

Keywords. Fixed points, discontinuous mappings, artificial neural nets, economic equilibria.

1 Introduction

Brouwer’s fixed point theorem states that a continuous function from a convex and compact subset of IR^{n} to itself leaves at least one point fixed. This basic theorem is famous for its simplicity and the many applications it has.

In some cases the continuity requirement of Brouwer’s theorem is not fulfilled. Without some kind of continuity asssumption the theorem is not valid; it needs not be completely false, though: Functions with small jumps or other smale discontinuities still leave some arguments ‘approximately’ fixed. In this paper such cases are investigated and the main result is stated in Theorem 2.1: Functions with ‘small’ discontinuities have ‘approximate’ fixed points. The central idea in the proof of the theorem is the following: A discontinuous real–valued function can be extended to a point–to–set mapping. The set H_{f}(x) assigned to a point x ∈ IR^{n} includes all accumulation points of sequences {f(x_{i}) | x_{i} → x}. The point–to–set mapping x →^{H} convH_{f}(x) is upper semi–continuous and may be interpreted as ‘continuoufication’ or smoothing of the discontinuous original function f. A similar construction, the set–valued hull [f] of f, was introduced by Georg (1982). Kakutanis’s fixed point theorem can therefore be applied to H and this – after some calculation – leads to the results of the main theorem.

In Section 3 a numerical procedure for the calculation of approximate fixed points of possibly discontinuous maps is sketched.

Finally, in Section 4 the theorem on approximate fixed points is applied in a few typical cases. The first application is about the existence of metabolic equilibria in neural nets. Discontinuities arise naturally in this context since the threshold operation is discontinuous. A metabolic equilibrium may be interpreted as fixed point of a certain adjustment function. Thus, our main theorem is applicable.

Next, we discuss the existence of equilibrium price vectors in an exchange economy. It turns out that small discontinuities in the demand functions lead to only small quantities of excess demand.

The last application in Section 4 is a generalization of the well–known multivariate mean value theorem to discontinuous functions.

2 Theory

We first formulate our main theorem which shows that for discontinuous functions f there exists at least an “approximate fixed point”, i.e. a point x^{∗} whose image is no further away from x^{∗} than by a certain measure of discontinuity for f.

2.1 Main theorem. Let X ⊂ IR^{n} be compact and convex and f : X → X any map.

(i): There exists a point x^{∗} ∈ X such that ∥f(x^{∗}) − x^{∗}∥ ≤ δ(f).

(ii): For all ϵ > 0 there exists a point x′ ∈ X such that ∥f(x′) − x′∥ ≤ κδ′(f) + ϵ.

Here, κ is a number less than 1 whose exact value depends on the dimension n and the norm used. See Lemma 2.5. The number δ(f) describes the maximal height of a jump discontinuity. The exact definition for the two measures of discontinuity is given by the following definition.

Definition. Let X ⊂ IR^{n} be compact and f : X → X any map. Then we define the following two measures of discontinuity:

δ(f) := sup_{x∈X} lim sup_{ε→0} sup_{z∈B_{ε}(x)} ∥f(x) − f(z)∥

and

δ′(f) := sup_{x∈X} lim sup_{ε→0} sup_{y,z∈Ḃ_{ε}(x)} ∥f(y) − f(z)∥,

where B_{ϵ}(x) denotes the ϵ–neighborhood of x and Ḃ_{ϵ}(x) the corresponding pointed neighborhood.

If f is continuous then δ(f) = 0 so that Brouwer’s fixed point theorem is a special case of (i). We always have δ′(f) ≤ 2δ(f). The difference between the two measures of discontinuity is illustrated by the following example. Let f̂ be continuous and suppose f and f̂ are identical except for a finite set of points. Then δ′(f) = 0 whereas δ(f) may assume any positive value up to the diameter of X. Thus, if f̂ has exactly one fixed point x̂ and f is made from f̂ by redefining f in x̂ then δ′(f) equals zero and (ii) guarantees the existence of an arbitrarily good “approximate fixed point” for f. Thus, in some cases the application of (i), in some cases the application of (ii) may be more advantageous.

Remark. The property of x^{∗} to be a “best approximate fixed point” is not invariant under homeomorphic transformations of the domain since the measures of discontinuity are not invariant. Furthermore, the point x^{∗} is not “stable”, since under repeated application of f the images might not stay in a small neighborhood of x^{∗}.

The general idea in the proof of our main theorem is the following: The (discontinuous) function f : X → X is first transformed into a continuous point–to–set mapping F. For x ∈ X the set F (x) includes all limits of sequences f(x_{i}), x_{i} → x. This guarantees upper semi–continuity of F. Therefore, Kakutani’s fixed point theorem for set–valued maps is applicable. The obtained (exact) fixed point of F is in a last step transformed into an approximate fixed point for the original function f. We now come to the details. First, we quote Kakutani’s fixed point theorem (Kakutani (1941):

2.2 Theorem. Let X be a nonempty, compact, and convex set in IR^{n}. For every x ∈ X let F (x) be a nonempty convex subset of X. Assume the graph

{(x, y) : x ∈ X, y ∈ F (x)} ⊂ X × X

is closed. Then there is a point x^{∗} ∈ X with x^{∗} ∈ F (x^{∗}).

We also need the following lemma which is proven by a diagonal argument.

2.3 Lemma. Let X ⊂ IR^{n} be compact and f : X → X any map. Let y_{i} → y^{∗} be a convergent sequence in X and suppose for every i there exists a convergent sequence x_{ij} → x_{i}^{∗} in X with

lim_{j→∞} f(x_{ij}) = y_{i}.

Suppose further that the sequence x_{i}^{∗} converges to some point x^{∗} ∈ X. Then there exists a convergent sequence z_{j} → x^{∗} in X such that

y^{∗} = lim_{j→∞} f(z_{j}).

Proof. By hypothesis there exists an integer function a(k) such that for all i ≥ a(k):

∥y^{∗} − y_{i}∥ < 1/k and ∥x^{∗} − x_{i}^{∗}∥ < 1/k.

Furthermore, there exists an integer function B(i, k) such that for all j ≥ B(i, k):

∥y_{i} − f(x_{ij})∥ < 1/k and ∥x_{i}^{∗} − x_{ij}∥ < 1/k

Now define b(k) := B(a(k), k) and z_{k} := x_{a(k)b(k)}. Then we have

∥z_{k} − x^{∗}∥ ≤ ∥z_{k} − x_{a(k)}^{∗}∥ + ∥x^{∗} − x_{a(k)}^{∗}∥ ≤ 2/k

and

∥y^{∗} − f(z_{k})∥ ≤ ∥y^{∗} − y_{a(k)}∥ + ∥y_{a(k)} − f(x_{a(k)b(k)})∥ ≤ 2/k.

Thus, z_{k} converges to x^{∗} and f(z_{k}) converges to y^{∗}. □

The next lemma defines a set–valued “continuoufication” x ↦ convH_{f}(x) of f such that the Kakutani fixed point theorem can be applied. It is the main tool used in the proof of Theorem 2.1:

2.4 Lemma. Let X be a nonempty, compact, and convex subset of IR^{n} and let f : X → X be any map. If X contains more than one point we define a set valued map H_{f}(x) on X:

H_{f}(x) := {y ∈ X : ∃ sequence x_{i} → x, x_{i} ≠ x such that f(x_{i}) → y}.

If X = {x} we set H_{f}(x) = {x}. Then there exists a point x^{∗} ∈ X with x^{∗} ∈ convH_{f}(x^{∗}).

Proof. Define F (x) := convH_{f}(x). We want to apply the Kakutani fixed point theorem to F. The only nontrivial condition that has to be checked is the closedness of the graph of F.

Let (u_{i}, v_{i}) → (u, v) be a convergent sequence in X × X with v_{i} ∈ F (u_{i}). We have to show that v ∈ F (u). This is trivial if u_{i} equals u infinitely often. Without less of generality we may therefore assume u_{i} ≠ u for all i ∈ IN.

By the theorem of Caratheodory, since v_{i} ∈ convH_{f}(u_{i}), we can for every v_{i} choose n + 1 points r_{0}^{i},…, r_{n}^{i} ∈ H_{f}(u_{i}) and numbers λ_{0}^{i},…, λ_{n}^{i} ≥ 0 with ∑ λ_{i} = 1, such that

v_{i} = ∑_{j=0}^{n} λ_{j}^{i}r_{j}^{i}.

Since λ^{i} := (λ_{0}^{i},…, λ_{n}^{i})^{t} is contained in the compact standard simplex S_{n} and the r_{k}^{i} are contained in the compact set X we can consider a subsequence {w_{j}} of {v_{i}} with w_{j} → v such that the corresponding sequences {r_{k}^{j}}_{j=1}^{∞} and {λ_{k}^{j}}_{j=1}^{∞}, k = 0,…, n, converge to points r_{k} and λ_{k} respectively. It follows that v can be written in the form

v = ∑_{k=0}^{n} λ_{k}r_{k}.

Thus, v ∈ conv{r_{0},…, r_{n}}. It remains to be shown, that r_{k} ∈ H_{f}(u) for k = 0, 1,…, n.

For fixed k we set y_{i} := r_{k}^{i} and y^{∗} := r_{k}. Since y_{i} ∈ H_{f}(u_{i}) there exists a sequence x_{ij} → u_{i}, x_{ij} ≠ u_{i}, such that f(x_{ij}) → y_{i}. Furthermore, u_{i} converges to u. Thus, by Lemma 2.3 there exists a sequence z_{j} → u with f(z_{j}) → y^{∗}. Also, z_{j} ≠ u for all j can be seen from the construction of the sequence z_{j} since u_{i} ≠ u for all i ∈ IN. From the definition of H_{f} it now follows that y^{∗} ∈ H_{f}(u). □

Remark. Since the extremal points of convH_{f}(x) are contained in H_{f}(x) we conclude that δ′(f) is equal to the supremum of the diameters of H_{f}(x) for x ∈ X, in other words:

δ′(f) := max_{x∈X} max_{y,z∈H_{f} (x)} ∥y − z∥.

The number δ(f) can also be written in the form

δ(f) := max_{x∈X} max_{z∈H_{f} (x)} ∥f(x) − z∥.

In the proof of 2.4 one could also define F by

F (x) := ⋂_{U∈V} convf(U),

where V denotes the system of pointed neighborhoods of x. Then obviously F (x) = convH_{f}(x). A similar construction was made in Georg (1982) and Allgower and Georg (1983) where a set– valued hull [f] of f is defined by

[f](x) := ⋂_{U∈U} convf(U),

where U is the system of neighborhoods of x. With this definition one can write

δ(f) := sup_{x∈X} sup_{y∈[f](x)} ∥f(x) − y∥.

F and [f] are not identical since f(x) is always an element of [f](x) whereas f(x) is not necessarly an element of F (x).

We need one further lemma which relates the diameter (dependent on the norm choosen) of a convex set K to the maximal distance a point within K can have from an extremal point of K.

2.5 Lemma. Let K be a compact and convex set in IR^{n} of diameter δ and x^{∗} ∈ K. Then there exists an extremal point y^{∗} of K such that

∥x^{∗} − y^{∗}∥ ≤ κδ

where κ is a constant depending only on n and the norm used. One can always take κ ≤ n/(n + 1).

Remark. For the euclidian norm one can set

κ = \frac{1}{\sqrt{2}}\sqrt{\frac{n}{n + 1}} .

This result can be proven with the help of Jung’s inequality (Jung (1901)) which states that this value of κ is an upper bound for the circumradius of a point set S ⊂ IR^{n} with diameter 1.

Proof of Lemma 2.5. From Minkowski’s classical theorem on extremal points we conclude that x^{∗} lies in an n–Simplex S contained in K whose vertices are extremal points of K. Since the diameter of S is at most δ it suffices to prove the theorem for the case of K being a nondegenerate simplex in IR^{n}.

Assume x^{∗} = ∑_{i=0}^{n} λ_{i}x_{i} with ∑_{i=0}^{n} λ_{i} = 1 and define the distance from x^{∗} to the k–th vertex of S by d_{k} := ∥x_{k} − x^{∗}∥. Since the diameter of S is at most δ we obtain

d_{k} ≤ ∥∑_{i=0}^{n} λ_{i}(x_{k} − x_{i})∥ ≤ δ(1 − λ_{k}).

Since λ_{k} ≥ 1/(n + 1) for at least one k, 0 ≤ k ≤ n, this gives us the claimed result. □

The main theorem is now a simple consequence of Lemma 2.4 and Lemma 2.5.

Proof of Theorem 2.1. By Lemma 2.4 there exists a point x^{∗} ∈ convH_{f}(x^{∗}). To prove (i) we remark

∥f(x^{∗}) − x^{∗}∥ ≤ max_{z∈H_{f} (x^{∗})} ∥f(x^{∗}) − z∥ ≤ max_{x∈X} max_{z∈H_{f} (x)} ∥f(x) − z∥ = δ(f).

To prove (ii) let ϵ_{1}, ϵ_{2} > 0 be given. First, we observe that some point q in H_{f}(x^{∗}) is at a distance of at most κδ′(f) from x^{∗}. See Lemma 2.5. Furthermore, there is a point x′ ∈ X such that ∥f(x′) − q∥ < ϵ_{1} and ∥x′ − x^{∗}∥ < ϵ_{2}. Thus, ∥x^{∗} − f(x′)∥ < κδ′(f) + ϵ_{1}. Altogether this gives us

∥x′ − f(x′)∥ < ∥x′ − x^{∗}∥ + ∥x^{∗} − f(x′)∥ < κδ′(f) + ϵ_{1} + ϵ_{2}.

Since ϵ_{1}, ϵ_{2} > 0 were arbitrary the theorem is proven. □

2.6 Remark.

a) In (ii) of the main theorem, κδ′(f) can be replaced by the number

δ′′(f) := max_{x∈X} max_{y∈convH_{f} (x)} min_{z∈H_{f} (x)} ∥y − z∥.

The proof is exactly the same, since some point q in H_{f}(x^{∗}) is at a distance of at most δ′′(f) from x^{∗}. However, in practice the value of δ′′(f) is much harder to determine than the other two measures of discontinuity.

b) One could also introduce local measures of discontinuity by defining

δ_{f}(x) := sup_{y∈H_{f} (x)} ∥f(x) − y∥

and

δ′_{f}(x) := diamH_{f}(x).

Then the first inequality in the proof of Theorem 2.1 would also prove the existence of a point x^{∗} ∈ X with

∥f(x^{∗}) − x^{∗}∥ ≤ δ_{f}(x^{∗})

and a similar “localized” result would we obtained for the second part of Theorem 2.1. However, these bounds are of no help in practice since for unknown x^{∗} the local measure of discontinuity are also unknown and for known x^{∗} the distance ∥x^{∗} − f(x^{∗})∥ need not be estimated because it is known!

3 Construction of approximate fixed points

In the proof of Theorem 2.1 an approximate fixed point of f is constructed from an exact fixed point of a set–valued function F. Algorithms to compute fixed points of set–valued maps are well-known (Todd (1976), Allgower and Georg (1980)). The problem is that in general the set–valued function F is not explicitly known.

Georg (1982) and Allgower and Georg (1983) avoid this difficulty. They suggest a simplicial homotopy method to compute a fixed point of the set–valued hull [f] of f (which is similar to but not identical to our F). The homotopy is defined with respect to the original function f on a refining triangulation, no explicit use is made for [f]. Convergence to a fixed point of [f] is shown under mild assumptions.

The following approach is particularly easy to implement if a convential fixed point algorithm for continuous real–valued functions is at hand, be it of predictor–corrector type, a simplicial homotopy method, or any either type. For the definition of terms like triangulation, mesh, etc. see Todd (1976), for example.

For a compact and convex set X ⊂ IR^{n} let a triangulation T_{ε} with mesh (T_{ε}) ≤ ε be given for every positive ε; for a given f : X → X not necessarily continuous, f_{ε} denotes the linear approximation of f on T_{ε} : f_{ε}(x) := ∑_{j=0}^{n} λ_{j}f(ξ^{j}), where σ = ⟨ξ^{0},…, ξ^{n}⟩ is an n–simplex of the triangulation with x ∈ \overline{σ}, λ_{j} ∈ [0, 1], x = ∑_{j=0}^{n} λ_{j}ξ^{j}, ∑_{j=0}^{n} λ_{j} = 1. f_{ε} is continuous on X and therefore posesses a fixed point. For i ∈ IN we can therefore construct a point x^{i} ∈ X such that ∥f_{1/i}(x^{i}) − x^{i}∥ ≤ 1/i utilizing a conventional fixed point algorithm. With x^{i} = ∑_{j=0}^{n} λ_{ij}ξ^{i,j}, x^{i} ∈ σ^{i} = ⟨ξ^{i,0},…, ξ^{i,n}⟩ ∈ T_{1/i}, ∑_{j=0}^{n} λ_{ij} = 1, λ_{ij} ≥ 0, we get

∥f(x^{i}) − x^{i}∥ ≤ ∥f(x^{i}) − f_{1/i}(x^{i})∥ + ∥f_{1/i}(x^{i}) − x^{i}∥

= ∥∑_{j=0}^{n} λ_{ij}f(x^{i}) − ∑_{j=0}^{n} λ_{ij}f(ξ^{i,j})∥ + \frac{1}{i} (properties of x^{i}, ∑_{j=0}^{n}λ_{i,j} = 1)

≤ ∑_{j=0}^{n} λ_{ij}∥f(x^{i}) − f(ξ^{i,j})∥ + \frac{1}{i}

≤ sup_{∥x−z∥<1/i^{x,z∈X}}∥f(x) − f(z)∥ + \frac{1}{i}

The described procedure thus generates a sequence of points x^{i} such that

lim sup_{i→∞} ∥f(x^{i}) − x^{i}∥ ≤ lim sup_{ε→0} sup_{∥x−y∥<ε} ∥f(x) − f(y)∥.

Since X is compact a few intermediate calculations connect the latter supremum to δ and δ′:

lim sup_{ε→0} sup_{∥x−y∥<ε} ∥f(x) − f(y)∥ = max(δ(f), δ′(f)).

Combining the results we conclude that the above procedure generates a sequence of points x^{i} such that

lim sup_{i→∞} ∥f(x^{i}) − x^{i}∥ ≤ max(δ(f), δ′(f)).

4 Applications

Neural Nets Our first application is a McCulloch–Pitts model of neural nets as used both in biology and artifical intelligence. A jump in the threshold function leads to built–in discontinuities for all derived functions. We discuss here the existence of metabolic equilibria.

The neural net consists of n ∈ IN neurons; each has two possible states at time t, it can fire (σ_{i}^{(t)} = 1) or not fire (σ_{i}^{(t)} = 0). Each neuron receives information from other neurons, weights the incoming information (c_{ij}) and decides to fire or not to fire. For given threshold Θ ∈ IR and connectivity C ∈ IR^{n×n} the initial state σ^{(0)} ∈ {0, 1}^{n} determines all future states:

σ_{i}^{(t+1)} = \{ \begin{matrix}1, & if C σ^{(t)} ≥ Θ \\ 0, & if C σ^{(t)} < Θ \end{matrix} i = 1, 2,…, n.

The threshold operation is discontinuous.

One is interested in adjusting the connectivities c_{ij} such that the whole network reaches a ‘metabolic equilibrium’, for example, a pre–specified average membrane potential (MP). Since the incorporation of biological features leads immediately to very complicated procedures we restrict ourselves here to a much simplified version that is better suited to classify the mathematical background; see Cromme and Dammasch (1989) for details.

The network is started and the average MP is then evaluated for (a finite section of) the generated sequence σ^{(t)}. To catch the ‘typical’ behaviour of the system the network is started with a number of ‘typical’ initial states (σ^{(0)} ∈ T).

Let a ‘test vector set’ T ⊂ {0, 1}^{n} be given with 0 ∉ T. For fixed n_{1}, n_{2} ∈ IN, n_{1} ≤ n_{2} the function ev evaluates the average membrane potential:

\begin{matrix}ev_{j}(C) := & \frac{1}{|T |} ∑_{σ^{0}∈T} ∑_{t=n_{1}}^{n_{2}}(C σ^{(t)})_{j}/(n_{2} + 1 − n_{1}) ∈ IR \\ ev(C) := & (ev_{1}(C),…, ev_{n}(C))^{t}. \end{matrix}

If a given average MP is not yet reached, ev(C) ≠ p ∈ IR_{+}^{n}, C must be adjusted. Here, we discuss a n–dimensional adjustment function adj allowing only rank one corrections of the connectivity matrix; for D ∈ IR^{n×n} we define the matrix D_{α_{1},...,α_{n}} ∈ IR^{n×n} by

(D_{α_{1},···,α_{n}})_{i,j} := (D)_{i,j} + α_{i}) 1 ≤ i, j ≤ n

adj (D) := \{ \begin{matrix}(p_{i_{0}} − ev_{i_{0}}(D))e^{i_{0}} ∈ IR^{n} & , if |p_{i_{0}} − ev_{i_{0}}(D)| ≤ 1 \\ sgn(p_{i_{0}} − ev_{i_{0}})(D)e^{i_{0}} ∈ IR^{n} & , if |p_{i_{0}} − ev_{i_{0}}(D)| > 1 \end{matrix}

where

i_{0} := min {i ∈ IN : |p_{i} − ev_{i}(D)| = max_{1≤j≤n} |p_{j} − ev_{j}(D)|}

and e^{i} denotes the i–th unit vector in IR^{n}. A network with conncetivity C_{α_{1},...,α_{n}} has the pre– specified average MP, ev(C_{α_{1},...,α_{n}}) = p ∈ IR_{+}^{n}, if and only if adj yields an adjustment zero at C_{α_{1},...,α_{n}}. Adjusting a given connectivity matrix C such that the modified matrix C_{α_{1},...,α_{n}} has the specified MP, is thus equivalent to finding a fixed point of the discontinuous function f : IR^{n} → IR^{n}:

( α_{1} ; ⋮ ; α_{n} ) →^{f} ( α_{1} ; ⋮ ; α_{n} ) + adj(C_{α_{1},...,α_{n}}).

The following lemma asserts that approximate fixed points exist despite the discontinuity of f.

4.1 Lemma. With the notation as above, Θ ∈ IR_{+} a positive threshold, τ ≠ 0 ∀τ ∈ T, δ_{ρ}^{∞}(f) the measure of discontinuity of f on B_{ρ} := {x ∈ IR^{n} | ∥x∥_{∞} ≤ ρ},

δ_{ρ}^{∞}(f) := sup_{x∈B_{ρ}} lim sup_{ε→0} sup_{y∈B_{ε}(x)}∥f(x) − f(y)∥_{∞},

there exists a ρ_{0} > 0 and x^{∗} ∈ B_{ρ_{0}} with

∥f(x^{∗}) − x^{∗}∥_{∞} ≤ δ_{ρ_{0}}^{∞}(f).

Proof. Let us first demonstrate that for ρ ≥ ρ_{0},

ρ_{0} := 1 + Θ + max_{1≤i,j≤n} |c_{ij}| + max_{1≤i≤n} |p_{i}|

the ball B_{ρ} is mapped into itself: f(B_{ρ}) ⊂ B_{ρ}. To prove this fix α := (α_{1},…, α_{n})^{t} ∈ B_{ρ}; we have to show |(f(α))_{i_{0}}| ≤ ρ. This is clear if |α_{i_{0}}| ≤ ρ − 1 since ∥adj(C_{α_{1},...α_{n}})∥_{∞} ≤ 1 by definition. Consider the case α_{i_{0}} > ρ − 1. A simple calculation gives us σ_{i_{0}}^{(t)} = 1 for all t ≥ 1 and for all σ^{(0)} ∈ T. Since (C_{α_{1},...,α_{n}})_{i_{0},j} ≥ Θ + p_{i_{0}} for j = 1, 2,…, n, the evaluation of the average MP gives us

p_{i_{0}} − ev_{i_{0}}(C_{α_{1},...,α_{n}}) ≤ −Θ < 0 if α_{i_{0}} > ρ − 1.

The positivity of p_{i_{0}} leads to

p_{i_{0}} − ev_{i_{0}}(C_{α_{1},...,α_{n}}) ≥ p_{i_{0}} > 0 if α_{i_{0}} < −ρ + 1.

Altogether the case |α_{i_{0}}| > ρ − 1 leads to

sgn(p_{i_{0}} − ev_{i_{0}}(C_{α_{1},...,α_{n}})) = −sgn α_{i_{0}}

and since |adj(·)| ≤ 1 and ρ > 1 this implies |f(α)_{i_{0}}| ≤ ρ proving the assertion. Thus, f(B_{ρ}) ⊂ B_{ρ} for all ρ ≥ ρ_{0} and the statement of Lemma 4.1 is now a direct consequence of our Theorem 2.1. □

Equilibrium price vectors In studying the economic interaction between economic agents one is interested in identifying the circumstances under which an equilibrium price vector exists. In the neoclassical excess demand approach usually some kind of continuity requirement is made for the demand functions. The following analysis shows that small discontinuities of the demand functions lead to only small quantities of excess demand.

For simplicity we demonstrate the effects of discontinuities in an exchange economy, see Todd [6] for details of the continuous case. There are m ∈ IN consumers, each with an initial endowment of goods, w^{i} ∈ IR_{+}^{n+1} and a demand function d^{i} : S^{n} → IR_{+}^{n+1}, where elements of the standard simplex S^{n} are interpreted as price vectors p, ∑ p_{i} = 1. With d(p) := ∑_{i=1}^{m} d^{i}(p) the aggregate demand, w := ∑_{i=1}^{m} w^{i} the total initial endowment, and g(p) := d(p) − w the excess demand vector we asssume the validity of Walras’ Law: p^{t}g(p) = 0 for all p ∈ S^{n}. In particular, Walras’ Law holds if a consumer spends all his income: p^{t}d^{i}(p) = p^{t}w^{i} for all p ∈ S^{n}. A price vector p^{∗} is an equilibrium price vector if all excess demands are non–positive: g(p^{∗}) ≤ 0.

4.2 Lemma. With the excess demand function g not necessarily continuous, δ(g) the measure of discontinuity of g not too big, p^{t}g(p) = 0 ∀p ∈ S^{n} (Walras’ Law) there exists an approximate equilibrium price vector:

∃ p^{∗} ∈ S^{n} : g(p^{∗}) ≤ λ · δ(g)

λ is independent of δ(g) and can be chosen constant and independent of g if upper bounds for the demand functions are known.

Proof. As in the continuous case we consider an adjustment process for non–equilibrium price vectors, f : S^{n} → S^{n}, f(p) := h^{+}(p)/e^{t}h^{+}(p) where h(p) := p + g(p), (h^{+}(p))_{i} := max(0, h_{i}(p)), e := (1,…, 1)^{t}. f is well–defined since e^{t}h^{+}(p) is strictly positive: e^{t}h^{+}(p) ≥ p^{t}h^{+}(p) ≥ p^{t}h(p) = p^{t}p + p^{t}g(p) = p^{t}p ≥ 1/(n + 1) > 0 (Walras’ Law).

The measures of discontinuity of f and g are related: δ(f) ≤ λ′δ(g), λ′ := (n + 1)[1 + (n + 1)^{2}(∥g∥_{∞,S^{n}} + 1)]. Deriving this inequality one should remember that e^{t}h^{+}(p) ≥ 1/(n + 1) > 0 is bounded away from zero, h_{i}^{+}(p) is nonnegative, δ(e^{t}h^{+}(·)) ≤ (n + 1)δ(g) and ∥h_{i}^{+}(p)∥_{∞} ≤ 1 + ∥g∥_{∞}.

From Theorem 2.1 (i) we conclude the existence of an approximate fixed point: ∃ p^{∗} ∈ S^{n} : ∥f(p^{∗}) − p^{∗}∥_{∞} =: ∥ε∥_{∞} ≤ δ(f), that is, h^{+}(p^{∗}) = μp^{∗} + μ(ε_{1},…, ε_{n})^{t} for μ := e^{t}h^{+}(p^{∗}) > 0. With I = {i ∈ IN | p_{i}^{∗} + ε_{i} > 0} we consider the case j ∉ I first.

a) j ∉ I: By definition of I we have p_{j}^{∗} + ε_{j} ≤ 0. Also, p_{j}^{∗} + ε_{j} = h^{+}(p^{∗})_{j}/μ ≥ 0. Altogether this gives us p_{j}^{∗} + ε_{j} = 0. We conclude further: 0 = (p_{j}^{∗} + ε_{j})μ = h_{j}^{+}(p^{∗}) ≥ h_{j}(p^{∗}) = p_{j}^{∗} + g_{j}(p^{∗}) ≥ g_{j}(p^{∗}) since p_{j}^{∗} ≥ 0. Therefore, there is no excess demand for j ∉ I: g_{j}(p^{∗}) ≤ 0 ∀ j ∉ I.

b) We now consider a component i ∈ I: From 0 < μ(p_{i}^{∗} + ε_{i}) = h_{i}^{+}(p^{∗}) = h_{i}(p^{∗}) = p_{i}^{∗} + g_{i}(p^{∗}) we get g_{i}(p^{∗}) = (μ − 1)p_{i}^{∗} + με_{i} ∀i ∈ I. Walras’ Law then gives us

0 = p^{∗t}g(p^{∗}) = ∑_{i∈I} p_{i}^{∗}g_{i}(p^{∗}) + ∑_{j∉I}p_{j}^{∗}g_{j}(p^{∗})

= ∑_{i∈I}[(μ − 1)p_{i}^{∗}p_{i}^{∗} + μ p_{i}^{∗}ε] + ∑_{j∉I}p_{j}^{∗}g_{j}(p^{∗})

= (μ − 1)p^{∗t}p^{∗} − ∑_{j∉I} p_{j}^{∗}p_{j}^{∗}(μ − 1) + ∑_{i∈I} μp_{i}^{∗}ε_{i} + ∑_{j∉I} p_{j}^{∗}g_{j}(p^{∗})

= (μ − 1)p^{∗t}p^{∗} + ∑_{j∉I} ε_{j}p_{j}^{∗}(μ − 1) + ∑_{i∈I} μp_{i}^{∗}ε_{i} − ∑_{j∉I}ε_{j}g_{j}(p^{∗})

where we exploited the first part of b) and p_{j}^{∗} + ε_{j} = 0, j ∉ I, see a). This gives us after a few intermediate calculations

μ − 1 = \frac{∑_{j∉I} ε_{j}g_{j}(p^{∗}) − ∑_{i∈I} p_{i}^{∗}ε_{i}}{p^{∗t}(p^{∗} + ε)}

leading to the estimate

|μ − 1| ≤ λ′′δ(f)
λ′′ := [(n + 1)∥g∥_{∞,S^{n}} + 1]/2(n + 1)

since p^{∗t}(p^{∗} + ε) ≥ p^{∗t}(p^{∗} − δ(f)) ≥ 1/(n + 1) − λ′δ(g) ≥ 1/2(n + 1). For this latter inequality we need the assumption δ(g) ≤ 1/(2 · (n + 1) · λ′). Combining the results we conclude from g_{i}(p^{∗}) = (μ − 1)p_{i}^{∗} + με_{i} for i ∈ I

\begin{aligned}|g_{i}(p^{∗})| & ≤ |μ − 1|p_{i}^{∗} + μ|ε_{i}| ≤ |μ − 1|p_{i}^{∗} + |μ − 1||ε_{i}| + |ε_{i}| \\ & ≤ (λ′′ + λ′′ · δ(f) + 1)δ(f). \end{aligned}

Combining a) and b) and inserting the inequality δ(f) ≤ λ′δ(g) derived above gives the result stated in the lemma. □

Mean value theorem for discontinuous functions Our final application is a generalization of the well–known multivariate mean value theorem (Aumann [2], Sansone and Conti [5]).

4.3 Lemma. Suppose a function f = (f_{1},… f_{n})^{t} : IR → IR^{n} is defined on the n–dimensional rectangle R := {x ∈ IR^{n} | a_{i} ≤ x_{i} ≤ b_{i}, i = 1,…, n} for given a_{i} < b_{i} (i = 1,…, n) and satisfies the inequalities

\begin{matrix}f_{i}(x_{1},…, x_{i−1}, a_{i}, x_{i+1},…, x_{n}) ≥ 0 \\ f_{i}(x_{1},…, x_{i−1}, b_{i}, x_{i+1},…, x_{n}) ≤ 0 \end{matrix} i = 1, 2,…, n

for all x_{j} ∈ [a_{j}, b_{j}]. The function f may be discontinuous with δ(f) the measure of discontinuity. Then there is at least one approximate zero of f:

∃ x^{∗} ∈ R : ∥f(x^{∗})∥ ≤ δ(f).

Proof. We extend f from R to all of IR^{n} by setting

f(x) := f(x_{a,b}) for x ∈ IR^{n} \ R

(x_{a,b})_{i} := \{ \begin{matrix}x_{i} & , if a_{i} ≤ x_{i} ≤ b_{i} \\ a_{i} & ; if x_{i} < a_{i} \\ b_{i} & , if x_{i} > b_{i} . \end{matrix}

The original and the extended f have the same measure of discontinuity: δ(f|_{R}) = δ(f|_{IR^{n}}). For positive δ we set R_{δ} := {x ∈ IR^{n} | a_{i} − δ ≤ x_{i} ≤ b_{i} + δ, i = 1, 2,… n}. With Id denoting the identity we then have for every positive ε

ε < \frac{δ}{sup_{1≤i≤n^{x∈R}}|f_{i}(x)|} implies (Id + εf)(R_{δ}) ⊂ R_{δ}  (∗)

To prove (∗) we first note that every function with finite measure of discontinuity is bounded on bounded regions. With x ∈ R_{δ}, x_{i} ≤ b_{i} we get

(Id + εf)_{i}(x) ≤ x_{i} + ε · sup_{x∈R} |f_{i}(x)| ≤ b_{i} + δ.

With x ∈ R_{δ}, x_{i} > b_{i} we conclude

\begin{aligned}(Id + εf)_{i}(x) & ≤ x_{i} + εf_{i}(x_{1},… x_{i−1}, b_{i}, x_{i+1},… x_{n}) \\ & ≤ b_{i} + δ + ε · 0 = b_{i} + δ. \end{aligned}

This gives us (Id + εf)_{i}(x) ≤ b_{i} + δ; i = 1, 2, .... . . , n. The analogue (Id + εf)_{i}(x) ≥ a_{i} − δ, i = 1, 2, .... . . , n, is proven similarly. Altogether this proves (∗).

Again, the measure of discontinuity is easily determined: δ(Id+εf) = εδ(f). From our Theorem 2.1 we know that an approximate fixed point exists:

∃ x_{ε} ∈ R_{δ} : ∥x_{ε} − (Id + εf)(x_{ε})∥ ≤ εδ(f).

Thus ∥f(x_{ε})∥ ≤ δ(f) and with x^{∗} := (x_{ε})_{a,b} ∈ R we have the claimed result:

∥f(x^{∗})∥ = ∥f(x_{ε})∥ ≤ δ(f).
□

5 References

E.L. Allgower and K. Georg, “Simplicial and continuation methods for approximating fixed points and solutions to systems of equations”. SIAM Review 22, (1980) 28–85

E.L. Allgower and K. Georg, “Predictor–corrector and simplicial methods for approximating fixed points and zero points of nonlinear mappings”, in: A. Bachem, M. Gr”otschel, B. Korte ed., Mathematical programming: The state of the art (Springer–Verlag, Berlin, Heidelberg, New York, 1983), pp. 15–56.

G. Aumann, Reelle Funktionen (Springer–Verlag, Berlin, Heidelberg, New York, 1969).

L.J. Cromme and I.E. Dammasch, “Stability and convergence of compensation type algorithms”, Journal of Mathematical Biology 27 (1989) 327–340

K. Georg, Zur numerischen Realisierung von Kontinuit”atsmethoden mit Pr”adiktor–Korrektor– oder simplizialen Verfahren (Habilitationsschrift, Universit”at Bonn, 1982).

H.E.W. Jung, “”Uber die kleinste Kugel, die eine r”aumliche Figur einschlie”st”, J. Reine Angew. Math 123 (1901) 241–257

S. Kakutani, “A generalization of Brouwer’s fixed point theorem”, Duke Matematical Journal 8 (1941) 457-458

G. Sansone and R. Conti, Nonlinear Differential Equations (Pergamon Press, Oxford, 1964).

M. Todd, The Computation of Fixed Points and Applications (Springer–Verlag, Berlin, Heidelberg, New York, 1976).