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, [1] and was used by John Nash in his description of Nash equilibria. [2] It has subsequently found widespread application in game theory and economics. [3]
Kakutani's theorem states: [4]
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 (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, since x is contained in the interval [0,1].
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.
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 sequences xn = 0.5 - 1/n, yn = 3/4.
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, [5] 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 φ(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.
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. [1]
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 finite 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. [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. [7]
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.
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: [8]
By the approximate selection theorem, there exists a sequence of continuous such that . By Brouwer fixed-point theorem, there exists a sequence such that , so .
Since is compact, we can take a convergent subsequence . Then since it is a closed set.
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 φ: [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.
Let (ai, bi, pi, qi) for i = 0, 1, … be a sequence 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 [ai, bi] 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 a0 = 0 and b0 = 1. Let p0 be any point in φ(0) and q0 be any point in φ(1). Then, conditions (1)–(4) are immediately fulfilled. Moreover, since p0 ∈ φ(0) ⊂ [0,1], it must be the case that p0 ≥ 0 and hence condition (5) is fulfilled. Similarly condition (6) is fulfilled by q0.
Now suppose we have chosen ak, bk, pk and qk satisfying (1)–(6). Let,
Then m ∈ [0,1] because [0,1] is convex.
If there is a r ∈ φ(m) such that r ≥ m, then we take,
Otherwise, since φ(m) is non-empty, there must be a s ∈ φ(m) such that s ≤ m. In this case let,
It can be verified that ak+1, bk+1, pk+1 and qk+1 satisfy conditions (1)–(6).
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, (an, pn, bn, qn). This lies in the cartesian product [0,1]×[0,1]×[0,1]×[0,1], which is a compact set by Tychonoff's theorem. Since our sequence (an, pn, bn, qn) 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 (bi − ai) ≤ 2−i by condition (2),
So, b* equals a*. Let x = b* = a*.
Then we have the situation that
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 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
it once again follows that x must belong to φ(x) since p* and q* do and hence x is a fixed point of φ.
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:
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, 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.
Kakutani's fixed-point theorem was extended to infinite-dimensional locally convex topological vector spaces by Irving Glicksberg [9] and Ky Fan. [10] To state the theorem in this case, we need a few more definitions:
Then the Kakutani–Glicksberg–Fan theorem can be stated as: [11]
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: [5]
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?"
Brouwer's fixed-point theorem is a fixed-point theorem in topology, named after L. E. J. (Bertus) Brouwer. It states that for any continuous function mapping a nonempty compact convex set to itself, there is a point such that . The simplest forms of Brouwer's theorem are for continuous functions from a closed interval in the real numbers to itself or from a closed disk to itself. A more general form than the latter is for continuous functions from a nonempty convex compact subset of Euclidean space to itself.
In mathematical analysis, a metric space M is called complete if every Cauchy sequence of points in M has a limit that is also in M.
In the mathematical field of algebraic topology, the fundamental group of a topological space is the group of the equivalence classes under homotopy of the loops contained in the space. It records information about the basic shape, or holes, of the topological space. The fundamental group is the first and simplest homotopy group. The fundamental group is a homotopy invariant—topological spaces that are homotopy equivalent have isomorphic fundamental groups. The fundamental group of a topological space is denoted by .
In mathematical analysis, the intermediate value theorem states that if is a continuous function whose domain contains the interval [a, b], then it takes on any given value between and at some point within the interval.
In computability theory, Kleene's recursion theorems are a pair of fundamental results about the application of computable functions to their own descriptions. The theorems were first proved by Stephen Kleene in 1938 and appear in his 1952 book Introduction to Metamathematics. A related theorem, which constructs fixed points of a computable function, is known as Rogers's theorem and is due to Hartley Rogers, Jr.
In mathematics, a real-valued function is called convex if the line segment between any two distinct points on the graph of the function lies above or on the graph between the two points. Equivalently, a function is convex if its epigraph is a convex set. In simple terms, a convex function graph is shaped like a cup , while a concave function's graph is shaped like a cap .
In mathematics, the closed graph theorem may refer to one of several basic results characterizing continuous functions in terms of their graphs. Each gives conditions when functions with closed graphs are necessarily continuous.
In mathematics, a number of fixed-point theorems in infinite-dimensional spaces generalise the Brouwer fixed-point theorem. They have applications, for example, to the proof of existence theorems for partial differential equations.
In mathematics, triangulation describes the replacement of topological spaces by piecewise linear spaces, i.e. the choice of a homeomorphism in a suitable simplicial complex. Spaces being homeomorphic to a simplicial complex are called triangulable. Triangulation has various uses in different branches of mathematics, for instance in algebraic topology, in complex analysis or in modeling.
In the mathematical field of mathematical analysis, Lusin's theorem or Lusin's criterion states that an almost-everywhere finite function is measurable if and only if it is a continuous function on nearly all its domain. In the informal formulation of J. E. Littlewood, "every measurable function is nearly continuous".
In the mathematical discipline of functional analysis, the concept of a compact operator on Hilbert space is an extension of the concept of a matrix acting on a finite-dimensional vector space; in Hilbert space, compact operators are precisely the closure of finite-rank operators in the topology induced by the operator norm. As such, results from matrix theory can sometimes be extended to compact operators using similar arguments. By contrast, the study of general operators on infinite-dimensional spaces often requires a genuinely different approach.
A mathematical object X has the fixed-point property if every suitably well-behaved mapping from X to itself has a fixed point. The term is most commonly used to describe topological spaces on which every continuous mapping has a fixed point. But another use is in order theory, where a partially ordered set P is said to have the fixed point property if every increasing function on P has a fixed point.
In mathematics, a quasi-isometry is a function between two metric spaces that respects large-scale geometry of these spaces and ignores their small-scale details. Two metric spaces are quasi-isometric if there exists a quasi-isometry between them. The property of being quasi-isometric behaves like an equivalence relation on the class of metric spaces.
In functional analysis, a branch of mathematics, Michael selection theorem is a selection theorem named after Ernest Michael. In its most popular form, it states the following:
The maximum theorem provides conditions for the continuity of an optimized function and the set of its maximizers with respect to its parameters. The statement was first proven by Claude Berge in 1959. The theorem is primarily used in mathematical economics and optimal control.
In functional analysis, a branch of mathematics, a selection theorem is a theorem that guarantees the existence of a single-valued selection function from a given set-valued map. There are various selection theorems, and they are important in the theories of differential inclusions, optimal control, and mathematical economics.
The Shapley–Folkman lemma is a result in convex geometry that describes the Minkowski addition of sets in a vector space. It is named after mathematicians Lloyd Shapley and Jon Folkman, but was first published by the economist Ross M. Starr.
In mathematics, the Markov–Kakutani fixed-point theorem, named after Andrey Markov and Shizuo Kakutani, states that a commuting family of continuous affine self-mappings of a compact convex subset in a locally convex topological vector space has a common fixed point. This theorem is a key tool in one of the quickest proofs of amenability of abelian groups.
In real analysis and approximation theory, the Kolmogorov–Arnold representation theorem states that every multivariate continuous function can be represented as a superposition of continuous single-variable functions.
In mathematics, particularly in functional analysis and topology, closed graph is a property of functions. A function f : X → Y between topological spaces has a closed graph if its graph is a closed subset of the product space X × Y. A related property is open graph.