角谷不动点定理

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

此定理1941年由角谷静夫提出，曾被纳什用于描述纳什均衡。之后，此定理在博弈论和经济学中得到了广泛应用。

叙述

角谷不动点定理的叙述如下

令$S$为欧几里得空间 ${𝐑}^n$中的非空紧凸集，令$\phi :S\to 2^S$为$S$上的一个具有下列特征的集值函数：

• $\phi$ 有闭图；

• 对于任意$x\in S,\phi (x)$ 为非空凸集。

则$\phi$ 具有不动点。

定义

集值函数

集值函数是一个从$X$映到$Y$的幂集的函数$\phi :X\to 2^Y$，使任意$x\in X,\phi (x)$都为非空集。这类函数有时也被称为对应，即函数的每个输入都将返回多个输出。因此，每个定义域的元素都对应一个由一个或多个值域元素构成的子集。

闭图

一个集值函数$\phi :X\to 2^Y$有闭图，如果集合$\{(x,y)|y\in \phi (x)\}$在积空间$X\times Y$中是一个闭子集。即：给定任意序列$\{x_n{\}}_{n\in \mathbb{N}}$和$\{y_n{\}}_{n\in \mathbb{N}}$，并满足$x_n\to x,y_n\to y,y_n\in \phi (x_n)$，则有$y\in \phi (x)$。

不动点

令$\phi :X\to 2^X$为一个集值函数。如果$a\in \phi (a),a\in X$，则$a$为一个不动点。

举例

有无穷多个不动点的函数

例如：函数$\phi (x)=[1-X/2,1-X/4]$满足所有角谷不动点定理的条件，并存在无穷多个不动点。

有一个不动点的函数

