在数学分析 中，角谷不动点定理 是一个适用于集值函数的不动点定理 。它为在定义在欧几里德空间中的紧 凸 集上的集值函数提供具有不动点 的充分条件 ，也即一个可以映射到包含自身的集合的点。角谷不动点定理是布劳威尔不动点定理 的泛化。布劳威尔不动点定理是拓扑学 的基础定理，它证明了定义在欧几里得空间 的紧致，凸子集上的连续函数 具有不动点。角谷静夫将此定理泛化到了集值函数。
此定理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)
