在數學分析 中，角谷不動點定理 是一個適用於集值函數的不動點定理 。它為在定義在歐幾里德空間中的緊 凸 集上的集值函數提供具有不動點 的充分條件 ，也即一個可以映射到包含自身的集合的點。角谷不動點定理是布勞威爾不動點定理 的泛化。布勞威爾不動點定理是拓撲學 的基礎定理，它證明了定義在歐幾里得空間 的緊緻，凸子集上的連續函數 具有不動點。角谷靜夫將此定理泛化到了集值函數。
此定理1941年由角谷靜夫提出[ 1] 納什 用於描述納什均衡 [ 2] 博弈論 和經濟學 中得到了廣泛應用[ 3]
角谷不動點定理的敘述如下[ 4]
令
S
{\displaystyle S}
R
n
{\displaystyle \mathbf {R} ^{n}}
非空 緊凸集，令
φ
:
S
→
2
S
{\displaystyle \varphi :S\to 2^{S}}
S
{\displaystyle S}
φ
{\displaystyle \varphi }
對於任意
x
∈
S
,
φ
(
x
)
{\displaystyle x\in S,\varphi (x)}
非空 凸集。 則
φ
{\displaystyle \varphi }
集值函數
集值函數是一個從
X
{\displaystyle X}
Y
{\displaystyle Y}
冪集 的函數
φ
:
X
→
2
Y
{\displaystyle \varphi :X\to 2^{Y}}
x
∈
X
,
φ
(
x
)
{\displaystyle x\in X,\varphi (x)}
對應 ，即函數的每個輸入都將返回多個輸出。因此，每個定義域 的元素都對應一個由一個或多個值域 元素構成的子集。
閉圖
一個集值函數
φ
:
X
→
2
Y
{\displaystyle \varphi :X\to 2^{Y}}
{
(
x
,
y
)
|
y
∈
φ
(
x
)
}
{\displaystyle \{(x,y)|y\in \varphi (x)\}}
積空間
X
×
Y
{\displaystyle X\times Y}
閉 子集。即：給定任意序列
{
x
n
}
n
∈
N
{\displaystyle \{x_{n}\}_{n\in \mathbb {N} }}
{
y
n
}
n
∈
N
{\displaystyle \{y_{n}\}_{n\in \mathbb {N} }}
x
n
→
x
,
y
n
→
y
,
y
n
∈
φ
(
x
n
)
{\displaystyle x_{n}\to x,y_{n}\to y,y_{n}\in \varphi (x_{n})}
y
∈
φ
(
x
)
{\displaystyle y\in \varphi (x)}
不動點
令
φ
:
X
→
2
X
{\displaystyle \varphi :X\to 2^{X}}
a
∈
φ
(
a
)
,
a
∈
X
{\displaystyle a\in \varphi (a),a\in X}
a
{\displaystyle a}
例如：函數
φ
(
x
)
=
[
1
−
X
/
2
,
1
−
X
/
4
]
{\displaystyle \varphi (x)=[1-X/2,1-X/4]}
例如：一個函數
φ
(
x
)
=
{
3
/
4
0
≤
x
<
0.5
(
0
,
1
)
x
=
0.5
1
/
4
0.5
<
x
≤
1
{\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}}}
滿足所有角谷不動點定理的條件，並存在唯一一個不動點
x
=
0.5
{\displaystyle x=0.5}
例如：一個函數
φ
(
x
)
=
{
3
/
4
0
≤
x
<
0.5
{
3
/
4
,
1
/
4
}
x
=
0.5
1
/
4
0.5
<
x
≤
1
{\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}}}
在
x
=
0.5
{\displaystyle x=0.5}
例如：一個函數
φ
(
x
)
=
{
3
/
4
0
≤
x
<
0.5
1
/
4
0.5
≤
x
≤
1
{\displaystyle \varphi (x)={\begin{cases}3/4&0\leq x<0.5\\1/4&0.5\leq x\leq 1\end{cases}}}
不存在不動點，因為函數不滿足閉合圖。考慮序列
x
n
=
0.5
−
1
/
n
{\displaystyle x_{n}=0.5-1/n}
y
n
=
3
/
4
{\displaystyle y_{n}=3/4}
x
n
→
x
=
0.5
,
y
n
→
y
=
3
/
4
,
y
∉
φ
(
x
)
{\displaystyle x_{n}\to x=0.5,y_{n}\to y=3/4,y\notin \varphi (x)}
角谷靜夫的原始論文使用了上半連續性 的概念敘述此定理：
令S 為歐幾里得空間
R
n
{\displaystyle \mathbf {R} ^{n}}
φ
:
S
→
2
S
{\displaystyle \varphi :S\to 2^{S}}
φ
(
x
)
{\displaystyle \varphi (x)}
x
∈
S
{\displaystyle x\in S}
φ
{\displaystyle \varphi }
這一敘述與之前的敘述完全等價。
我們可以通過集值函數的閉圖像定理 來說明這種等價關係：對緊緻的豪斯多夫空間
Y
{\displaystyle Y}
φ
:
X
→
2
Y
{\displaystyle \varphi :X\to 2^{Y}}
φ
{\displaystyle \varphi }
x
{\displaystyle x}
φ
{\displaystyle \varphi }
φ
{\displaystyle \varphi }
角谷不動點定理可以用來證明零和博弈 中的極小化極大算法 。
納什 利用角谷不動點定理證明了博弈論中的一個重要結論。這一定理暗示，在任何混合策略 的多人有限遊戲中都必定存在納什均衡 。納什的貢獻使他獲得了諾貝爾經濟學獎 。
基本集S 是博弈中各個參與者選擇的混合策略的多元組 集合。假設每個參與者有k 種可能的行為，那麼每個參與者的策略就是一個相加之和為1的k 元概率，也即每個參與者的策略空間是
R
k
{\displaystyle \mathbf {R} ^{k}}
單純形 。而S 是所有這些單純形的笛卡兒積 ，並且S 是一個非空，緊緻和凸型的
R
k
n
{\displaystyle \mathbf {R} ^{kn}}
函數
φ
(
x
)
{\displaystyle \varphi (x)}
最佳應對 。由於最佳應對可以不唯一，
φ
(
x
)
{\displaystyle \varphi (x)}
x ，
φ
(
x
)
{\displaystyle \varphi (x)}
φ
(
x
)
{\displaystyle \varphi (x)}
φ
(
x
)
{\displaystyle \varphi (x)}
納什均衡 被定義為
φ
(
x
)
{\displaystyle \varphi (x)}
角谷不動點定理的證明對於定義在閉區間 上的實數集值函數最為簡單。假設
S
=
[
0
,
1
]
{\displaystyle S=[0,1]}
φ
:
[
0
,
1
]
→
2
[
0
,
1
]
{\displaystyle \varphi :[0,1]\to 2^{[0,1]}}
創建一個序列，使序列處於[0,1]的具有相鄰點的子區間中，並向相反方向移動 。令
(
a
i
,
b
i
,
p
i
,
q
i
)
,
i
=
0
,
1
,
⋯
{\displaystyle (a_{i},b_{i},p_{i},q_{i}),i=0,1,\cdots }
1
1
≥
b
i
>
a
i
≥
0
{\displaystyle 1\geq b_{i}>a_{i}\geq 0}
2
(
b
i
−
a
i
)
≤
2
−
i
{\displaystyle (b_{i}-a_{i})\leq 2^{-i}}
3
p
i
∈
φ
(
a
i
)
{\displaystyle p_{i}\in \varphi (a_{i})}
4
q
i
∈
φ
(
b
i
)
{\displaystyle q_{i}\in \varphi (b_{i})}
5
p
i
≥
a
i
{\displaystyle p_{i}\geq a_{i}}
6
q
i
≤
b
i
{\displaystyle q_{i}\leq b_{i}}
閉集
[
a
i
,
b
i
]
{\displaystyle [a_{i},b_{i}]}
[
0
,
1
]
{\displaystyle [0,1]}
2 使這些子區間的範圍逐漸減小，而條件3-6 讓
φ
{\displaystyle \varphi }
這樣一個序列可以按如下方式構建：
令
a
0
=
0
,
b
0
=
1
{\displaystyle a_{0}=0,b_{0}=1}
p
0
,
q
0
{\displaystyle p_{0},q_{0}}
φ
(
0
)
,
φ
(
1
)
{\displaystyle \varphi (0),\varphi (1)}
假設我們已經選取了序列的第k 個元素為
(
a
k
,
b
k
,
p
k
,
q
k
)
{\displaystyle (a_{k},b_{k},p_{k},q_{k})}
m
=
(
a
k
+
b
k
)
/
2
{\displaystyle m=(a_{k}+b_{k})/2}
m
∈
[
0
,
1
]
{\displaystyle m\in [0,1]}
[
0
,
1
]
{\displaystyle [0,1]}
如果存在
r
∈
φ
(
m
)
{\displaystyle r\in \varphi (m)}
r
≥
m
{\displaystyle r\geq m}
a
k
+
1
=
m
{\displaystyle a_{k+1}=m}
b
k
+
1
=
b
k
{\displaystyle b_{k+1}=b_{k}}
p
k
+
1
=
r
{\displaystyle p_{k+1}=r}
q
k
+
1
=
q
k
{\displaystyle q_{k+1}=q_{k}}
否則，必定存在
s
∈
φ
(
m
)
{\displaystyle s\in \varphi (m)}
s
≤
m
{\displaystyle s\leq m}
a
k
+
1
=
a
k
{\displaystyle a_{k+1}=a_{k}}
b
k
+
1
=
m
{\displaystyle b_{k+1}=m}
p
k
+
1
=
p
k
{\displaystyle p_{k+1}=p_{k}}
q
k
+
1
=
s
{\displaystyle q_{k+1}=s}
根據吉洪諾夫定理 ，緊緻集合的笛卡兒積
[
0
,
1
]
×
[
0
,
1
]
×
[
0
,
1
]
×
[
0
,
1
]
{\displaystyle [0,1]\times [0,1]\times [0,1]\times [0,1]}
(
a
n
,
b
n
,
p
n
,
q
n
)
{\displaystyle (a_{n},b_{n},p_{n},q_{n})}
波爾查諾-魏爾斯特拉斯定理 ，這個序列一定存在收斂的子序列 。假設這個收斂子序列的極限是
(
a
∗
,
b
∗
,
p
∗
,
q
∗
)
{\displaystyle (a^{*},b^{*},p^{*},q^{*})}
φ
{\displaystyle \varphi }
p
∗
∈
φ
(
a
∗
)
{\displaystyle p^{*}\in \varphi (a^{*})}
q
∗
∈
φ
(
b
∗
)
{\displaystyle q^{*}\in \varphi (b^{*})}
p
∗
≥
a
∗
{\displaystyle p^{*}\geq a^{*}}
q
∗
≤
b
∗
{\displaystyle q^{*}\leq b^{*}}
由於條件2 ，有
(
b
i
−
a
i
)
≤
2
−
i
{\displaystyle (b_{i}-a_{i})\leq 2^{-i}}
b
∗
−
a
∗
=
lim
(
b
n
−
a
n
)
=
0
{\displaystyle b^{*}-a^{*}=\lim(b_{n}-a_{n})=0}
有：
a
∗
=
b
∗
=
x
{\displaystyle a^{*}=b^{*}=x}
φ
(
x
)
∋
q
∗
≤
x
≤
p
∗
∈
φ
(
x
)
{\displaystyle \varphi (x)\ni q^{*}\leq x\leq p^{*}\in \varphi (x)}
如果
p
∗
=
q
∗
{\displaystyle p^{*}=q^{*}}
p
∗
=
x
=
q
∗
{\displaystyle p^{*}=x=q^{*}}
p
∗
∈
φ
(
x
)
{\displaystyle p^{*}\in \varphi (x)}
x 是
φ
{\displaystyle \varphi }
如果
p
∗
≠
q
∗
{\displaystyle p^{*}\neq q^{*}}
p^* 與q^* 間的直線：
x
=
(
x
−
q
∗
p
∗
−
q
∗
)
p
∗
+
(
1
−
x
−
q
∗
p
∗
−
q
∗
)
q
∗
{\displaystyle x=({\cfrac {x-q^{*}}{p^{*}-q^{*}}})p^{*}+(1-{\cfrac {x-q^{*}}{p^{*}-q^{*}}})q^{*}}
由於
φ
(
x
)
{\displaystyle \varphi (x)}
p
∗
∈
φ
(
x
)
,
q
∗
∈
φ
(
x
)
{\displaystyle p^{*}\in \varphi (x),q^{*}\in \varphi (x)}
x
∈
φ
(
x
)
{\displaystyle x\in \varphi (x)}
x 是
φ
(
x
)
{\displaystyle \varphi (x)}
當S 的維度大於1時，最簡單的情況是n維單純形 。n維單純形相當於一個高維的三角形。證明單純形的角谷不動點定理與區間上的證明極其相似。複雜度僅在於證明的第一步：如何切割空間為子空間。
類似於一維的情況，我們使用重心細分 方法將單純形切割為子單純形
為確保子單純形序列的邊界向相反方向運動，需要用到斯佩納引理 以保證子單純形的存在。 對n維單純形的證明可以用來證明任意緊緻，凸型S 情況下的角谷不動點定理。單純形在這種情況下不再有直線的邊界，而是有曲線邊界。這會用到形變收縮 。
角谷不動點定理可以泛化為無窮維度局部凸拓撲向量空間 [ 5] [ 6]
上半連續性 定義：
一個集值函數
φ
:
X
→
2
Y
{\displaystyle \varphi :X\to 2^{Y}}
開集
W
∈
Y
{\displaystyle W\in Y}
{
x
|
φ
(
x
)
⊂
W
}
{\displaystyle \{x|\varphi (x)\subset W\}}
X 上的開集[ 7]
角谷映射 定義：
令X,Y 為拓撲向量空間 ，
φ
:
X
→
2
Y
{\displaystyle \varphi :X\to 2^{Y}}
Y 為凸，且
φ
:
X
→
2
Y
{\displaystyle \varphi :X\to 2^{Y}}
x
∈
X
{\displaystyle x\in X}
φ
:
X
→
2
Y
{\displaystyle \varphi :X\to 2^{Y}}
角谷-格里科斯伯格-樊定理的敘述為：
令S 為豪斯多夫 局部凸拓撲向量空間 的非空，緊緻凸子集。令
φ
:
S
→
2
S
{\displaystyle \varphi :S\to 2^{S}}
φ
{\displaystyle \varphi }
對應的單值函數定理是吉洪諾夫不動點定理 。
^ 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 ^ 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 ^ Border, Kim C. Fixed Point Theorems with Applications to Economics and Game Theory. Cambridge University Press. 1989. ISBN 0-521-38808-2 ^ Osborne, Martin J.; Rubinstein, Ariel. A Course in Game Theory. Cambridge, MA: MIT. 1994. ^ 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 ^ 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 ^ Dugundji, James; Andrzej Granas. Fixed Point Theory. Springer. 2003: Chapter II, Section 5.8. ISBN 978-0-387-00173-9
![{\displaystyle \varphi (x)=[1-X/2,1-X/4]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/572b360715eebcf367fcacd5eae8564e6dfdb490)
![{\displaystyle S=[0,1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e864a9b8dc0b19134f37427101cb5ebece0805cf)
![{\displaystyle \varphi :[0,1]\to 2^{[0,1]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/143257b22f94c2b92ceb9f1e0526b18ce0405b20)
![{\displaystyle [a_{i},b_{i}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ea1adde530cc8cd17a451c905e20cfe882e73fdd)
![{\displaystyle [0,1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/738f7d23bb2d9642bab520020873cccbef49768d)
![{\displaystyle m\in [0,1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2c233f01eb60173e7860c7bf11cc0a4e5b401ece)
![{\displaystyle [0,1]\times [0,1]\times [0,1]\times [0,1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/49925af62ae6eac9616af753b4206e2e084fdf64)
