Kakutani fixed-point theorem: Difference between revisions

Revision as of 06:32, 18 September 2019

Latest revision as of 07:50, 19 August 2025

(42 intermediate revisions by 29 users not shown)

Line 1:

{{Short description|Fixed-point theorem for set-valued functions}}

In [[mathematical analysis]], the '''Kakutani fixed-point theorem''' is a [[fixed-point theorem]] for [[set-valued function]]s. It provides [[sufficient condition]]s for a set-valued function defined on a [[convex set|convex]], [[compact set|compact]] subset of a [[Euclidean space]] to have a [[fixed point (mathematics)|fixed point]], i.e. a point which is [[map (mathematics)|map]]ped 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 function (topology)|continuous function]]s 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,<ref name="kakutani">

Line 5 ⟶ 6:

| last = Kakutani

| first = Shizuo

| authorlinkauthor-link = Shizuo Kakutani

| title = A generalization of Brouwer’sBrouwer's fixed point theorem

| journal = Duke Mathematical Journal

| volume = 8

Line 22 ⟶ 23:

==Statement==

Kakutani's theorem states:<ref name=Osborne>{{cite book |lastlast1=Osborne |firstfirst1=Martin J. |author2linkauthor2-link=Ariel Rubinstein |first2=Ariel |last2=Rubinstein |title=A Course in Game Theory |___location=Cambridge, MA |publisher=MIT |year=1994 |pages= |isbn= }}</ref>

: ''Let'' ''S'' ''be a [[empty set|non-empty]], [[compact set|compact]] and [[convex set|convex]] [[subset]] of some [[Euclidean space]]'' '''R'''^''n''.
:''Let'' ''φ'':&nbsp;''S''&nbsp;→&nbsp;2^''S'' ''be a [[set-valued function]] on'' ''S'' ''with the following properties:''
:* ''φ has ''a [[closed graph]] and the property that;''
:* ''φ''(''x'') ''is non-empty and convex for all'' ''x''&nbsp;∈&nbsp;''S''.
:''Then'' ''φ'' ''has a [[fixed point (mathematics)|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 (mathematics)|function]] from ''X'' to the [[power set]] of ''Y'', written as ''φ'':&nbsp;''X''&nbsp;→&nbsp;2^''Y'', such that ''φ''(''x'') is non-empty for every <math>x \in X</math>. 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 φ:&nbsp;''X''&nbsp;→&nbsp;2^''Y'' is said to have a '''closed graph''' if the set {(''x'',''y'')&nbsp;|&nbsp;''y''&nbsp;∈&nbsp;''φ''(''x'')} is a [[closed set|closed]] subset of ''X''&nbsp;×&nbsp;''Y'' in the [[product topology]] i.e. for all sequences <math>\{x_n\}_{n\in \mathbb{N}}</math> and <math>\{y_n\}_{n\in \mathbb{N}}</math> such that <math>x_n\to x</math>, <math>y_{n}\to y</math> and <math>y_{n}\in \varphiphi(x_n)</math> for all <math>n</math>, we have <math>y\in \varphiphi(x)</math>.

;Fixed point: Let φ:&nbsp;''X''&nbsp;→&nbsp;2^''X'' be a set-valued function. Then ''a''&nbsp;∈&nbsp;''X'' is a '''fixed point''' of ''φ'' if ''a''&nbsp;∈&nbsp;''φ''(''a'').

==ExampleExamples==

[[File:Kakutani.svg|thumb|150px|Fixed points for ''φ''(x)=[1−''x''/2,&nbsp;1−''x''<nowiki>/4]</nowiki>]]

[[File:Kakutani.svg|thumb|150px|Fixed points for f(x)=<nowiki>[1−x/2,&nbsp;1−x/4]</nowiki>]]Let ''f''(''x'') be a set-valued function defined on the closed [[interval (mathematics)|interval]] [0,&nbsp;1] that maps a point ''x'' to the closed interval [1&nbsp;−&nbsp;''x''/2,&nbsp;1&nbsp;−&nbsp;''x''/4]. Then ''f''(''x'') satisfies all the assumptions of the theorem and must have fixed points.

=== A function with infinitely many 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''&nbsp;=&nbsp;0.72 (dashed line in blue) is a fixed point since 0.72&nbsp;∈&nbsp;[1&nbsp;−&nbsp;0.72/2,&nbsp;1&nbsp;−&nbsp;0.72/4].

{{clear}}<!--Stops image from floating past-->

The function: <math>

==Non-example==

\varphi(x)=

[1-x/2, ~1-x/4]

In</math>, shown on the diagramfigure 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''&nbsp;=&nbsp;0.72 (dashed line in blue) is a fixed point since 0.72&nbsp;∈&nbsp;[1&nbsp;−&nbsp;0.72/2,&nbsp;1&nbsp;−&nbsp;0.72/4].{{clear}}<!--Stops image from floating past-->

=== A function with a unique fixed point ===

The function:

:<math>

\varphi(x)=

\begin{cases}

3/4 & 0 \le x < 0.5 \\{}

