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 [cite journal
last = Kakutani
first = Shizuo
authorlink = Shizuo Kakutani
title = A generalization of Brouwer’s fixed point theorem
journal = Duke Mathematical Journal
volume = 8
pages = 457–459
issue = 3
date = 1941
doi = 10.1215/S0012-7094-41-00838-4] and was famously used by John Nash in his description of Nash equilibrium. It has subsequently found widespread application in game theory and economics. [cite book
last = Border
first = Kim C.
title = Fixed Point Theorems with Applications to Economics and Game Theory
year = 1989
publisher = Cambridge University Press ]

tatement

Kakutani's theorem states:: "Let S be a non-empty, compact and convex subset of some Euclidean space Rⁿ. Let φ: S → 2^S be a set-valued function on S with a closed graph and the property that φ(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".;Closed graph: A set-valued 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 set-valued function. Then "a" ∈ "X" is a fixed point of φ if "a" ∈ φ("a").

Example

[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] .

Non-example

The requirement that φ("x") be convex for all "x" 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 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 non-empty, compact and convex subset of some Euclidean space Rⁿ. 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.

Since an upper hemicontinuous function has a closed graph by definition, the alternative statement of the theorem is an immediate consequence of our original statement.

Conversely, the alternative statement implies our original version. Let φ be a function which satisfies the requirements of the original statement. Then it has a closed graph. Since "S" is a compact subset of an Euclidean space, it must be bounded (by the Heine-Borel theorem). For all "K" ⊂ "S", and therefore also for compact "K", φ("K") is a subset of the bounded set "S" and hence is itself bounded. It follows that φ is upper hemicontinuous. Further, since the graph of φ is closed, φ("x") is a closed set for all values of "x". Therefore φ satisfies all the requirements of the alternative statement and must have a fixed point.

Applications

Game theory

Mathematician John Nash used the Kakutani fixed point theorem to prove a major result in game theory.cite journal
last = Nash
first = J.F., Jr.
authorlink = John Forbes Nash
title = Equilibrium Points in N-Person Games
journal = Proc. Nat. Acad. Sci. U.S.A.
volume = 36
pages = 48–49
date = 1950
url = http://www.pubmedcentral.nih.gov/articlerender.fcgi?artid=1063129
doi = 10.1073/pnas.36.1.48
pmid = 16588946 ] 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 set-valued rather than single-valued. 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. [ cite book
last = Starr
first = Ross M.
authorlink =
title = General Equilibrium Theory
year = 1997
publisher = Cambridge University Press
url = http://books.google.com/books?id=Lv3VtS9CcAoC&pg
format = limited preview ]

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 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.

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 φ: [0,1] →2 ^[0,1] be a set-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") for "i" = 0, 1, … be a sequence with the following properties::

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 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) ⊂ [0,1] , 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" ∈ [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 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.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 Bolzano-Weierstrass 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, since φ("x") is convex and:$x=left(frac\{x-q^*\}\{p^*-q^*\}\; ight)p^*+left(1-frac\{x-q^*\}\{p^*-q^*\}\; ight)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 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 trianges 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 [cite journal
last = Glicksberg
first = I.L.
title = A Further Generalization of the Kakutani Fixed Point Theorem, with Application to Nash Equilibrium
journal = Proceedings of the American Mathematical Society
volume = 3
issue = 1
pages = 170–174
date = 1952
doi = 10.2307/2032478] and Ky Fan [cite journal
last = Fan
first = Ky
title = Fixed-point and Minimax Theorems in Locally Convex Topological Linear Spaces
journal = Proc Natl Acad Sci U S A. 1952 February; 38(2): 121–126.
volume = 38
issue = 2
pages = 121–126
date = 1952
url = http://www.pubmedcentral.nih.gov/articlerender.fcgi?artid=1063516
doi = 10.1073/pnas.38.2.121
pmid = 16589065] .To state the theorem in this case, we need a few more definitions:;Upper semicontinuity: A set-valued function φ: "X"→2^"Y" is upper semicontinuous if for every open set "W" ⊂ "Y", the set {"x"| φ("x") ⊂ "W"} is open in "X".cite book
last = Dugundji
first = James
authorlink = James Dugundji
coauthors = Andrzej Granas
title = Fixed Point Theory
year = 2003
publisher = Springer
chapter = Chapter II, Section 8
url = http://books.google.com/books?id=4_iJAoLSq3cC
format = limited preview ] ;Kakutani
topological vector spaces and φ: "X"→2^"Y" be a set-valued function. If "Y" is convex, then φ is termed a Kakutani map if it is upper semicontinuous and φ("x") is non-empty, compact and convex for all "x" ∈ "X".

Then the Kakutani-Glicksberg-Fan theorem can be stated as::"Let S be a non-empty, 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 single-valued 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:cite book
last = Aliprantis
first = Charlambos
coauthors = Kim C. Border
title = Infinite Dimensional Analysis: A Hitchhiker's Guide
year = 1999
publisher = Springer
edition = 2nd edition
chapter = Chapter 16
url = http://books.google.com/books?id=6jjY2Vi3aDEC
format = limited preview ]

:"Let S be a non-empty, compact and convex subset of a locally convex Hausdorff space. Let φ: S→2^S be a set-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 of fixed points of φ is non-empty and compact."

Further reading

* cite book
last = Border
first = Kim C.
title = Fixed Point Theorems with Applications to Economics and Game Theory
year = 1989
publisher = Cambridge University Press (Standard reference on fixed-point theory for economists. Includes a proof of Kakutani's theorem.)

* cite book
last = Dugundji
first = James
authorlink = James Dugundji
coauthors = Andrzej Granas
title = Fixed Point Theory
year = 2003
publisher = Springer (Comprehensive high-level mathematical treatment of fixed point theory, including the infinite dimensional analogues of Kakutani's theorem.)

* cite book
last = Arrow
first = Kenneth J.
authorlink = Kenneth Arrow
coauthors = F. H. Hahn
title = General Competitive Analysis
year = 1971
publisher = Holden-Day (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

External links

* [http://cepa.newschool.edu/het/essays/math/fixedpoint.htm Fixed Point Theorems] . (Page on fixed point theorems from the New School's [http://cepa.newschool.edu/het/home.htm History of Economic Thought] site.)