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 the 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:
: ''Let'' ''S'' ''be a non-empty, compact and convex subset of some Euclidean space'' R^''n''.
:''Let'' ''φ'': ''S'' → 2^''S'' ''be a set-valued function on'' ''S'' ''with the following properties:''
:* ''φ has ''a closed graph;''
:* ''φ''(''x'') ''is non-empty and convex for all'' ''x'' ∈ ''S''.
:''Then'' ''φ'' ''has a fixed point.''

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'' → 2^''Y'', such that ''φ''(''x'') is non-empty for every $x \in X$. 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'' → 2^''Y'' 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 $x_n\to x$, $y_\to y$ and $y_\in \phi(x_n)$ for all $n$, we have $y\in \phi(x)$.
;Fixed point: Let φ: ''X'' → 2^''X'' be a set-valued function. Then ''a'' ∈ ''X'' is a fixed point of ''φ'' if ''a'' ∈ ''φ''(''a'').

Examples

A function with infinitely many fixed points

The function:
\varphi(x)=
-x/2, ~1-x/4, 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 (dotted line in red) which intersects the graph of the function (shaded in grey) is a fixed point, so in fact there is an infinity of fixed points in this particular case. For example, ''x'' = 0.72 (dashed line in blue) is a fixed point since 0.72 ∈   − 0.72/2, 1 − 0.72/4

A function with a unique fixed point

The function:

:
\varphi(x)=
\begin
3/4 & 0 \le x < 0.5 \\
,1 & x = 0.5 \\
1/4 & 0.5 < x \le 1
\end

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 ,1

A function that does not satisfy convexity

The requirement that ''φ''(''x'') be convex for all ''x'' is essential for the theorem to hold.

Consider the following function defined on ,1
:$\varphi(x)= \begin 3/4 & 0 \le x < 0.5 \\ \ & x = 0.5 \\ 1/4 & 0.5 < x \le 1 \end$
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 closed graph

Consider the following function defined on ,1

:$\varphi(x)= \begin 3/4 & 0 \le x < 0.5 \\ 1/4 & 0.5 \le x \le 1 \end$

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 ''x_n'' = 0.5 - 1/''n'', ''y_n'' = 3/4.

Alternative statement

Some sources, including Kakutani's original paper, use the concept of upper hemicontinuity while stating the theorem:
:''Let'' ''S'' ''be a non-empty, compact and convex subset of some Euclidean space'' R^''n''. ''Let'' ''φ'': ''S''→2^''S'' ''be an upper hemicontinuous set-valued function on'' ''S'' ''with the property that'' ''φ''(''x'') ''is non-empty, closed, and convex for all'' ''x'' ∈ ''S''. ''Then'' ''φ'' ''has a fixed point.''

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''→2^''Y'' has a closed graph if and only if it is upper hemicontinuous and ''φ''(''x'') is a closed set for all ''x''. Since all Euclidean spaces are Hausdorff (being metric spaces) 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 finite number of players. This work later earned him a Nobel Prize in Economics. In this case:

* The base set ''S'' is the set of tuples of mixed strategies chosen by each player in a game. If each player has ''k'' possible actions, then each player's strategy is a ''k''-tuple of probabilities summing up to 1, so each player's strategy space is the standard simplex in ''R''^''k''''.'' Then, ''S'' is the cartesian product of all these simplices. It is indeed a nonempty, compact and convex subset of ''R''^''kn''''.''
* The function φ(''x'') associates with each tuple a new tuple where each player's strategy is her best response to other players' strategies in ''x''. Since there may be a number of responses which are equally good, φ is set-valued rather than single-valued. For each ''x'', φ(''x'') is nonempty since there is always at least one best response. It is convex, since a mixture of two best-responses for a player is still a best-response for the player. It can be proved that φ has a closed graph.
* Then the Nash equilibrium of the game is defined as a fixed point of φ, i.e. a tuple of strategies where each player's strategy is a best response to the strategies of the other players. Kakutani's theorem ensures that this fixed point exists.

General equilibrium

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:

* The base set ''S'' is the set of tuples of commodity prices.
* The function φ(''x'') is chosen so that its result differs from its arguments as long as the price-tuple ''x'' does not equate supply and demand everywhere. The challenge here is to construct φ so that it has this property while at the same time satisfying the conditions in Kakutani's theorem. If this can be done then φ has a fixed point according to the theorem. Given the way it was constructed, this fixed point must correspond to a price-tuple which equates supply with demand everywhere.

Fair division

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.