[0,1] & x = 0.5 \\

1/4 & 0.5 < x \le 1

\end{cases}

</math>

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

[[File:Kakutani non.svg|thumb|150px|A function without fixed points]]The requirement that ''φ''(''x'') be convex for all ''x'' is essential for the theorem to hold.

Line 50 ⟶ 73:

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.

{{clear}}<!--Stops image from floating past-->

=== A function that does not satisfy closed graph ===

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

:<math>

\varphi(x)=

\begin{cases}

3/4 & 0 \le x < 0.5 \\

1/4 & 0.5 \le x \le 1

\end{cases}

</math>

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

==Alternative statement==

Line 64 ⟶ 100:

===Game theory===

{{See also|Game theory}}

The Kakutani fixed point theorem can be used to prove the [[Minimax#Minimax theorem|minimax theorem]] in the theory of [[zero-sum game]]s. This application was specifically discussed by Kakutani's original paper.<ref name="kakutani"/>

Mathematician [[John Forbes Nash|John Nash]] used the Kakutani fixed point theorem to prove a major result in [[game theory]].<ref name="nash">

{{cite journal

| last = Nash

| first = J.F., Jr.

| authorlinkauthor-link = John Forbes Nash

| title = Equilibrium Points in N-Person Games

| journal = Proc. Natl. Acad. Sci. U.S.A.

Line 79 ⟶ 115:

| pmid = 16588946

| issue = 1

| pmc = 1063129 }}</ref>| bibcode = 1950PNAS...36...48N

| doi-access = free

}}</ref> 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* thisThe case,base set ''S'' is the set of [[tuple]]s of [[mixed strategy|mixed strategies]] chosen by each player in a game. TheIf functioneach player has φ(''xk'') givespossible a new tupleactions, wherethen each player's strategy is hera best response to other players' strategies in 'k'x''. Since there may be a number-tuple of responsesprobabilities whichsumming areup equallyto good1, φso iseach set-valuedplayer's ratherstrategy thanspace single-valued. Thenis the [[Nashstandard equilibriumsimplex]] ofin the'''''R'''''^''k''''.'' game isThen, defined''S'' asis athe fixedcartesian pointproduct of φ,all these i.esimplices. aIt tupleis of strategies where each player's strategy isindeed a bestnonempty, responsecompact toand theconvex strategiessubset of the other players. Kakutani's theorem ensures that this fixed point exists''''R'''''^''kn''''.''

* The function φ(''x'') associates with each tuple 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. For each ''x'', φ(''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 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===

Line 90 ⟶ 129:

| last = Starr

| first = Ross M.

| authorlinkauthor-link = Ross Starr

| title = General Equilibrium Theory

| year = 1997

| publisher = Cambridge University Press

| url = https://books.google.com/books?id=Lv3VtS9CcAoC&pg

| isbn = 978-0-521-56473-1

}}</ref> The existence of such prices had been an open question in economics going back to at least [[Léon Walras|Walras]]. The first proof of this result was constructed by [[Lionel McKenzie]].<ref>{{cite journal |first=Lionel |last=McKenzie |title=On Equilibrium in Graham's Model of World Trade and Other Competitive Systems |journal=[[Econometrica]] |volume=22 |issue=2 |year=1954 |pages=147–161 |doi=10.2307/1907539 |jstor=1907539 }}</ref>

In this case:

In this case, ''S'' is the set of [[tuple]]s 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.

* The base set ''S'' is the set of [[tuple]]s of commodity prices.

In* thisThe case, ''S'' is the set of [[tuple]]s of commodity prices.function φ(''x'') is chosen asso athat function whoseits result is differentdiffers 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.

===Fair division===

{{See also|Fair cake-cutting}}

Kakutani's fixed-point theorem is used in proving the existence of cake allocations that are both [[envy-free cake-cutting|envy-free]] and [[Pareto efficient]]. This result is known as [[Weller's theorem]].

== Relation to Brouwer's fixed-point 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 [[Selection theorem|approximate selection theorem]]:<ref>{{Cite book |last=Shapiro |first=Joel H. |title=A Fixed-Point Farrago |date=2016 |publisher=Springer International Publishing |isbn=978-3-319-27978-7 |pages=68–70 |oclc=984777840}}</ref>

{{Math proof|proof=

By the approximate selection theorem, there exists a sequence of continuous <math>f_n: S \to S</math> such that <math>\operatorname{graph}(f_n) \subset[\operatorname{graph}(\varphi)]_{1/n}</math>. By Brouwer fixed-point theorem, there exists a sequence <math>x_n</math> such that <math>f_n(x_n) = x_n</math>, so <math>(x_n, x_n) \in [\operatorname{graph}(\varphi)]_{1/n}</math>.

Since <math>S</math> is compact, we can take a convergent subsequence <math>x_n \to x</math>. Then <math>(x, x)\in \operatorname{graph}(\varphi)</math> since it is a closed set.

}}

==Proof outline==

===''S'' = <nowiki>[0,1]</nowiki>===

