角谷不動點定理

在數學分析中，角谷不動點定理是一個適用於集值函數的不動點定理。它為在定義在歐幾里德空間中的緊凸集上的集值函數提供具有不動點的充分條件，也即一個可以映射到包含自身的集合的點。角谷不動點定理是布勞威爾不動點定理的泛化。布勞威爾不動點定理是拓撲學的基礎定理，它證明了定義在歐幾里得空間的緊緻，凸子集上的連續函數具有不動點。角谷靜夫將此定理泛化到了集值函數。

此定理1941年由角谷靜夫提出^[1]，曾被納什用於描述納什均衡^[2]。之後，此定理在博弈論和經濟學中得到了廣泛應用^[3]。

敘述

角谷不動點定理的敘述如下^[4]

令${\displaystyle S}$為歐幾里得空間 ${\displaystyle \mathbf {R} ^{n}}$中的非空緊凸集，令${\displaystyle \varphi :S\to 2^{S}}$為${\displaystyle S}$上的一個具有下列特徵的集值函數：

• ${\displaystyle \varphi }$ 有閉圖；

• 對於任意${\displaystyle x\in S,\varphi (x)}$ 為非空凸集。

則${\displaystyle \varphi }$ 具有不動點。

定義

集值函數

集值函數是一個從${\displaystyle X}$映到${\displaystyle Y}$的冪集的函數${\displaystyle \varphi :X\to 2^{Y}}$，使任意${\displaystyle x\in X,\varphi (x)}$都為非空集。這類函數有時也被稱為對應，即函數的每個輸入都將返回多個輸出。因此，每個定義域的元素都對應一個由一個或多個值域元素構成的子集。

閉圖

一個集值函數${\displaystyle \varphi :X\to 2^{Y}}$有閉圖，如果集合${\displaystyle \{(x,y)|y\in \varphi (x)\}}$在積空間${\displaystyle X\times Y}$中是一個閉子集。即：給定任意序列${\displaystyle \{x_{n}\}_{n\in \mathbb {N} }}$和${\displaystyle \{y_{n}\}_{n\in \mathbb {N} }}$，並滿足${\displaystyle x_{n}\to x,y_{n}\to y,y_{n}\in \varphi (x_{n})}$，則有${\displaystyle y\in \varphi (x)}$。

不動點

令${\displaystyle \varphi :X\to 2^{X}}$為一個集值函數。如果${\displaystyle a\in \varphi (a),a\in X}$，則${\displaystyle a}$為一個不動點。

舉例

有無窮多個不動點的函數

例如：函數${\displaystyle \varphi (x)=[1-X/2,1-X/4]}$滿足所有角谷不動點定理的條件，並存在無窮多個不動點。

有一個不動點的函數

例如：一個函數${\displaystyle \varphi (x)={\begin{cases}3/4&0\leq x<0.5\\(0,1)&x=0.5\\1/4&0.5<x\leq 1\end{cases}}}$

滿足所有角谷不動點定理的條件，並存在唯一一個不動點${\displaystyle x=0.5}$。

不滿足凸集的函數

例如：一個函數${\displaystyle \varphi (x)={\begin{cases}3/4&0\leq x<0.5\\\{3/4,1/4\}&x=0.5\\1/4&0.5<x\leq 1\end{cases}}}$

在${\displaystyle x=0.5}$處不滿足凸集定義，但滿足其他角谷不動點定理的條件。這個函數沒有不動點。

不滿足閉合圖的函數

例如：一個函數${\displaystyle \varphi (x)={\begin{cases}3/4&0\leq x<0.5\\1/4&0.5\leq x\leq 1\end{cases}}}$

不存在不動點，因為函數不滿足閉合圖。考慮序列${\displaystyle x_{n}=0.5-1/n}$和${\displaystyle y_{n}=3/4}$：當${\displaystyle x_{n}\to x=0.5,y_{n}\to y=3/4,y\notin \varphi (x)}$。

其他敘述方式

角谷靜夫的原始論文使用了上半連續性的概念敘述此定理：

令S為歐幾里得空間${\displaystyle \mathbf {R} ^{n}}$上的一個非空，緊緻，凸集的子集。令${\displaystyle \varphi :S\to 2^{S}}$為上半連續的集值函數，且${\displaystyle \varphi (x)}$在所有${\displaystyle x\in S}$上非空，閉合，且為凸。則函數${\displaystyle \varphi }$有不動點。

這一敘述與之前的敘述完全等價。

我們可以通過集值函數的閉圖像定理來說明這種等價關係：對緊緻的豪斯多夫空間${\displaystyle Y}$，一個集值函數${\displaystyle \varphi :X\to 2^{Y}}$有閉合圖的充分必要條件是：${\displaystyle \varphi }$是上半連續的，且對所有${\displaystyle x}$,${\displaystyle \varphi }$是閉集。因為所有歐幾里得空間都為豪斯多夫空間，且${\displaystyle \varphi }$在這種敘述方式中必須為封閉值，所以根據閉圖像定理，兩種敘述方式等價。

