Content deleted Content added
Telugubanti (talk | contribs) m fixed typos |
Citation bot (talk | contribs) Altered template type. Add: eprint, class, date, title, authors 1-3. Changed bare reference to CS1/2. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Headbomb | #UCB_toolbar |
||
| (3 intermediate revisions by 3 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 ''φ'': ''X'' → 2<sup>''Y''</sup>, 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 φ: ''X'' → 2<sup>''Y''</sup> is said to have a '''closed graph''' if the set {(''x'',''y'') | ''y'' ∈ ''φ''(''x'')} is a [[closed set|closed]] subset of ''X'' × ''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
;Fixed point: Let φ: ''X'' → 2<sup>''X''</sup> be a set-valued function. Then ''a'' ∈ ''X'' is a '''fixed point''' of ''φ'' if ''a'' ∈ ''φ''(''a'').
Line 164:
* '''Create a sequence of subdivisions of <nowiki>[0,1]</nowiki> with adjacent points moving in opposite directions.'''
Let (''a''<sub>''i''</sub>, ''b''<sub>''i''</sub>, ''p''<sub>''i''</sub>, ''q''<sub>''i''</sub>) for ''i'' = 0, 1,
:{|class="wikitable"
|-
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==
| |||