.
Kakutani fixedpoint theorem
In mathematical analysis, the Kakutani fixedpoint theorem is a fixedpoint theorem for setvalued functions. It provides sufficient conditions for a setvalued 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 setvalued functions.
The theorem was developed by Shizuo Kakutani in 1941[1] and was famously used by John Nash[2] in his description of Nash equilibrium. It has subsequently found widespread application in game theory and economics.[3]
Statement[4]:20
Kakutani's theorem states:
LLet S be a nonempty, compact and convex subset of some Euclidean space R^{n}. Let φ: S → 2^{S} be a setvalued function on S with a closed graph and the property that φ(x) is nonempty and convex for all x ∈ S. Then φ has a fixed point.
When we say that the graph of f is closed, we mean that for all sequences \( \{x_{n}\}_{n\in \mathbb{N}} \) and \( \{y_{n}\}_{n\in \mathbb{N}} \) such that \( x_{n}\to x, y_{n}\to y \) and \( y_{n}\in f(x_{n}) \) for all n, we have \( y\in f(x) \) .
Definitions
Setvalued function
 Setvalued function
 A setvalued 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}. 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 setvalued function φ: X→2^{Y} is said to have a closed graph if the set {(x,y) y ∈ φ(x)} is a closed subset of X×Y in the product topology.
 Fixed point
 Let φ: X→2^{X} be a setvalued function. Then a ∈ X is a fixed point of φ if a ∈ φ(a).
Example
Fixed points for f(x)=[1−x/2, 1−x/4]
Let f(x) be a setvalued function defined on the closed interval [0, 1] that maps a point x to the closed interval [1 − x/2, 1 − x/4]. Then f(x) satisfies all the assumptions of the theorem and must have fixed points.
In the diagram, 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].
Nonexample
A function without fixed points
The requirement that φ(x) be convex for all x is essential for the theorem to hold.
Consider the following function defined on [0,1]:
\( f(x)= \begin{cases} 3/4 & 0 \le x < 0.5 \\ \{ 3/4, 1/4 \} & x = 0.5 \\ 1/4 & 0.5 < x \le 1 \\ \end{cases} \)
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.
Alternative statement
Some sources, including Kakutani's original paper, use the concept of upper hemicontinuity while stating the theorem:
 Let S be a nonempty, compact and convex subset of some Euclidean space R^{n}. Let φ: S→2^{S} be an upper hemicontinuous setvalued function on S with the property that φ(x) is nonempty, 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 setvalued functions,^{[5]} which says that a for a compact Hausdorff range space Y, a setvalued 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 closedvalued in the alternative statement of the Kakutani theorem, the Closed Graph Theorem implies that the two statements are equivalent.
Applications
See also: Mathematical economics
Game theory
See also: Game theory
Mathematician John Nash used the Kakutani fixed point theorem to prove a major result in game theory.[2] 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 would later earn him a Nobel Prize in Economics.
In this case, S is the set of tuples of mixed strategies chosen by each player in a game. The function φ(x) gives 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 setvalued rather than singlevalued. 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
See also: 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.[6] 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, S is the set of tuples of commodity prices. φ(x) is chosen as a function whose result is different from its arguments as long as the pricetuple 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 pricetuple which equates supply with demand everywhere.
Proof outline
S = [0,1]
The proof of Kakutani's theorem is simplest for setvalued 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 φ: [0,1]→2^{[0,1]} be a setvalued function on the closed interval [0,1] which satisfies the conditions of Kakutani's fixedpoint 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}) for i = 0, 1, … be a sequence with the following properties:

1. 1 ≥ b_{i} > a_{i} ≥ 0 2. (b_{i} − a_{i}) ≤ 2^{−i} 3. p_{i} ∈ φ(a_{i}) 4. q_{i} ∈ φ(b_{i}) 5. p_{i} ≥ a_{i} 6. q_{i} ≤ b_{i}
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. Let a_{0} = 0 and b_{0} = 1. Let p_{0} be any point in φ(0) and q_{0} be any point in φ(1). Then, conditions (1)–(4) are immediately fulfilled. Moreover, since p_{0} ∈ φ(0) ⊂ [0,1], it must be the case that p_{0} ≥ 0 and hence condition (5) is fulfilled. Similarly condition (6) is fulfilled by q_{0}.
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 ∈ [0,1] because [0,1] 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 nonempty, 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.
The cartesian product [0,1]×[0,1]×[0,1]×[0,1] is a compact set by Tychonoff's theorem. Since the sequence (a_{n}, p_{n}, b_{n}, q_{n}) lies in this compact set, it must have a convergent subsequence by the BolzanoWeierstrass theorem. 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
 q* ∈ φ(x) ≤ 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 (1t)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) is convex and