Relation to Brouwer's fixed-point theorem

Brouwer's fixed-point theorem is a special case of Kakutani fixed-point theorem. Conversely, Kakutani fixed-point theorem is an immediate generalization via the approximate selection theorem:

Proof outline

''S'' = ,1/nowiki>

The proof of Kakutani's theorem is simplest for set-valued functions defined over closed intervals of the real line. Moreover, the proof of this case is instructive since its general strategy can be carried over to the higher-dimensional case as well.

Let φ: ,1/nowiki>→2 ^,1/nowiki> be a set-valued function on the closed interval ,1/nowiki> which satisfies the conditions of Kakutani's fixed-point theorem.

* Create a sequence of subdivisions of ,1/nowiki> with adjacent points moving in opposite directions.
Let (''a''_''i'', ''b''_''i'', ''p''_''i'', ''q''_''i'') for ''i'' = 0, 1, … be a sequence with the following properties:
:

Thus, the closed intervals /nowiki>''a''_''i'', ''b''_''i''/nowiki> form a sequence of subintervals of ,1/nowiki>. Condition (2) tells us that these subintervals continue to become smaller while condition (3)–(6) 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 ''a''₀ = 0 and ''b''₀ = 1. Let ''p''₀ be any point in φ(0) and ''q''₀ be any point in φ(1). Then, conditions (1)–(4) are immediately fulfilled. Moreover, since ''p''₀ ∈ φ(0) ⊂ ,1/nowiki>, it must be the case that ''p''₀ ≥ 0 and hence condition (5) is fulfilled. Similarly condition (6) is fulfilled by ''q''₀.

Now suppose we have chosen ''a''_''k'', ''b''_''k'', ''p''_''k'' and ''q''_''k'' satisfying (1)–(6). Let,
:''m'' = (''a''_''k''+''b''_''k'')/2.
Then ''m'' ∈ ,1/nowiki> because ,1/nowiki> is convex.

If there is a ''r'' ∈ φ(''m'') such that ''r'' ≥ ''m'', then we take,
:''a''_''k''+1 = ''m''
:''b''_''k''+1 = ''b''_''k''
:''p''_''k''+1 = ''r''
:''q''_''k''+1 = ''q''_''k''
Otherwise, since φ(''m'') is non-empty, there must be a ''s'' ∈ φ(''m'') such that ''s'' ≤ ''m''. In this case let,
:''a''_''k''+1 = ''a''_''k''
:''b''_''k''+1 = ''m''
:''p''_''k''+1 = ''p''_''k''
:''q''_''k''+1 = ''s''.
It can be verified that ''a''_''k''+1, ''b''_''k''+1, ''p''_''k''+1 and ''q''_''k''+1 satisfy conditions (1)–(6).

* Find a limiting point of the subdivisions.
We have a pair of sequences of intervals, and we would like to show them to converge to a limiting point with the Bolzano-Weierstrass theorem. To do so, we construe these two interval sequences as a single sequence of points, (''a''_''n'', ''p''_''n'', ''b''_''n'', ''q''_''n''). This lies in the cartesian product ,1/nowiki>× ,1/nowiki>× ,1/nowiki>× ,1/nowiki>, which is a compact set by Tychonoff's theorem. Since our sequence (''a''_''n'', ''p''_''n'', ''b''_''n'', ''q''_''n'') lies in a compact set, it must have a convergent subsequence by Bolzano-Weierstrass. Let's fix attention on such a subsequence and let its limit be (''a''*, ''p''*,''b''*,''q''*). Since the graph of φ is closed it must be the case that ''p''* ∈ φ(''a''*) and ''q''* ∈ φ(''b''*). Moreover, by condition (5), ''p''* ≥ ''a''* and by condition (6), ''q''* ≤ ''b''*.

But since (''b''_''i'' − ''a''_''i'') ≤ 2^−''i'' by condition (2),
:''b''* − ''a''* = (lim ''b''_''n'') − (lim ''a''_''n'') = lim (''b''_''n'' − ''a''_''n'') = 0.
So, ''b''* equals ''a''*. Let ''x'' = ''b''* = ''a''*.

Then we have the situation that

:φ(''x'') ∋ ''q''* ≤ ''x'' ≤ ''p''* ∈ φ(''x'').

* Show that the limiting point is a fixed point.
If ''p''* = ''q''* then ''p''* = ''x'' = ''q''*. Since ''p''* ∈ φ(''x''), ''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 (1-t)a + tb. Using our finding above that qconvex