Kakutani fixed-point theorem


In mathematical analysis, the Kakutani fixed-point theorem is a fixed-point theorem for set-valued functions. It provides sufficient conditions for a set-valued function defined on a convex, compact subset of a Euclidean space to have a fixed point, i.e. a point which is mapped to a set containing it. The Kakutani fixed point theorem is a generalization of Brouwer fixed point theorem. The Brouwer fixed point theorem is a fundamental result in topology which proves the existence of fixed points for continuous functions defined on compact, convex subsets of Euclidean spaces. Kakutani's theorem extends this to set-valued functions.
The theorem was developed by Shizuo Kakutani in 1941, and was used by John Nash in his description of Nash equilibria. It has subsequently found widespread application in game theory and economics.

Statement

Kakutani's theorem states:

Definitions

;Set-valued function: A set-valued function φ from the set X to the set Y is some rule that associates one or more points in Y with each point in X. Formally it can be seen just as an ordinary function from X to the power set of Y, written as φ: X → 2Y, such that φ is non-empty for every. Some prefer the term correspondence, which is used to refer to a function that for each input may return many outputs. Thus, each element of the domain corresponds to a subset of one or more elements of the range.
;Closed graph: A set-valued function φ: X → 2Y is said to have a closed graph if the set is a closed subset of X × Y in the product topology i.e. for all sequences and such that, and for all, we have.
;Fixed point: Let φ: X → 2X be a set-valued function. Then a ∈ X is a fixed point of φ if a ∈ φ.

Examples

A function with infinitely many fixed points

The function:, shown on the figure at the right, satisfies all Kakutani's conditions, and indeed it has many fixed points: any point on the 45° line which intersects the graph of the function is a fixed point, so in fact there is an infinity of fixed points in this particular case. For example, x = 0.72 is a fixed point since 0.72 ∈ .

A function with a unique fixed point

The function:
satisfies all Kakutani's conditions, and indeed it has a fixed point: x = 0.5 is a fixed point, since x is contained in the interval.

A function that does not satisfy convexity

The requirement that φ be convex for all x is essential for the theorem to hold.
Consider the following function defined on :
The function has no fixed point. Though it satisfies all other requirements of Kakutani's theorem, its value fails to be convex at x = 0.5.

A function that does not satisfy close graph

Consider the following function defined on :
The function has no fixed point. Though it satisfies all other requirements of Kakutani's theorem, its graph is not closed; for example, consider the sequences xn = 0.5 - 1/n, yn = 3/4.

Alternative statement

Some sources, including Kakutani's original paper, use the concept of upper hemicontinuity while stating the theorem:
This statement of Kakutani's theorem is completely equivalent to the statement given at the beginning of this article.
We can show this by using the closed graph theorem for set-valued functions, which says that for a compact Hausdorff range space Y, a set-valued function φ: X→2Y has a closed graph if and only if it is upper hemicontinuous and φ is a closed set for all x. Since all Euclidean spaces are Hausdorff and φ is required to be closed-valued in the alternative statement of the Kakutani theorem, the Closed Graph Theorem implies that the two statements are equivalent.

Applications

Game theory

The Kakutani fixed point theorem can be used to prove the minimax theorem in the theory of zero-sum games. This application was specifically discussed by Kakutani's original paper.
Mathematician John Nash used the Kakutani fixed point theorem to prove a major result in game theory. Stated informally, the theorem implies the existence of a Nash equilibrium in every finite game with mixed strategies for any number of players. This work later earned him a Nobel Prize in Economics. In this case:
In general equilibrium theory in economics, Kakutani's theorem has been used to prove the existence of set of prices which simultaneously equate supply with demand in all markets of an economy. The existence of such prices had been an open question in economics going back to at least Walras. The first proof of this result was constructed by Lionel McKenzie.
In this case:
Kakutani's fixed-point theorem is used in proving the existence of cake allocations that are both envy-free and Pareto efficient. This result is known as Weller's theorem.

Proof outline

''S'' = 0,1

