Inmathematical analysis, theKakutani fixed-point theorem is afixed-point theorem forset-valued functions. It providessufficient conditions for a set-valued function defined on aconvex,compact subset of aEuclidean space to have afixed point, i.e. a point which ismapped to a set containing it. The Kakutani fixed point theorem is a generalization of theBrouwer fixed point theorem. The Brouwer fixed point theorem is a fundamental result intopology which proves the existence of fixed points forcontinuous functions defined on compact, convex subsets of Euclidean spaces. Kakutani's theorem extends this to set-valued functions.

The theorem was developed byShizuo Kakutani in 1941,^[1] and was used byJohn Nash in his description ofNash equilibria.^[2] It has subsequently found widespread application ingame theory andeconomics.^[3]

Kakutani's theorem states:^[4]

LetSbe anon-empty,compact andconvexsubset of someEuclidean spaceRⁿ.

Letφ: S → 2^Sbe aset-valued function onSwith the following properties:

• φ hasaclosed graph;
• φ(x)is non-empty and convex for allx ∈ S.

Thenφhas afixed point.

Set-valued function

Aset-valued functionφ from the setX to the setY is some rule that associates oneor more points inY with each point inX. Formally it can be seen just as an ordinaryfunction fromX to thepower set ofY, written asφ: X → 2^Y, such thatφ(x) is non-empty for every${\displaystyle x\in X}$. Some prefer the termcorrespondence, 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 aclosed graph if the set {(x,y) | y ∈ φ(x)} is aclosed subset ofX × Y in theproduct topology i.e. for all sequences${\displaystyle \{x_n{\}}_{n\in \mathbb{N}}}$ and${\displaystyle \{y_n{\}}_{n\in \mathbb{N}}}$ such that${\displaystyle x_n\to x}$,${\displaystyle y_n\to y}$ and${\displaystyle y_n\in \varphi (x_n)}$ for all${\displaystyle n}$, we have${\displaystyle y\in \varphi (x)}$.

Fixed point

Let φ: X → 2^X be a set-valued function. Thena ∈ X is afixed point ofφ ifa ∈ φ(a).

