南京邮电大学2010届本科生毕业设计（论文）
图4.1 [0,1]区间上的自变换函数的不动点
f(x)
1 x* 不动点 f(x)
2、Kakutani定理
0 45o x*
x 1
10080定义4.5.2：设向量v1,...,vr危Rn(rn)，且v1,v2,...,vr是线性无关的，则v1,v2,...,vr生40201r60第一季度第二季度第三季度三角形，3维单纯形是四面体。 任给x?S，总有 x=邋av,iii=1rrai=1,i=1ai 0
而且表示法唯一。称v1,v2,...,vr是S的顶点，称点集S。
禳镲Sj=镲x?S|x睚镲镲铪邋av,aiii=1rrj=0,i=1ai=1,ai 0
为单纯形S的一个端面（与顶点vj相对），它相当于以v1,...,vj-1,vj+1,...,vr为顶点的凸包。
以e1,...,en为顶点的单纯形S称为单纯形。如果x?S，则 x=其中
ai?0,?aii=1n?raiei=(a1,a2,...,an)
i=11
16
第四季度成的凸包S被称为r-1维单纯形，并记S=v,...,v。1维单纯形是直线段，2维单纯形是0东部西部北部南京邮电大学2010届本科生毕业设计（论文）
定义4.5.3：设S是一单纯形，一族单纯形S1,S2,...,SkDS称为S的单纯形部分，如果满足下列条件：S=USi；Si?Sji=1k ，或者Si与Sj相交于顶点，或者相交于一个端面
(i1j)。
通常称Si为S的单纯形剖分的一个胞径腔，并记的直径为Si。可见，单纯形剖分是把原单纯形分割成一些小单纯形，一个胞腔的端面不能严格地含于另一个胞腔的端面内部。
定理4.5.2（Kakutani，1941）：设SDRn是单纯形，集值映射j:S?2S取值非空凸闭集，而且是上半连续的，则j有不动点，即存在x?S，使得x?j(x)。
证明：对单纯形S作一系列细剖分：D1,D2,...,并要求剖分的胞腔直径趋于零。对于剖分Dm，定义单值映射jm:S?S如下：
m当x?S是某小胞腔的顶点，则任取y?j(x)作为j在作为x点的值，即jm(x)=y。
当x?S是某个小胞腔的内点，则把包含x在内的胞腔的n+1哥顶点的函数值的线性插值
jm在x点的值，具体地说，如果含x的胞腔的顶点是x,x,...,x，于是，x=n12n?naxi，其
i=0中，?ai=1,ai 0，则ji=0m(x)=?naijm(xi)，此处j(x)已知前确定。
mii=1m注意，当x位于两个胞腔的交面上时，则依两个胞腔所定义的j组合表达式是唯一的。
j显然，
m值是相等的，因为x的凸
:S?S是连续映射，由Brouwer不动点定理，存在xm?S，使得xm=jm (xm)。
m设xm所在的胞腔以v1m,...,vn为顶点，则
xm=am1vm1+...+amnvmn xm=jnm(xm)=am1ym1+...+amnymn
m其中ami30，?ai=1,ymi ji=0由于S是凸紧集，j(vmi)，
取值也是凸紧集，一句Weierstras
聚点原理，可选子序列{mk}r不妨就设mk=m，使得
17
南京邮电大学2010届本科生毕业设计（论文）
xmx,amimiai,y?yi,i1,2,.., .n当m时，剖分加细，因此，xm所在的胞腔的顶点都收缩到x，即
vmi?x， i=1,2,...n ,又因为jx=1是上半连续的，所以yi?j(x)，i=1,2,...,n。注意，
n1ay+...+anyi,?aa0?i=0n,i，而且j1(x)是凸集，故必有x?j(x)定理证完。
Kakutani不动点定理说的是对于有限维向量空间中任一非空有界闭凸子集上的上半连续自对应来说，在一定条件下都至少存在一个不动点。数理经济学家Scarf曾通过一种计算不动点的算法而提供了一个构造性证明，其中不动点的存在性是由这个定理所保证的。
Kakutani定理的一般形式如下：
定理4.5.3：设XDRn为凸紧集，集值映射j:X?2X取值非空凸闭集，而且是上半连续的，则j有不动点。
证明：因为X是有界集合，故可嵌入到某单纯形S内，即XDS。定义映射T:S?X如下：
当x?X,T(x)x。
x?X当x?X，但x?S，设点y是X中距离点x最近的点，即有y-x=minx-z，由于X是凸紧集，故如此的y存在且唯一。令T(x)=y。
不难验证，T是连续映射，再定义集值映射：
y:S?2S，y(x)=j(T(x))
则y取值非空凸闭集，且是上半连续的。事实上，如果xn?x0，yn?y(xn)，yn?y0，
0则由映射T的连续性，有T(xn)?T(x)。于是，再由集值映射j的上半连续性，
y0?j(T(x0))y(x0)，根据定理，y有不动点，使得
x?y(x)j()x(T)
注意，j的值域含在集合X之中，所以x?X，根据T的定义，有T(x)=x，于是，
x?j(x)，定理证完。
18
南京邮电大学2010届本科生毕业设计（论文）
利用集值映射的不动点定理，我们可以证明前节所述的多人对策的均衡局势的存在性。
数学家Brouwer在很久以前就注意到这一现象，他得出了如下的一般性定理，即著名的Brouwer不动点定理。
定理4.5.4：(Brouwer不动点定理)设f(x)是定义在集合X?Rn上的实函数，且
f(x)?X，如果f(x)是连续的，则至少存在一个x*?X\x X。C为一非空的有界凸闭集，
使f(x*)=x*。即f(x)至少存在一个不动点。见文献[8]
有意思的是，Brouwer不动点定理存在很强的几何直观[2]，但其数学证明却十分艰深，需要动用代数拓扑这类就是职业数学家也感到望而生畏的超级抽象数学工具。在此，我们不给出Brouwer不动点定理的证明。
我们所以要引用Kakutani不动点定理，是因为在纳什均衡存在性证明中所遇到的反应函数一般是多个因变量函数，即所谓对应，而角谷静夫不动点定理正好描述的是对应的一种性质。Kakutani不动点定理是Brouwer不动点定理的推广，但其自身的证明要用到Brouwer不动点定理。我们在这里不打算给出这两个不动点定理的证明，因为这类证明只是一种纯数学过程，但我们将给出纳什存在性定理的一种证明，因为了解存在性定理的证明过程有助于我们更好地理解纳什均衡。
为了解读Kakutani不动点定理，我们先来准备一下一些有关的数学概念。
对于任一有限集M，我们用RM表示形如x=(xm)m?M的所有向量组成的集合，其中对
M中每一个m，第m个分量xm是实数域R的一个元素。为方便计，我们也可将RM等价地理解为M到R上的所有函数组成的集合，这时RM中x的m分量xm也可被记为x(m)。 令S是RM中的一个子集，我们有如下定义：
定理4.5.5： S是凸的当且仅当对任意的x?RM,y?RM及满足0＃lx?S和y?S，则有
lx+(1-l)y S
1的l，只要
这里，x=(xm)m挝M,y=(ym)mM,lx+(1-l)y=(lxm+(1-l)ym),m M
定义4.5.4：S是闭的当且仅当对每个收敛的序列x(j)x(j)?S，则有limx(j)?S。
j{}j=1，如果对每个j都有
￥定义4.5.5：RM中的子集S是开的当且仅当它的补集RM\\S是闭的。
19
相关推荐：
loading