The proof of Kakutani's theorem is simplest for set-valued functions defined over closed intervals of the real line. However, the proof of this case is instructive since its general strategy can be carried over to the higher-dimensional case as well.
Let φ: →2 be a set-valued function on the closed interval which satisfies the conditions of Kakutani's fixed-point theorem.
Let for i = 0, 1, … be a sequence with the following properties:
Thus, the closed intervals form a sequence of subintervals of . Condition tells us that these subintervals continue to become smaller while condition – tell us that the function φ shifts the left end of each subinterval to its right and shifts the right end of each subinterval to its left.
Such a sequence can be constructed as follows. Let a0 = 0 and b0 = 1. Let p0 be any point in φ and q0 be any point in φ. Then, conditions – are immediately fulfilled. Moreover, since p0 ∈ φ ⊂ , it must be the case that p0 ≥ 0 and hence condition is fulfilled. Similarly condition is fulfilled by q0.
Now suppose we have chosen ak, bk, pk and qk satisfying –. Let,
Then m ∈ because is convex.
If there is a r ∈ φ such that r ≥ m, then we take,
Otherwise, since φ is non-empty, there must be a s ∈ φ such that s ≤ m. In this case let,
It can be verified that ak+1, bk+1, pk+1 and qk+1 satisfy conditions –.
The cartesian product ××× is a compact set by Tychonoff's theorem. Since the sequence lies in this compact set, it must have a convergent subsequence by the Bolzano-Weierstrass theorem. Let's fix attention on such a subsequence and let its limit be. Since the graph of φ is closed it must be the case that p* ∈ φ and q* ∈ φ. Moreover, by condition, p* ≥ a* and by condition, q* ≤ b*.
But since ≤ 2−i by condition,
So, b* equals a*. Let x = b* = a*.
Then we have the situation that
If p* = q* then p* = x = q*. Since p* ∈ φ, x is a fixed point of φ.
Otherwise, we can write the following. Recall that we can parameterize a line between two points a and b by a + tb. Using our finding above that qfunction of x. By a convenient writing of x, and since φ is convex and
it once again follows that x must belong to φ since p* and q* do and hence x is a fixed point of φ.

''S'' is a ''n''-simplex

In dimensions greater one, n-simplices are the simplest objects on which Kakutani's theorem can be proved. Informally, a n-simplex is the higher-dimensional version of a triangle. Proving Kakutani's theorem for set-valued function defined on a simplex is not essentially different from proving it for intervals. The additional complexity in the higher-dimensional case exists in the first step of chopping up the domain into finer subpieces:
  • Where we split intervals into two at the middle in the one-dimensional case, barycentric subdivision is used to break up a simplex into smaller sub-simplices.
  • While in the one-dimensional case we could use elementary arguments to pick one of the half-intervals in a way that its end-points were moved in opposite directions, in the case of simplices the combinatorial result known as Sperner's lemma is used to guarantee the existence of an appropriate subsimplex.
Once these changes have been made to the first step, the second and third steps of finding a limiting point and proving that it is a fixed point are almost unchanged from the one-dimensional case.

Arbitrary ''S''

Kakutani's theorem for n-simplices can be used to prove the theorem for an arbitrary compact, convex S. Once again we employ the same technique of creating increasingly finer subdivisions. But instead of triangles with straight edges as in the case of n-simplices, we now use triangles with curved edges. In formal terms, we find a simplex which covers S and then move the problem from S to the simplex by using a deformation retract. Then we can apply the already established result for n-simplices.

Infinite-dimensional generalizations

Kakutani's fixed-point theorem was extended to infinite-dimensional locally convex topological vector spaces by Irving Glicksberg
and Ky Fan.
To state the theorem in this case, we need a few more definitions:
;Upper hemicontinuity: A set-valued function φ: X→2Y is upper hemicontinuous if for every open set W ⊂ Y, the set is open in X.
;Kakutani map: Let X and Y be topological vector spaces and φ: X→2Y be a set-valued function. If Y is convex, then φ is termed a Kakutani map if it is upper hemicontinuous and φ is non-empty, compact and convex for all x ∈ X.
Then the Kakutani–Glicksberg–Fan theorem can be stated as:
The corresponding result for single-valued functions is the Tychonoff fixed-point theorem.
There is another version that the statement of the theorem becomes the same as that in the Euclidean case:

Anecdote

In his game theory textbook, Ken Binmore recalls that Kakutani once asked him at a conference why so many economists had attended his talk. When Binmore told him that it was probably because of the Kakutani fixed point theorem, Kakutani was puzzled and replied, "What is the Kakutani fixed point theorem?"