Fixed-Point Theorems

Back

Contents

(A) Intermediate Value Theorem
(B) Brouwer's Fixed Point Theorem
(C) Kakutani's Fixed Point Theorem

Selected References

Fixed-point theorems are one of the major tools economists use for proving existence, etc. One of the oldest fixed-point theorems - Brouwer's - was developed in 1910 and already by 1928, John von Neumann was using it to prove the existence of a "minimax" solution to two-agent games (which translates itself mathematically into the existence of a saddlepoint). von Neumann (1937) used a generalization of Brouwer's theorem to prove existence again for a saddlepoint - this time for a balanced growth equilibrium for his expanding economy. This generalization was later simplified by Kakutani (1941). Working on the theory of games, John Nash (1950) was among the first to use Kakutani's Fixed Point Theorem. Gerard Debreu (1952), generalizing upon Nash, came across this. The existence proofs of Arrow and Debreu (1954), McKenzie (1954) and others gave Kakutani's Fixed Point Theorem a central role. Brouwer's Theorem made a reapparence in Lionel McKenzie (1959), Hirofumi Uzawa (1962) and, later, in the computational work of Herbert Scarf (1973).

(A) Intermediate Value Theorem (IVT)

Theorem: (Bolzano, IVT) Let ｦ : [a, b] ｮ R be a continuous function, where [a, b] is a non-empty, compact, convex subset of R and ｦ (a)ｷｦ (b) < 0, then there exists a x* ﾎ [a, b] such that ｦ (x*) = 0.

Proof: (i) Suppose ｦ (a) > 0, then this implies ｦ (b) < 0. Define M⁺ = {x ﾎ [a, b] | ｦ (x) ｳ 0} and M^- = {x ﾎ [a, b] | ｦ (x) ｣ 0}. By continuity of ｦ on a connected set [a, b] ﾌ R, then M⁺ and M^- are closed and M⁺ ﾇ M^- ｹ ﾆ . Suppose not. Suppose M⁺ ﾇ M^- = ﾆ so x ﾎ M⁺ ﾞ x ﾏ M^- and x ﾎ M^- ﾞ x ﾏ M⁺. But M⁺ ﾈ M^- = [a, b], which implies that M^- = (M⁺)^c. But as M⁺ is closed, then M^- is open. A contradiction. Thus, M⁺ ﾇ M^- ｹ ﾆ , i.e. there is an x* ﾎ [a, b] such that x* ﾎ M⁺ ﾇ M^-, i.e. there is an x* such that ｦ (x*) ｣ 0 and ｦ (x*) ｳ 0. Thus, there is an x* ﾎ [a, b] such that ｦ (x*) = 0.ｧ

We can follow up on this with the following demonstration:

Corollary: Let ｦ : [0, 1] ｮ [0, 1] be a continuous function. Then, there exists a fixed point, i.e. $ x* ﾎ [0, 1] such that ｦ (x*) = x*.

Proof: there are two essential possibilities: (i) if ｦ (0) = 0 or if ｦ (1) = 1, then we are done.

(ii) If ｦ (0) ｹ 0 and ｦ (1) ｹ 1, then define F(x) = ｦ (x) - x. In this case:

F(0) = ｦ (0) - 0 = ｦ (0) > 0

F(1) = ｦ (1) - 1 < 0

So F: [0, 1] ｮ R, where F(0)ｷF(1) < 0. As ｦ (.) is continuous, then F(.) is also continuous. Then by using the Intermediate Value Theorem (IVT), $ x* ﾎ [0, 1] such that F(x*) = 0. By the definition of F(.), then F(x*) = ｦ (x*) - x* = 0, thus ｦ (x*) = x*.ｧ

(B) Brouwer’s Fixed Point Theorem

Brouwer's fixed point theorem (Th. 1.10.1 in Debreu, 1959) is a generalization of the corollary to the IVT set out above. Specifically:

Theorem: (Brouwer) Let ｦ : S ｮ S be a continuous function from a non-empty, compact, convex set S ﾌ Rⁿ into itself, then there is a x* ﾎ S such that x* = ｦ (x*) (i.e. x* is a fixed point of function ｦ ).

Proof: Omitted. See Nikaido (1968: p. 63), Scarf (1973: p. 52) or Border (1985: p.28).

Thus, the previous corollary is simply a special case (where S = [0, 1]) of Brouwer's fixed point theorem. The intuition can be gathered from Figure 1 where we have a function ｦ mapping from [0, 1] to [0, 1]. At point d, obviously x｢ maps to x｢｢ = ｦ (x｢ ) and x｢ ｹ x｢ ｢ , thus point d is not a fixed point. ｦ intersects the 45ｰ line at three points - a, b and c - all of which represent different fixed points as, for instance, at point a, x* = ｦ (x*).

Figure 1 - Brouwer's Fixed Point Theorem

(C) Kakutani’s Fixed Point Theorem

The following, Kakutani's fixed-point theorem for correspondences (Th. 1.10.2 in Debreu, 1959), can be derived from Brouwer's Fixed Point Theorem via a continuous selection argument.

Theorem: (Kakutani) Let j : S ｮ S be an upper semi-continuous correspondence from a non-empty, compact, convex set S ﾌ Rⁿ into itself such that for all x ﾎ S, the set j (x) is convex and non-empty, then j (.) has a fixed point, i.e. there is an x* where x* ﾎ j (x*).

Proof: Omitted. See Nikaido (1968: p.67) or Border (1985: p.72).

We can see this in Figure 2 below where S = [0, 1] and the correspondence j is obviously upper semicontinuous and convex-valued. Obviously, we have a fixed-point at point the intersection of the correspondence with the 45 ｰ line at point (a) where x* ﾎ j (x*).

Figure 8 - Kakutani's Fixed Point Theorem

Note the importance of convex-valuedness for this result in Figure 2: if the upper and lower portions of the correspondence j were not connected by a line at j (x*) (e.g. if j (x*) was merely the end of the upper "box" and the end of the lower "box" only and thus not a convex set), then the correspondence would still be upper semicontinuous (albeit not convex-valued) but it would not intersect the 45ｰ line (thus x* ﾏ j (x*)) and thus there would be no fixed point, i.e. no x* such that x* ﾎ j (x*). Thus, convex-valuedness is instrumental.

Selected References

Kim C. Border (1985) Fixed Point Theorems with Applications to Economics and Game Theory. Cambridge, UK: Cambridge University Press.

Gerard Debreu (1959) Theory of Value: An axiomatic analysis of economic equilibrium. New York: Wiley.

J. von Neumann (1937) "A Model of General Economic Equilibrium", in K. Menger, editor, Ergebnisse eines mathematischen Kolloquiums, 1935-36. 1945 Translation, Review of Economic Studies, Vol. 13 (1), p.1-9.

Hukukane Nikaido (1968) Convex Structures and Economic Theory. New York: Academic Press.

Herbert Scarf (1973) The Computation of Economic Equilibria. (with the collaboration of Terje Hansen), New Haven: Yale University Press.

Back

Top

Next