應用

參見：數理經濟學

博弈論

參見：博弈論

角谷不動點定理可以用來證明零和博弈中的極小化極大算法。

納什利用角谷不動點定理證明了博弈論中的一個重要結論。這一定理暗示，在任何混合策略的多人有限遊戲中都必定存在納什均衡。納什的貢獻使他獲得了諾貝爾經濟學獎。

• 基本集S是博弈中各個參與者選擇的混合策略的多元組集合。假設每個參與者有k種可能的行為，那麼每個參與者的策略就是一個相加之和為1的k元概率，也即每個參與者的策略空間是${\displaystyle \mathbf {R} ^{k}}$空間中的單純形。而S是所有這些單純形的笛卡兒積，並且S是一個非空，緊緻和凸型的${\displaystyle \mathbf {R} ^{kn}}$的子集。
• 函數${\displaystyle \varphi (x)}$將每個多元組都與另一個多元組聯繫起來，即每個參與者的策略都是她對於其他參與者策略的最佳應對。由於最佳應對可以不唯一，${\displaystyle \varphi (x)}$是一個集值函數。對任意x，${\displaystyle \varphi (x)}$都是非空的，因為一定存在至少一個最佳應對策略。${\displaystyle \varphi (x)}$也是凸的，因為任意兩個最佳應對的組合仍然是最佳應對。${\displaystyle \varphi (x)}$也可以被證明是閉合圖。
• 納什均衡被定義為${\displaystyle \varphi (x)}$的不動點，即：策略多元組集合中，每個參與者的策略都是其他參與者策略的最佳應對。角谷不動點定理保證了不動點的存在。

證明框架

S是單維區間的情況

角谷不動點定理的證明對於定義在閉區間上的實數集值函數最為簡單。假設${\displaystyle S=[0,1]}$。假設${\displaystyle \varphi :[0,1]\to 2^{[0,1]}}$為在閉區間[0,1]上的集值函數，且滿足角谷不動點定理的條件。

• 創建一個序列，使序列處於[0,1]的具有相鄰點的子區間中，並向相反方向移動。

令${\displaystyle (a_{i},b_{i},p_{i},q_{i}),i=0,1,\cdots }$為一個具有下列特點的序列：

1	${\displaystyle 1\geq b_{i}>a_{i}\geq 0}$	2	${\displaystyle (b_{i}-a_{i})\leq 2^{-i}}$
3	${\displaystyle p_{i}\in \varphi (a_{i})}$	4	${\displaystyle q_{i}\in \varphi (b_{i})}$
5	${\displaystyle p_{i}\geq a_{i}}$	6	${\displaystyle q_{i}\leq b_{i}}$

閉集${\displaystyle [a_{i},b_{i}]}$形成了一個由${\displaystyle [0,1]}$的子區間組成的序列。條件2使這些子區間的範圍逐漸減小，而條件3-6讓${\displaystyle \varphi }$令子區間的邊界向相反方向移動。

這樣一個序列可以按如下方式構建：

令${\displaystyle a_{0}=0,b_{0}=1}$。令${\displaystyle p_{0},q_{0}}$分別為${\displaystyle \varphi (0),\varphi (1)}$上的任一點。

假設我們已經選取了序列的第k個元素為${\displaystyle (a_{k},b_{k},p_{k},q_{k})}$且滿足以上6個條件。令：${\displaystyle m=(a_{k}+b_{k})/2}$。一定有${\displaystyle m\in [0,1]}$，因為${\displaystyle [0,1]}$是凸集。

如果存在${\displaystyle r\in \varphi (m)}$並且有${\displaystyle r\geq m}$，我們可以選取：

 ${\displaystyle a_{k+1}=m}$
 ${\displaystyle b_{k+1}=b_{k}}$
 ${\displaystyle p_{k+1}=r}$
 ${\displaystyle q_{k+1}=q_{k}}$

否則，必定存在${\displaystyle s\in \varphi (m)}$使得${\displaystyle s\leq m}$。我們選取：

 ${\displaystyle a_{k+1}=a_{k}}$
 ${\displaystyle b_{k+1}=m}$
 ${\displaystyle p_{k+1}=p_{k}}$
 ${\displaystyle q_{k+1}=s}$

• 尋找子區間的極限值。

根據吉洪諾夫定理，緊緻集合的笛卡兒積${\displaystyle [0,1]\times [0,1]\times [0,1]\times [0,1]}$也是緊緻的。由於序列${\displaystyle (a_{n},b_{n},p_{n},q_{n})}$在這個集合里，所以根據波爾查諾-魏爾斯特拉斯定理，這個序列一定存在收斂的子序列。假設這個收斂子序列的極限是${\displaystyle (a^{*},b^{*},p^{*},q^{*})}$。由於${\displaystyle \varphi }$是閉合圖，一定有：

 ${\displaystyle p^{*}\in \varphi (a^{*})}$
 ${\displaystyle q^{*}\in \varphi (b^{*})}$
 ${\displaystyle p^{*}\geq a^{*}}$
 ${\displaystyle q^{*}\leq b^{*}}$

