Kakutani fixed-point theorem

Last updated

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.

Contents

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]

Statement

Kakutani's theorem states: [4]

LetSbe a non-empty, compact and convex subset of some Euclidean space Rn.
Letφ: S  2Sbe a set-valued function onSwith the following properties:
  • φ has a closed graph;
  • φ(x) is non-empty and convex for allx  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  2Y, such that φ(x) is non-empty for every . 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  2Y 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 i.e. for all sequences and such that , and for all , we have .
Fixed point
Let φ: X  2X be a set-valued function. Then a  X is a fixed point of φ if a  φ(a).

Examples

Fixed points for ph(x)=[1-x/2, 1-x/4] Kakutani.svg
Fixed points for φ(x)=[1−x/2, 1−x/4]

A function with infinitely many fixed points

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

A function with a unique fixed point

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

A function that does not satisfy convexity

A function without fixed points Kakutani non.svg
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]:

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

Alternative statement

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

LetSbe a non-empty, compact and convex subset of some Euclidean space Rn. Letφ: S→2Sbe an upper hemicontinuous set-valued function onSwith the property thatφ(x) is non-empty, closed, and convex for allx  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, [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.

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. [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 number of players. This work later earned him a Nobel Prize in Economics. In this case:

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

In this case:

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.

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.

Let (ai, bi, pi, qi) for i = 0, 1, … be a sequence with the following properties:

1.1 ≥ bi>ai ≥ 02.(biai) ≤ 2i
3.pi ∈ φ(ai)4.qi ∈ φ(bi)
5.piai6.qibi

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,

m = (ak+bk)/2.

Then m[0,1] because [0,1] is convex.

If there is a r ∈ φ(m) such that rm, then we take,

ak+1 = m
bk+1 = bk
pk+1 = r
qk+1 = qk

Otherwise, since φ(m) is non-empty, there must be a s ∈ φ(m) such that sm. In this case let,

ak+1 = ak
bk+1 = m
pk+1 = pk
qk+1 = s.

It can be verified that ak+1, bk+1, pk+1 and qk+1 satisfy conditions (1)–(6).

The cartesian product [0,1]×[0,1]×[0,1]×[0,1] is a compact set by Tychonoff's theorem. Since the sequence (an, pn, bn, qn) 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 (biai) ≤ 2i by condition (2),

b* − a* = (lim bn) − (lim an) = lim (bnan) = 0.

So, b* equals a*. Let x = b* = a*.

Then we have the situation that

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

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

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:

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

Infinite-dimensional generalizations

Kakutani's fixed-point theorem was extended to infinite-dimensional locally convex topological vector spaces by Irving Glicksberg [8] and Ky Fan. [9] To state the theorem in this case, we need a few more definitions:

Upper hemicontinuity
A set-valued function φ: X→2Y is upper hemicontinuous if for every open set W  Y, the set {x| φ(x)  W} is open in X. [10]
Kakutani map
Let X and Y be topological vector spaces and φ: X→2Y be a set-valued function. If Y is convex, then φ is termed a Kakutani map if it is upper hemicontinuous and φ(x) is non-empty, compact and convex for all x  X. [10]

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

Let S be a non-empty, compact and convex subset of a Hausdorff locally convex topological vector space. Let φ: S→2S be a Kakutani map. Then φ has a fixed point.

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]

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

Anecdote

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

Related Research Articles

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 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 convex compact subset of Euclidean space to itself.

Convex set In geometry, set that intersects every line into a single line segment

In geometry, a subset of a Euclidean space, or more generally an affine space over the reals, is convex if, given any two points in the subset, the subset contains the whole line segment that joins them. Equivalently, a convex set or a convex region is a subset that intersects every line into a single line segment . For example, a solid cube is a convex set, but anything that is hollow or has an indent, for example, a crescent shape, is not convex.

Intermediate value theorem Continuous function on an interval takes on every value between its values at the ends

In mathematical analysis, the intermediate value theorem states that if f is a continuous function whose domain contains the interval [a, b], then it takes on any given value between f(a) and f(b) at some point within the interval.

In mathematics, weak topology is an alternative term for certain initial topologies, often on topological vector spaces or spaces of linear operators, for instance on a Hilbert space. The term is most commonly used for the initial topology of a topological vector space with respect to its continuous dual. The remainder of this article will deal with this case, which is one of the concepts of functional analysis.

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

Multivalued function Generalization of a function that may produce several outputs for each input

In mathematics, a multivalued function, also called multifunction, many-valued function, set-valued function, is similar to a function, but may associate several values to each input. More precisely, a multivalued function from a domain X to a codomain Y associates each x in X to one or more values y in Y; it is thus a serial binary relation. Some authors allow a multivalued function to have no value for some inputs.

Jensens inequality Theorem of convex functions

In mathematics, Jensen's inequality, named after the Danish mathematician Johan Jensen, relates the value of a convex function of an integral to the integral of the convex function. It was proved by Jensen in 1906. Given its generality, the inequality appears in many forms depending on the context, some of which are presented below. In its simplest form the inequality states that the convex transformation of a mean is less than or equal to the mean applied after convex transformation; it is a simple corollary that the opposite is true of concave transformations.

Fixed point (mathematics) Point preserved by an endomorphism

In mathematics, a fixed point of a function is an element of the function's domain that is mapped to itself by the function. That is to say, c is a fixed point of the function f if f(c) = c. This means f(f ) = fn(c) = c, an important terminating consideration when recursively computing f. A set of fixed points is sometimes called a fixed set.

Closed graph theorem Theorem relating continuity to graphs

In mathematics, the closed graph theorem is a basic result which characterizes continuous functions in terms of their graphs. In particular, they give conditions when functions with closed graphs are necessarily continuous. In mathematics, there are several results known as the "closed graph theorem".

In functional analysis and related areas of mathematics, locally convex topological vector spaces (LCTVS) or locally convex spaces are examples of topological vector spaces (TVS) that generalize normed spaces. They can be defined as topological vector spaces whose topology is generated by translations of balanced, absorbent, convex sets. Alternatively they can be defined as a vector space with a family of seminorms, and a topology can be defined in terms of that family. Although in general such spaces are not necessarily normable, the existence of a convex local base for the zero vector is strong enough for the Hahn–Banach theorem to hold, yielding a sufficiently rich theory of continuous linear functionals.

In mathematics, a duality translates concepts, theorems or mathematical structures into other concepts, theorems or structures, in a one-to-one fashion, often by means of an involution operation: if the dual of A is B, then the dual of B is A. Such involutions sometimes have fixed points, so that the dual of A is A itself. For example, Desargues' theorem is self-dual in this sense under the standard duality in projective geometry.

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, infinite-dimensional holomorphy is a branch of functional analysis. It is concerned with generalizations of the concept of holomorphic function to functions defined and taking values in complex Banach spaces, typically of infinite dimension. It is one aspect of nonlinear functional analysis.

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

Quasi-isometry

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.

Hilbert space Generalization of Euclidean space allowing infinite dimensions

In mathematics, a Hilbert space generalizes the notion of Euclidean space. It extends the methods of vector algebra and calculus from the two-dimensional Euclidean plane and three-dimensional space to spaces with any finite or infinite number of dimensions. A Hilbert space is a vector space equipped with an inner product operation, which allows lengths and angles to be defined. Furthermore, Hilbert spaces are complete, which means that there are enough limits in the space to allow the techniques of calculus to be used.

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

In mathematics, particularly in functional analysis, a webbed space is a topological vector space designed with the goal of allowing the results of the open mapping theorem and the closed graph theorem to hold for a wider class of linear maps whose codomains are webbed spaces. A space is called webbed if there exists a collection of sets, called a web that satisfies certain properties. Webs were first investigated by de Wilde.

In mathematics, particularly in functional analysis and topology, the closed graph theorem is a fundamental result stating that a linear operator with a closed graph will, under certain conditions, be continuous. The original result has been generalized many times so there are now many theorems referred to as "closed graph theorems."

References

  1. 1 2 Kakutani, Shizuo (1941). "A generalization of Brouwer's fixed point theorem". Duke Mathematical Journal. 8 (3): 457–459. doi:10.1215/S0012-7094-41-00838-4.
  2. 1 2 Nash, J.F., Jr. (1950). "Equilibrium Points in N-Person Games". Proc. Natl. Acad. Sci. U.S.A. 36 (1): 48–49. Bibcode:1950PNAS...36...48N. doi: 10.1073/pnas.36.1.48 . PMC   1063129 . PMID   16588946.
  3. Border, Kim C. (1989). Fixed Point Theorems with Applications to Economics and Game Theory. Cambridge University Press. ISBN   0-521-38808-2.
  4. Osborne, Martin J.; Rubinstein, Ariel (1994). A Course in Game Theory. Cambridge, MA: MIT.
  5. 1 2 Aliprantis, Charlambos; Kim C. Border (1999). "Chapter 17". Infinite Dimensional Analysis: A Hitchhiker's Guide (3rd ed.). Springer.
  6. Starr, Ross M. (1997). General Equilibrium Theory. Cambridge University Press. ISBN   978-0-521-56473-1.
  7. McKenzie, Lionel (1954). "On Equilibrium in Graham's Model of World Trade and Other Competitive Systems". Econometrica . 22 (2): 147–161. doi:10.2307/1907539. JSTOR   1907539.
  8. 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.
  9. Fan, Ky (1952). "Fixed-point and Minimax Theorems in Locally Convex Topological Linear Spaces". Proc Natl Acad Sci U S A. 38 (2): 121–126. Bibcode:1952PNAS...38..121F. doi: 10.1073/pnas.38.2.121 . PMC   1063516 . PMID   16589065.
  10. 1 2 3 Dugundji, James; Andrzej Granas (2003). "Chapter II, Section 5.8". Fixed Point Theory (limited preview). Springer. ISBN   978-0-387-00173-9.
  11. Binmore, Ken (2007). "When Do Nash Equilibria Exist?". Playing for Real: A Text on Game Theory (1st ed.). Oxford University Press. p. 256. ISBN   978-0-19-804114-6.

Further reading