例如：一个函数$\phi (x)=\{\begin{array}{cc}3/4& 0\le x<0.5\\ (0,1)& x=0.5\\ 1/4& 0.5<x\le 1\end{array}$

满足所有角谷不动点定理的条件，并存在唯一一个不动点$x=0.5$。

不满足凸集的函数

例如：一个函数$\phi (x)=\{\begin{array}{cc}3/4& 0\le x<0.5\\ \{3/4,1/4\}& x=0.5\\ 1/4& 0.5<x\le 1\end{array}$

在$x=0.5$处不满足凸集定义，但满足其他角谷不动点定理的条件。这个函数没有不动点。

不满足闭合图的函数

例如：一个函数$\phi (x)=\{\begin{array}{cc}3/4& 0\le x<0.5\\ 1/4& 0.5\le x\le 1\end{array}$

不存在不动点，因为函数不满足闭合图。考虑序列$x_n=0.5-1/n$和$y_n=3/4$：当$x_n\to x=0.5,y_n\to y=3/4,y\notin \phi (x)$。

其他叙述方式

角谷静夫的原始论文使用了上半连续性的概念叙述此定理：

令S为欧几里得空间${𝐑}^n$上的一个非空，紧致，凸集的子集。令$\phi :S\to 2^S$为上半连续的集值函数，且$\phi (x)$在所有$x\in S$上非空，闭合，且为凸。则函数$\phi$有不动点。

这一叙述与之前的叙述完全等价。

我们可以通过集值函数的闭图像定理来说明这种等价关系：对紧致的豪斯多夫空间$Y$，一个集值函数$\phi :X\to 2^Y$有闭合图的充分必要条件是：$\phi$是上半连续的，且对所有$x$,$\phi$是闭集。因为所有欧几里得空间都为豪斯多夫空间，且$\phi$在这种叙述方式中必须为封闭值，所以根据闭图像定理，两种叙述方式等价。

应用

博弈论

角谷不动点定理可以用来证明零和博弈中的极小化极大算法。

纳什利用角谷不动点定理证明了博弈论中的一个重要结论。这一定理暗示，在任何混合策略的多人有限游戏中都必定存在纳什均衡。纳什的贡献使他获得了诺贝尔经济学奖。

• 基本集S是博弈中各个参与者选择的混合策略的多元组集合。假设每个参与者有k种可能的行为，那么每个参与者的策略就是一个相加之和为1的k元概率，也即每个参与者的策略空间是${𝐑}^k$空间中的单纯形。而S是所有这些单纯形的笛卡儿积，并且S是一个非空，紧致和凸型的${𝐑}^{kn}$的子集。
• 函数$\phi (x)$将每个多元组都与另一个多元组联系起来，即每个参与者的策略都是她对于其他参与者策略的最佳应对。由于最佳应对可以不唯一，$\phi (x)$是一个集值函数。对任意x，$\phi (x)$都是非空的，因为一定存在至少一个最佳应对策略。$\phi (x)$也是凸的，因为任意两个最佳应对的组合仍然是最佳应对。$\phi (x)$也可以被证明是闭合图。
• 纳什均衡被定义为$\phi (x)$的不动点，即：策略多元组集合中，每个参与者的策略都是其他参与者策略的最佳应对。角谷不动点定理保证了不动点的存在。

证明框架

S是单维区间的情况

角谷不动点定理的证明对于定义在闭区间上的实数集值函数最为简单。假设$S=[0,1]$。假设$\phi :[0,1]\to 2^{[0,1]}$为在闭区间[0,1]上的集值函数，且满足角谷不动点定理的条件。

• 创建一个序列，使序列处于[0,1]的具有相邻点的子区间中，并向相反方向移动。

令$(a_i,b_i,p_i,q_i),i=0,1,\cdots$为一个具有下列特点的序列：

1	$1\ge b_i>a_i\ge 0$	2	$(b_i-a_i)\le 2^{-i}$
3	$p_i\in \phi (a_i)$	4	$q_i\in \phi (b_i)$
5	$p_i\ge a_i$	6	$q_i\le b_i$

闭集$[a_i,b_i]$形成了一个由$[0,1]$的子区间组成的序列。条件2使这些子区间的范围逐渐减小，而条件3-6让$\phi$令子区间的边界向相反方向移动。

这样一个序列可以按如下方式构建：

令$a_0=0,b_0=1$。令$p_0,q_0$分别为$\phi (0),\phi (1)$上的任一点。

假设我们已经选取了序列的第k个元素为$(a_k,b_k,p_k,q_k)$且满足以上6个条件。令：$m=(a_k+b_k)/2$。一定有$m\in [0,1]$，因为$[0,1]$是凸集。

如果存在$r\in \phi (m)$并且有$r\ge m$，我们可以选取：

 $a_{k+1}=m$
 $b_{k+1}=b_k$
 $p_{k+1}=r$
 $q_{k+1}=q_k$

否则，必定存在$s\in \phi (m)$使得$s\le m$。我们选取：

 $a_{k+1}=a_k$
 $b_{k+1}=m$
 $p_{k+1}=p_k$
 $q_{k+1}=s$

• 寻找子区间的极限值。

根据吉洪诺夫定理，紧致集合的笛卡儿积$[0,1]\times [0,1]\times [0,1]\times [0,1]$也是紧致的。由于序列$(a_n,b_n,p_n,q_n)$在这个集合里，所以根据波尔查诺-魏尔斯特拉斯定理，这个序列一定存在收敛的子序列。假设这个收敛子序列的极限是$(a^{*},b^{*},p^{*},q^{*})$。由于$\phi$是闭合图，一定有：

 $p^{*}\in \phi (a^{*})$
 $q^{*}\in \phi (b^{*})$
 $p^{*}\ge a^{*}$
 $q^{*}\le b^{*}$

由于条件2，有$(b_i-a_i)\le 2^{-i}$，所以：

$b^{*}-a^{*}=\lim (b_n-a_n)=0$

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

• 证明子区间的极限值为不动点

如果$p^{*}=q^{*}$，则有$p^{*}=x=q^{*}$。因为 $p^{*}\in \phi (x)$，所以x是$\phi$的一个不动点。

如果$p^{*}\ne q^{*}$，则构造一条p^*与q^*间的直线：

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

由于$\phi (x)$是凸集，所以由$p^{*}\in \phi (x),q^{*}\in \phi (x)$可以推导出$x\in \phi (x)$。所以x是$\phi (x)$的一个不动点。

S是n维单纯形的情况

当S的维度大于1时，最简单的情况是n维单纯形。n维单纯形相当于一个高维的三角形。证明单纯形的角谷不动点定理与区间上的证明极其相似。复杂度仅在于证明的第一步：如何切割空间为子空间。

• 类似于一维的情况，我们使用重心细分方法将单纯形切割为子单纯形
• 为确保子单纯形序列的边界向相反方向运动，需要用到斯佩纳引理以保证子单纯形的存在。

任意S的情况

对n维单纯形的证明可以用来证明任意紧致，凸型S情况下的角谷不动点定理。单纯形在这种情况下不再有直线的边界，而是有曲线边界。这会用到形变收缩。

无穷维度的泛化

角谷不动点定理可以泛化为无穷维度局部凸拓扑向量空间。

上半连续性定义：

一个集值函数$\phi :X\to 2^Y$是上半连续的，如果对于任何开集$W\in Y$，集合$\{x|\phi (x)\subset W\}$也是X上的开集。

角谷映射定义：

令X,Y为拓扑向量空间，$\phi :X\to 2^Y$为集值函数。如果Y为凸，且$\phi :X\to 2^Y$对所有$x\in X$都是上半连续的，非空，紧致的凸集，则$\phi :X\to 2^Y$称为角谷映射。

角谷-格里科斯伯格-樊定理的叙述为：

令S为豪斯多夫局部凸拓扑向量空间的非空，紧致凸子集。令$\phi :S\to 2^S$为角谷映射。则$\phi$存在不动点。

对应的单值函数定理是吉洪诺夫不动点定理。