由於條件2，有${\displaystyle (b_{i}-a_{i})\leq 2^{-i}}$，所以：

${\displaystyle b^{*}-a^{*}=\lim(b_{n}-a_{n})=0}$

有：${\displaystyle a^{*}=b^{*}=x}$，且 ${\displaystyle \varphi (x)\ni q^{*}\leq x\leq p^{*}\in \varphi (x)}$。

• 證明子區間的極限值為不動點

如果${\displaystyle p^{*}=q^{*}}$，則有${\displaystyle p^{*}=x=q^{*}}$。因為 ${\displaystyle p^{*}\in \varphi (x)}$，所以x是${\displaystyle \varphi }$的一個不動點。

如果${\displaystyle p^{*}\neq q^{*}}$，則構造一條p^*與q^*間的直線：

${\displaystyle x=({\cfrac {x-q^{*}}{p^{*}-q^{*}}})p^{*}+(1-{\cfrac {x-q^{*}}{p^{*}-q^{*}}})q^{*}}$

由於${\displaystyle \varphi (x)}$是凸集，所以由${\displaystyle p^{*}\in \varphi (x),q^{*}\in \varphi (x)}$可以推導出${\displaystyle x\in \varphi (x)}$。所以x是${\displaystyle \varphi (x)}$的一個不動點。

S是n維單純形的情況

當S的維度大於1時，最簡單的情況是n維單純形。n維單純形相當於一個高維的三角形。證明單純形的角谷不動點定理與區間上的證明極其相似。複雜度僅在於證明的第一步：如何切割空間為子空間。

• 類似於一維的情況，我們使用重心細分方法將單純形切割為子單純形
• 為確保子單純形序列的邊界向相反方向運動，需要用到斯佩納引理以保證子單純形的存在。

任意S的情況

對n維單純形的證明可以用來證明任意緊緻，凸型S情況下的角谷不動點定理。單純形在這種情況下不再有直線的邊界，而是有曲線邊界。這會用到形變收縮。

無窮維度的泛化

角谷不動點定理可以泛化為無窮維度局部凸拓撲向量空間^[5][6]。

上半連續性定義：

一個集值函數${\displaystyle \varphi :X\to 2^{Y}}$是上半連續的，如果對於任何開集${\displaystyle W\in Y}$，集合${\displaystyle \{x|\varphi (x)\subset W\}}$也是X上的開集^[7]。

角谷映射定義：

令X,Y為拓撲向量空間，${\displaystyle \varphi :X\to 2^{Y}}$為集值函數。如果Y為凸，且${\displaystyle \varphi :X\to 2^{Y}}$對所有${\displaystyle x\in X}$都是上半連續的，非空，緊緻的凸集，則${\displaystyle \varphi :X\to 2^{Y}}$稱為角谷映射。

角谷-格里科斯伯格-樊定理的敘述為：

令S為豪斯多夫局部凸拓撲向量空間的非空，緊緻凸子集。令${\displaystyle \varphi :S\to 2^{S}}$為角谷映射。則${\displaystyle \varphi }$存在不動點。

對應的單值函數定理是吉洪諾夫不動點定理。

參考資料

1. Kakutani, Shizuo. A generalization of Brouwer's fixed point theorem. Duke Mathematical Journal. 1941, 8 (3): 457–459. doi:10.1215/S0012-7094-41-00838-4.
2. Nash, J.F., Jr. Equilibrium Points in N-Person Games. Proc. Natl. Acad. Sci. U.S.A. 1950, 36 (1): 48–49. PMID 16588946. doi:10.1073/pnas.36.1.48.
3. Border, Kim C. Fixed Point Theorems with Applications to Economics and Game Theory. Cambridge University Press. 1989. ISBN 0-521-38808-2.
4. Osborne, Martin J.; Rubinstein, Ariel. A Course in Game Theory. Cambridge, MA: MIT. 1994. 引文使用過時參數coauthors (幫助)
5. Glicksberg, I.L. A Further Generalization of the Kakutani Fixed Point Theorem, with Application to Nash Equilibrium. Proceedings of the American Mathematical Society. 1952, 3 (1): 170–174. doi:10.2307/2032478.
6. Fan, Ky. Fixed-point and Minimax Theorems in Locally Convex Topological Linear Spaces. Proc Natl Acad Sci U S A. 1952, 38 (2): 121–126. doi:10.1073/pnas.38.2.121.
7. Dugundji, James; Andrzej Granas. Fixed Point Theory. Springer. 2003: Chapter II, Section 5.8. ISBN 978-0-387-00173-9. 引文使用過時參數coauthors (幫助)