查看“︁角谷不动点定理”︁的源代码

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

此定理1941年由角谷静夫提出<ref>{{cite journal |author1=Kakutani, Shizuo |title=A generalization of Brouwer's fixed point theorem |journal=Duke Mathematical Journal |date=1941 |volume=8 |issue=3 |pages=457–459 |doi=10.1215/S0012-7094-41-00838-4}}</ref>，曾被[[约翰·福布斯·纳什|纳什]]用于描述[[纳什均衡]]<ref>{{cite journal |author1=Nash, J.F., Jr. |title=Equilibrium Points in N-Person Games |journal=Proc. Natl. Acad. Sci. U.S.A. |date=1950 |volume=36 |issue=1 |pages=48-49 |doi=10.1073/pnas.36.1.48 |pmid=16588946}}</ref>。之后，此定理在[[博弈论]]和[[经济学]]中得到了广泛应用<ref>{{cite book |author1=Border, Kim C. |title=Fixed Point Theorems with Applications to Economics and Game Theory |date=1989 |publisher=Cambridge University Press |isbn=0-521-38808-2}}</ref>。

== 叙述 ==

角谷不动点定理的叙述如下<ref>{{cite book |author1=Osborne, Martin J. |coauthors=Rubinstein, Ariel |title=A Course in Game Theory |date=1994 |publisher=Cambridge, MA: MIT}}</ref>

令<math>S</math>为欧几里得空间 <math>\mathbf{R}^n</math>中的[[空集|非空]]紧凸集，令<math>\varphi:S \to 2^S</math>为<math>S</math>上的一个具有下列特征的集值函数：

* <math>\varphi</math> 有闭图；

* 对于任意<math>x \in S, \varphi(x)</math> 为[[空集|非空]]凸集。

则<math>\varphi</math> 具有不动点。

== 定义 ==

'''集值函数'''

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

'''闭图'''

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

'''不动点'''

令<math>\varphi: X \to 2^X</math>为一个集值函数。如果<math>a \in \varphi(a), a \in X</math>，则<math>a</math>为一个不动点。

== 举例 ==

=== 有无穷多个不动点的函数 ===

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

=== 有一个不动点的函数 ===

例如：一个函数<math>\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}</math>

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

=== 不满足凸集的函数 ===

例如：一个函数<math>\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}</math>

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

=== 不满足闭合图的函数 ===

例如：一个函数<math>\varphi(x)=\begin{cases}
3/4 & 0 \leq x < 0.5 \\
1/4 & 0.5 \leq x \leq 1
\end{cases}</math>

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

== 其他叙述方式 ==

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

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

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

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

== 应用 ==

{{see also|数理经济学}}

=== 博弈论 ===

{{see also|博弈论}}

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

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

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

== 证明框架 ==

=== '''S'''是单维区间的情况 ===

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

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

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

{| class="wikitable"
|'''1'''
|<math>1 \geq b_i > a_i \geq 0</math>
|'''2'''
|<math>(b_i-a_i) \leq 2^{-i}</math>
|-
|'''3'''
|<math>p_i \in \varphi(a_i)</math>
|'''4'''
|<math>q_i \in \varphi(b_i)</math>
|-
|'''5'''
|<math>p_i \geq a_i</math>
|'''6'''
|<math>q_i \leq b_i</math>
|}

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

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

令<math>a_0=0,b_0=1</math>。令<math>p_0,q_0</math>分别为<math>\varphi(0),\varphi(1)</math>上的任一点。

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

如果存在<math>r \in \varphi(m)</math>并且有<math>r \geq m</math>，我们可以选取：

  <math>a_{k+1}=m</math>
  <math>b_{k+1}=b_k</math>
  <math>p_{k+1}=r</math>
  <math>q_{k+1}=q_k</math>

否则，必定存在<math>s \in \varphi(m)</math>使得<math>s \leq m</math>。我们选取：

  <math>a_{k+1}=a_k</math>
  <math>b_{k+1}=m</math>
  <math>p_{k+1}=p_k</math>
  <math>q_{k+1}=s</math>

* '''寻找子区间的极限值'''。

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

  <math>p^* \in \varphi(a^*)</math>
  <math>q^* \in \varphi(b^*)</math>
  <math>p^* \geq a^*</math>
  <math>q^* \leq b^*</math>

由于条件'''2'''，有<math>(b_i-a_i)\leq 2^{-i}</math>，所以：

<math>b^*-a^*=\lim(b_n-a_n)=0</math>

有：<math>a^* = b^* =x</math>，且 <math>\varphi(x) \ni q^* \leq x \leq p^* \in \varphi(x)</math>。

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

如果<math>p^*=q^*</math>，则有<math>p^*=x=q^*</math>。因为 <math>p^* \in \varphi(x)</math>，所以'''x'''是<math>\varphi</math>的一个不动点。

如果<math>p^* \neq q^*</math>，则构造一条'''p^*'''与'''q^*'''间的直线：

<math>x = (\cfrac{x-q^*}{p^*-q^*})p^* + (1-\cfrac{x-q^*}{p^*-q^*})q^* </math>

由于<math>\varphi(x)</math>是凸集，所以由<math>p^* \in \varphi(x),q^* \in \varphi(x)</math>可以推导出<math>x \in \varphi(x)</math>。所以'''x'''是<math>\varphi(x)</math>的一个不动点。

=== '''S'''是n维单纯形的情况 ===

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

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

=== 任意'''S'''的情况 ===

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

== 无穷维度的泛化 ==

角谷不动点定理可以泛化为无穷维度[[局部凸拓扑向量空间]]<ref>{{cite journal |author1=Glicksberg, I.L. |title=A Further Generalization of the Kakutani Fixed Point Theorem, with Application to Nash Equilibrium |journal=Proceedings of the American Mathematical Society |date=1952 |volume=3 |issue=1 |pages=170–174 |doi=10.2307/2032478}}</ref><ref>{{cite journal |author1=Fan, Ky |title=Fixed-point and Minimax Theorems in Locally Convex Topological Linear Spaces |journal=Proc Natl Acad Sci U S A |date=1952 |volume=38 |issue=2 |pages=121–126 |doi=10.1073/pnas.38.2.121}}</ref>。

'''上半连续性'''定义：

一个集值函数<math>\varphi: X \to 2^Y</math>是上半连续的，如果对于任何[[开集]]<math>W \in Y</math>，集合<math>\{x| \varphi(x) \subset W \}</math>也是'''X'''上的开集<ref>{{cite book |author1=Dugundji, James |coauthors=Andrzej Granas |title=Fixed Point Theory |date=2003 |publisher=Springer |isbn=978-0-387-00173-9 |pages=Chapter II, Section 5.8}}</ref>。

'''角谷映射'''定义：

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

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

令'''S'''为[[豪斯多夫空间|豪斯多夫]]局部凸[[拓扑向量空间]]的非空，紧致凸子集。令<math>\varphi: S \to 2^S</math>为角谷映射。则<math>\varphi</math>存在不动点。

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

== 参考资料 ==
{{Reflist|2}}

[[Category:数学分析]]
[[Category:数学定理]]
[[Category:数学专题]]
[[Category:一般均衡理论]]