在数学分析 中,角谷不动点定理 是一个适用于集值函数的不动点定理 。它为在定义在欧几里德空间中的紧 凸 集上的集值函数提供具有不动点 的充分条件 ,也即一个可以映射到包含自身的集合的点。角谷不动点定理是布劳威尔不动点定理 的泛化。布劳威尔不动点定理是拓扑学 的基础定理,它证明了定义在欧几里得空间 的紧致,凸子集上的连续函数 具有不动点。角谷静夫将此定理泛化到了集值函数。
此定理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 是单维区间的情况
角谷不动点定理的证明对于定义在闭区间 上的实数集值函数最为简单。假设
S
=
[
0
,
1
]
{\displaystyle S=[0,1]}
。假设
φ
:
[
0
,
1
]
→
2
[
0
,
1
]
{\displaystyle \varphi :[0,1]\to 2^{[0,1]}}
为在闭区间[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})}
且满足以上6个条件。令:
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 是n维单纯形的情况
当S 的维度大于1时,最简单的情况是n维单纯形 。n维单纯形相当于一个高维的三角形。证明单纯形的角谷不动点定理与区间上的证明极其相似。复杂度仅在于证明的第一步:如何切割空间为子空间。
类似于一维的情况,我们使用重心细分 方法将单纯形切割为子单纯形
为确保子单纯形序列的边界向相反方向运动,需要用到斯佩纳引理 以保证子单纯形的存在。
任意S 的情况
对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 .