The mathematician Shizuo Kakutani has died at the age of 92. One tool he developed, known as the Kakutani fixed-point theorem, was a key step in the original proof of the existence of Nash equilibria, the theorem for which John Forbes Nash received his Nobel Prize. Dr. Kakutani's theorem is also used to prove a famous 1954 theorem by the economists Kenneth J. Arrow and Gérard Debreu, which says that there are prices for goods that balance supply and demand in a complex economy.

In economics the most frequent technique for establishing the existence of solutions to an equilibrium system of equations consists of setting up the problem as the search for a fixed point of a suitably constructed function or correspondence
f : A → A from some set A ⊂ Rⁿ into itself. A vector x ∈ A is a fixed point of f(.)
if x = f(x) or, in the correspondence case, if x ∈ f(x).

The reason for proceeding in this, often roundabout, way is that important mathematical theorems for providing the existence of fixed points are readily available. The most important fixed point theorem is Brouwer's (deals with functions); the extention of this theorem to correspondences is given by Kakutani's fixed point theorem.

Real world examples: (1) Take two equal size sheets of paper, one lying directly above the other. If you crumple the top sheet, and place it on top of the other sheet, then Brouwer's fixed point theorem says that there must be at least one point on the top sheet that is directly above the corresponding point on the bottom sheet. (2) Take a map of the city in which you live. Now lay the map down on the floor. There exists at least one point on the map which tells the location of the corresponding point below it on the floor.

Warm-up: Brouwer’s fixed point theorem in dimension one:

Let f : [0, 1] → [0, 1] be a continuous function. Then, there exists a fixed point, i.e. there is a x* in [0, 1] such that f (x*) = x*.


Proof: There are two essential possibilities:

1. if f(0) = 0 or if f(1) = 1, then we are done.
2. if f(0) ≠ 0 and f(1) ≠ 1, then define F(x) =f(x) - x. In this case:
   F(0) = f(0) - 0 =f(0) > 0
   F(1) = f(1) - 1 < 0
   So F: [0, 1] → R, where F(0)·F(1) < 0. As f(.) is continuous, then F(.) is also continuous. Then by using the Intermediate Value Theorem (IVT), there is a x* in [0, 1] such that F(x*) = 0. By the definition of F(.), then F(x*) = f (x*) - x* = 0, thus f (x*) = x*.

NB: The IVT was freely used by mathematicians of the 18th century (including Euler and Gauss) without any consideration of its validity. In fact, the first analytical proof was not offered until 1817 by Bolzano in a paper that also contains the first appearance of a somewhat modern definition of continuity.

Getting down to business: Kakutani's fixed point theorem:

Suppose that A ⊂ Rⁿ is a nonempty, compact, convex set, and that f : A → A is an upper hemicontinuous correspondence from A into itself with the property that the set f(x) ⊂ A is nonempty and convex for every x ∈ A. Then f(.) has a fixed point; that is, there is an x ∈ A such that x ∈ f(x).

NB: A set in Rⁿ is compact ⇔ it is closed and bounded (Heine-Borel Covering Theorem). A set A in n-dimensional space is called a convex set if the line segment joining any pair of points of A lies entirely in A. Given a set A in n-dimensional space and the closed set Y in k-dimensinal space, the correspondence f : A → Y is upper hemicontinuous (uhc, usc (upper semi continuous)) if it has a closed graph and the images of compact sets are bounded, that is, for every compact set B ⊂ A the set f(B) = {y ∈ Y: y ∈ f(x) for some x ∈ B} is bounded.

Example:


(a) A fixed point exists
(b) The convex-valuedness assumption is indispensable.

Click here for a nice introduction to game theory (see 1.3 Existence of Nash Equilibrium).

via Alex Tabarrok (Kakutani is at rest)

References:
Microeconomic theory, A. Mas-Colell, M. Whinston, J. Green
Understanding Analyisis, Steven Abbott
Lebesgue Integration on Euclidean Space, Frank Jones
A First Course in Optimization Theory, Rangarajan K. Sundaram

NB: I am back to Vienna & blogging. Stay tuned!