Kakutani fixed-point theorem: Difference between revisions

Revision as of 13:07, 19 December 2023

Latest revision as of 07:50, 19 August 2025

(12 intermediate revisions by 10 users not shown)

Line 32:

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

Line 48:

The function:

:<math>

\varphi(x)=

\begin{cases}

Line 147:

== Relation to Brouwer's fixed-point theorem ==

{{Disputed section|Mistake in section "[[Kakutani_fixed-point_theorem#Relation_to_Brouwer's_fixed-point_theorem|Relation to Brouwer's fixed-point theorem]]"|date=December 2023}}

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{{dubious}}, 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.

Line 159:

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