The function:${\displaystyle \phi (x)=[1-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 ∈ [1 − 0.72/2, 1 − 0.72/4].

The function:

satisfies all Kakutani's conditions, and indeed it has a fixed point:x = 0.5 is a fixed point, sincex is contained in the interval [0,1].

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

Consider the following function defined on [0,1]:

The function has no fixed point. Though it satisfies all other requirements of Kakutani's theorem, its value fails to be convex atx = 0.5.

Consider the following function defined on [0,1]:

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

Some sources, including Kakutani's original paper, use the concept ofupper hemicontinuity while stating the theorem:

LetSbe anon-empty,compact andconvexsubset of someEuclidean spaceRⁿ.Letφ: S→2^Sbe anupper hemicontinuousset-valued function onSwith the property thatφ(x)is non-empty, closed, and convex for allx ∈ S.Thenφhas afixed 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 theclosed graph theorem for set-valued functions,^[5] which says that for a compactHausdorff range spaceY, 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 allx. Since allEuclidean spaces are Hausdorff (beingmetric 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.

The Kakutani fixed point theorem can be used to prove theminimax theorem in the theory ofzero-sum games. This application was specifically discussed by Kakutani's original paper.^[1]

MathematicianJohn Nash used the Kakutani fixed point theorem to prove a major result ingame theory.^[2] Stated informally, the theorem implies the existence of aNash equilibrium in every finite game with mixed strategies for any finite number of players. This work later earned him aNobel Prize in Economics. In this case:

• The base setS is the set oftuples ofmixed strategies chosen by each player in a game. If each player hask possible actions, then each player's strategy is ak-tuple of probabilities summing up to 1, so each player's strategy space is thestandard simplex inR^k. Then,S is the cartesian product of all these simplices. It is indeed a nonempty, compact and convex subset ofR^kn.
• The function φ(x) associates with each tuple a new tuple where each player's strategy is her best response to other players' strategies inx. Since there may be a number of responses which are equally good, φ is set-valued rather than single-valued. For eachx, φ(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 theNash 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.

Ingeneral 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.^[6] The existence of such prices had been an open question in economics going back to at leastWalras. The first proof of this result was constructed byLionel McKenzie.^[7]

In this case:

• The base setS is the set oftuples of commodity prices.
• The function φ(x) is chosen so that its result differs from its arguments as long as the price-tuplex 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.

Kakutani's fixed-point theorem is used in proving the existence of cake allocations that are bothenvy-free andPareto efficient. This result is known asWeller's 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 theapproximate selection theorem:^[8]

The proof of Kakutani's theorem is simplest for set-valued functions defined overclosed 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 φ: [0,1]→2^[0,1] be aset-valued function on the closed interval [0,1] which satisfies the conditions of Kakutani's fixed-point theorem.

• Create a sequence of subdivisions of [0,1] with adjacent points moving in opposite directions.

Let (a_i,b_i,p_i,q_i) fori = 0, 1, … be asequence with the following properties:

1.	1 ≥bi >ai ≥ 0	2.	(bi −ai) ≤ 2−i
3.	pi ∈ φ(ai)	4.	qi ∈ φ(bi)
5.	pi ≥ai	6.	qi ≤bi

Thus, the closed intervals [a_i,b_i] form a sequence of subintervals of [0,1]. 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. Leta₀ = 0 andb₀ = 1. Letp₀ be any point in φ(0) andq₀ be any point in φ(1). Then, conditions (1)–(4) are immediately fulfilled. Moreover, sincep₀ ∈ φ(0) ⊂ [0,1], it must be the case thatp₀ ≥ 0 and hence condition (5) is fulfilled. Similarly condition (6) is fulfilled byq₀.

Now suppose we have chosena_k,b_k,p_k andq_k satisfying (1)–(6). Let,

m = (a_k+b_k)/2.

Thenm ∈ [0,1] because [0,1] isconvex.

If there is ar ∈ φ(m) such thatr ≥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 as ∈ φ(m) such thats ≤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 thata_k+1,b_k+1,p_k+1 andq_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 theBolzano-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 thecartesian product [0,1]×[0,1]×[0,1]×[0,1], which is acompact set byTychonoff's theorem. Since our sequence (a_n,p_n,b_n,q_n) lies in a compact set, it must have aconvergentsubsequence byBolzano-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 thatp* ∈ φ(a*) andq* ∈ φ(b*). Moreover, by condition (5),p* ≥a* and by condition (6),q* ≤b*.

But since (b_i −a_i) ≤ 2⁻ⁱ by condition (2),

b* −a* = (limb_n) − (lima_n) = lim (b_n −a_n) = 0.

So,b* equalsa*. Letx =b* =a*.

Then we have the situation that

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

• Show that the limiting point is a fixed point.

Ifp* =q* thenp* =x =q*. Sincep* ∈ φ(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 q<x<p, we can create such a line between p and q as a function of x (notice the fractions below are on the unit interval). By a convenient writing of x, and since φ(x) isconvex and

${\displaystyle x=\left(\frac{x-q^{\ast }}{p^{\ast }-q^{\ast }}\right)p^{\ast }+\left(1-\frac{x-q^{\ast }}{p^{\ast }-q^{\ast }}\right)q^{\ast }}$

it once again follows thatx must belong to φ(x) sincep* andq* do and hencex is a fixed point of φ.

In dimensions greater one,n-simplices are the simplest objects on which Kakutani's theorem can be proved. Informally, an-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 thecombinatorial result known asSperner'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.

Kakutani's theorem for n-simplices can be used to prove the theorem for an arbitrary compact, convexS. 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 coversS and then move the problem fromS to the simplex by using adeformation retract. Then we can apply the already established result for n-simplices.

Kakutani's fixed-point theorem was extended to infinite-dimensionallocally convex topological vector spaces byIrving Glicksberg^[9]andKy Fan.^[10]To state the theorem in this case, we need a few more definitions:

Upper hemicontinuity

A set-valued function φ: X→2^Y isupper hemicontinuous if for everyopen setW ⊂ Y, the set {x| φ(x) ⊂ W} is open inX.^[11]

Kakutani map

LetX andY betopological vector spaces and φ: X→2^Y be a set-valued function. IfY is convex, then φ is termed aKakutani map if it is upper hemicontinuous and φ(x) is non-empty, compact and convex for allx ∈ X.^[11]

Then the Kakutani–Glicksberg–Fan theorem can be stated as:^[11]

Let S be anon-empty,compact andconvexsubset of aHausdorfflocally convex topological vector space. Let φ: S→2^S be a Kakutani map. Then φ has a fixed point.

The corresponding result for single-valued functions is theTychonoff fixed-point theorem.

There is another version that the statement of the theorem becomes the same as that in theEuclidean case:^[5]

Let S be anon-empty,compact andconvexsubset of alocally convexHausdorff space. Let φ: S→2^S be aset-valued function on S which has a closed graph and the property that φ(x) is non-empty and convex for all x ∈ S. Then the set offixed points of φ is non-empty and compact.

In his game theory textbook,^[12]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?"

• Border, Kim C. (1989).Fixed Point Theorems with Applications to Economics and Game Theory. Cambridge University Press.(Standard reference on fixed-point theory for economists. Includes a proof of Kakutani's theorem.)
• Dugundji, James; Andrzej Granas (2003).Fixed Point Theory. Springer.(Comprehensive high-level mathematical treatment of fixed point theory, including the infinite dimensional analogues of Kakutani's theorem.)
• Arrow, Kenneth J.; F. H. Hahn (1971).General Competitive Analysis. Holden-Day.ISBN 978-0-8162-0275-1.(Standard reference ongeneral equilibrium theory. Chapter 5 uses Kakutani's theorem to prove the existence of equilibrium prices. Appendix C includes a proof of Kakutani's theorem and discusses its relationship with other mathematical results used in economics.)

• "Kakutani theorem",Encyclopedia of Mathematics,EMS Press, 2001 [1994]

• Fixed-point theorems
• Theorems in convex geometry
• Theorems in topology
• General equilibrium theory

• Articles with short description
• Short description is different from Wikidata