\( x=\left(\frac{xq^*}{p^*q^*}\right)p^*+\left(1\frac{xq^*}{p^*q^*}\right)q^* \)
it once again follows that x must belong to φ(x) since p* and q* do and hence x is a fixed point of φ.
S is a nsimplex
In dimensions greater one, nsimplices are the simplest objects on which Kakutani's theorem can be proved. Informally, a nsimplex is the higher dimensional version of a triangle. Proving Kakutani's theorem for setvalued function defined on a simplex is not essentially different from proving it for intervals. The additional complexity in the higherdimensional 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 onedimensional case, barycentric subdivision is used to break up a simplex into smaller subsimplices.
While in the onedimensional case we could use elementary arguments to pick one of the halfintervals in a way that its endpoints 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 onedimensional case.
Arbitrary S
Kakutani's theorem for nsimplices 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 nsimplices, 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 nsimplices.
Infinite dimensional generalizations
Kakutani's fixed point theorem was extended to infinite dimensional locally convex topological vector spaces by Irving Glicksberg^{[7]} and Ky Fan.^{[8]} To state the theorem in this case, we need a few more definitions:
 Upper semicontinuity
 A setvalued function φ: X→2^{Y} is upper semicontinuous if for every open set W ⊂ Y, the set {x φ(x) ⊂ W} is open in X.^{[9]}
 Kakutani map
 Let X and Y be topological vector spaces and φ: X→2^{Y} be a setvalued function. If Y is convex, then φ is termed a Kakutani map if it is upper semicontinuous and φ(x) is nonempty, compact and convex for all x ∈ X.^{[9]}
Then the KakutaniGlicksbergFan theorem can be stated as:^{[9]}
 Let S be a nonempty, compact and convex subset of a locally convex topological vector space. Let φ: S→2^{S} be a Kakutani map. Then φ has a fixed point.
The corresponding result for singlevalued functions is the Tychonoff fixed point theorem.
If the space on which the function is defined is Hausdorff in addition to being locally convex, then the statement of the theorem becomes the same as that in the Euclidean case:^{[5]}
 Let S be a nonempty, compact and convex subset of a locally convex Hausdorff space. Let φ: S→2^{S} be a setvalued function on S which has a closed graph and the property that φ(x) is nonempty and convex for all x ∈ S. Then the set of fixed points of φ is nonempty and compact.
Anecdote
In his game theory textbook,[10] 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?"
Further reading
Border, Kim C. (1989). Fixed Point Theorems with Applications to Economics and Game Theory. Cambridge University Press. (Standard reference on fixedpoint theory for economists. Includes a proof of Kakutani's theorem.)
Dugundji, James; Andrzej Granas (2003). Fixed Point Theory. Springer. (Comprehensive highlevel 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. HoldenDay. (Standard reference on general 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.)
References
^ Kakutani, Shizuo (1941). "A generalization of Brouwer’s fixed point theorem". Duke Mathematical Journal 8 (3): 457–459. doi:10.1215/S0012709441008384.
^ a b Nash, J.F., Jr. (1950). "Equilibrium Points in NPerson Games". Proc. Nat. Acad. Sci. U.S.A. 36 (1): 48–49. doi:10.1073/pnas.36.1.48. PMC 1063129. PMID 16588946.
^ Border, Kim C. (1989). Fixed Point Theorems with Applications to Economics and Game Theory. Cambridge University Press.
^ Osborne, Martin J., and Ariel Rubinstein. A Course in Game Theory. Cambridge, MA: MIT, 1994. Print.
^ a b Aliprantis, Charlambos; Kim C. Border (1999). "Chapter 17". Infinite Dimensional Analysis: A Hitchhiker's Guide (3rd ed.). Springer.
^ Starr, Ross M. (1997). General Equilibrium Theory. Cambridge University Press. ISBN 9780521564731.
^ Glicksberg, I.L. (1952). "A Further Generalization of the Kakutani Fixed Point Theorem, with Application to Nash Equilibrium". Proceedings of the American Mathematical Society 3 (1): 170–174. doi:10.2307/2032478. JSTOR 2032478.
^ Fan, Ky (1952). "Fixedpoint and Minimax Theorems in Locally Convex Topological Linear Spaces". Proc Natl Acad Sci U S A. 1952 February; 38(2): 121–126. 38 (2): 121–126. doi:10.1073/pnas.38.2.121. PMC 1063516. PMID 16589065.
^ a b c Dugundji, James; Andrzej Granas (2003). "Chapter II, Section 8" (limited preview). Fixed Point Theory. Springer. ISBN 9780387001739.
^ Binmore, Ken (2007). "Chapter 8". Playing for Real: A Text on Game Theory (1st ed.). Oxford.
External links
Fixed Point Theorems. (Page on fixed point theorems from the New School's History of Economic Thought site.)
Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License