The proof of Kakutani's theorem is simplest for set-valued functions defined over [[interval (mathematics)|closed intervals]] of the real line. HoweverMoreover, the proof of this case is instructive since its general strategy can be carried over to the higher-dimensional case as well.

Let φ: <nowiki>[0,1]</nowiki>→2^{<nowiki>[0,1]</nowiki>} be a [[set-valued function]] on the closed interval <nowiki>[0,1]</nowiki> which satisfies the conditions of Kakutani's fixed-point theorem.

* '''Create a sequence of subdivisions of <nowiki>[0,1]</nowiki> 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:

:{|class="wikitable"

|-

Line 146 ⟶ 198:

* '''Find a limiting point of the subdivisions.'''

TheWe 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, (''a''_''n'', ''p''_''n'', ''b''_''n'', ''q''_''n''). This lies in the [[cartesian product]] <nowiki>[0,1]</nowiki>×<nowiki>[0,1]</nowiki>×<nowiki>[0,1]</nowiki>×<nowiki>[0,1]</nowiki>, which is a [[compact set]] by [[Tychonoff's theorem]]. Since theour sequence (''a''_''n'', ''p''_''n'', ''b''_''n'', ''q''_''n'') lies in thisa compact set, it must have a [[limit of a sequence|convergent]] [[subsequence]] by the [[Bolzano-Weierstrass theorem|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 (''b''_''i'' − ''a''_''i'') ≤ 2^−''i'' by condition (2),

Line 172 ⟶ 224:

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

== Computation ==

Papadimitriou, Vlatakis-Gkaragkounis and Zampetakis<ref>{{cite arXiv | last1=Papadimitriou | first1=Christos H. | last2=Vlatakis-Gkaragkounis | first2=Emmanouil-Vasileios | last3=Zampetakis | first3=Manolis | title=The Computational Complexity of Multi-player Concave Games and Kakutani Fixed Points | date=2022 | class=cs.CC | eprint=2207.07557 }}</ref> prove that computing a Kakutani fixed-point theorem is [[PPAD-complete]].

==Infinite-dimensional generalizations==

Line 186 ⟶ 241:

| doi = 10.2307/2032478

| jstor = 2032478| url = http://www.dtic.mil/get-tr-doc/pdf?AD=AD0603907

| archive-url = https://web.archive.org/web/20170922175230/http://www.dtic.mil/get-tr-doc/pdf?AD=AD0603907

| archive-date = September 22, 2017

}}</ref>

and [[Ky Fan]].<ref>

Line 199 ⟶ 257:

| doi = 10.1073/pnas.38.2.121

| pmid = 16589065

| pmc = 1063516}}</ref>| bibcode = 1952PNAS...38..121F

| doi-access = free

}}</ref>

To state the theorem in this case, we need a few more definitions:

;Upper hemicontinuity: A set-valued function φ:&nbsp;''X''→2^''Y'' is '''[[upper hemicontinuous]]''' if for every [[open set]] ''W''&nbsp;⊂&nbsp;''Y'', the set {''x''|&nbsp;φ(''x'')&nbsp;⊂&nbsp;''W''} is open in ''X''.<ref name="dugundji">

Line 205 ⟶ 265:

| last = Dugundji

| first = James

| authorlinkauthor-link = James Dugundji

|author2=Andrzej Granas

| title = Fixed Point Theory

Line 211 ⟶ 271:

| publisher = Springer

| chapter = Chapter II, Section 5.8

| url = https://books.google.com/books?id=4_iJAoLSq3cC

| format = limited preview

| isbn = 978-0-387-00173-9

Line 232 ⟶ 292:

| edition = 3rd

| chapter = Chapter 17

| url =

}}</ref>

Line 238 ⟶ 297:

==Anecdote==

In his game theory textbook,<ref>{{cite book |last=Binmore |first=Ken |title=Playing for Real: A Text on Game Theory |year=2007 |publisher=Oxford University Press |edition=1st |chapter=When Do Nash Equilibria Exist? |page=256 |chapterurlisbn=978-0-19-804114-6 |chapter-url=https://books.google.com/books?id=NycDSDcmSM4C&pg=PA256 }}</ref> [[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?"

==References==

Line 247 ⟶ 306:

| last = Border

| first = Kim C.

| author-link = Kim Border

| title = Fixed Point Theorems with Applications to Economics and Game Theory

| year = 1989

Line 254 ⟶ 314:

| last = Dugundji

| first = James

| authorlinkauthor-link = James Dugundji

|author2=Andrzej Granas

| title = Fixed Point Theory

Line 263 ⟶ 323:

| last = Arrow

| first = Kenneth J.

| authorlinkauthor-link = Kenneth Arrow

|author2=F. H. Hahn

| title = General Competitive Analysis

| url = https://archive.org/details/generalcompetiti0000arro

| url-access = registration

| year = 1971

| publisher = Holden-Day

| isbn = 978-0-8162-0275-1

}} <small>(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.)</small>

==External links==

* {{springer|title=Kakutani theorem|id=p/k055090}}