这一部分是樊畿不等式。

预备(一)

之前我们已经使用Sperner引理表述过了KKM引理,现在为了得到樊畿不等式,需要先引入KKMF引理。

首先回顾一下KKM引理

令Δ=co{v0,..,vm}⊂Rm+1\Delta = co\lbrace v_{0},..,v_{m} \rbrace\subset\mathbb {R}^{m+1},其中{v0,…,vm}​\lbrace v_{0},…,v_{m} \rbrace​仿射无关,令{F0,…,Fm}​\lbrace F_{0},…, F_{m} \rbrace​为Δ​\Delta​中的一族闭集,使得任给以A⊂{0,…,m}​A\subset\lbrace 0,…,m \rbrace​为标号的子集有co{vi:i∈A}⊂⋃i∈AFi​co\lbrace v_{i}:i\in A \rbrace\subset\bigcup_{i\in A}F_{i}​,则⋂i=0mFi≠∅​\bigcap_{i=0}^{m}F_{i}\neq \varnothing​。

意即,Δ​\Delta​为m+1​m+1​个仿射无关向量的凸包,每个Fi​Fi​均为Δ​\Delta​内的闭集。如果从指标集{0,…,m}​\lbrace 0,…,m \rbrace​里任选一组子集A(比如A={0,2,6}​A=\lbrace 0,2,6 \rbrace​),对相应的向量们(比如{v0,v2,v6}​\lbrace v_{0}, v_{2}, v_{6} \rbrace​)做凸包,所形成的低维单纯形(比如co{v0,v2,v6}​co\lbrace v_{0}, v_{2}, v_{6} \rbrace​)都被包含在相应的闭集之并里(比如F0∪F2∪F6​F_{0}∪F_{2}∪F_{6}​),那么把全部指标都用上,把从i=1​i=1​到i=m​i=m​的所有Fi​Fi​们取交,会是非空的。

最先几次的笔记内容所使用的语言实在是含混不清,又为了「砸挂」而使用诡异的记法,应该以后会重新写一下。

KKM引理的一般形式

令K=co{a0,…,am}⊂Rk​K=co\lbrace a_{0},…,a_{m} \rbrace\subset\mathbb R^{k}​,令{F0,…,Fm}​\lbrace F_{0},…,F_{m} \rbrace​为一族闭集使得任给A⊂{0,…,m}​A\subset\lbrace 0,…,m \rbrace​,有co{ai:i⊂A}⊂⋃i∈AFi​co\lbrace a_{i}:i\subset A \rbrace\subset\bigcup_{i\in A}F_{i}​,则⋂i=0mFi≠∅​\bigcap_{i=0}^{m}F_{i}\neq\varnothing​。

把仿射无关向量组换成了任意一组a0,…,ama_{0},…,a_{m}会带来一些影响,例如如果aia_{i}们不是仿射无关的话KK会是低于m+1m+1维的单纯形。不过后面会看到这并不会改变结果。

证明:
定义σ:Δ→K\sigma:\Delta\rightarrow K 为σ(z)=Σi=0mziai\sigma(z)=\Sigma_{i=0}^{m}z_{i}a_{i},其中ziz_{i}为使得z=Σi=0mziviz=\Sigma_{i=0}^{m}z_{i}v_{i}而∀z∈Δ\forall z\in \Delta的那些ziz_{i}们,这就将单纯形Δ\Delta与KK联系了起来。
如果aia_{i}们不是仿射无关的,表示codomin维数低于domin维数,则σ\sigma不是单射。不过不是单射也无所谓,不影响其连续性。
连续函数值域中的闭集,其原像(射回去)仍是闭集,因此对于像集F(xi)F(x_{i}),则原像集Si=σ−1(Fi)S_{i}=σ^{-1}(F_{i})也是闭的。

Claim
任给A⊂{0,...,m}​A\subset\lbrace 0,...,m \rbrace​,有co{vi:i∈A}⊂⋃i∈ASi​co\lbrace v_{i}:i\in A \rbrace\subset\bigcup_{i\in A}S_{i}​。
if not,则有∃z∈co{vi:i∈A},s.th.z∉⋃i∈ASi,i.e.z∉Si,∀i∈A​\exists z\in co\lbrace v_{i}:i\in A \rbrace,s.th.z\notin\bigcup_{i\in A}S_{i},i.e.z\notin S_{i},\forall i\in A​。但这就意味着z∉σ−1(Fi),∀i∈A,i.e.σ(z)∉⋃i∈AFi​z\notin\sigma^{-1}(F_{i}),\forall i\in A,i.e.\sigma(z)\notin\bigcup_{i\in A}F_{i}​则σ(z)∈co{ai:i∈A}⊈⋃i∈AFi​\sigma(z)\in co\lbrace a_{i}:i\in A \rbrace\nsubseteq\bigcup_{i\in A}F_{i}​,矛盾。
至此,我们已经有了任给A⊂{0,...,m}​A\subset\lbrace 0,...,m \rbrace​,有co{vi:i∈A}⊂⋃i∈ASi​co\lbrace v_{i}:i\in A \rbrace\subset\bigcup_{i\in A}S_{i}​,因此根据单纯形上的KKM引理,有⋂i=0mSi≠∅​\bigcap_{i=0}^{m}S_{i}\neq\varnothing​。
从其中任选一点z∈⋂i=0mSi=⋂i=0mσ−1(Fi)​z\in\bigcap_{i=0}^{m}S_{i}=\bigcap_{i=0}^{m}\sigma^{-1}(F_{i})​,即有σ(z)∈⋂i=0mFi​\sigma(z)\in\bigcap_{i=0}^{m}F_{i}​,从而⋂i=0mFi≠∅​\bigcap_{i=0}^{m}F_{i}\neq\varnothing​。□​\square​

KKMF引理

令X⊂RkX\subset\mathbb R^{k},∀x∈X\forall x\in X,令F(x)⊂RkF(x)\subset\mathbb R^{k}为闭集,如果有
(1)任给有限个点构成的集合{x1,...,xn}⊂X\lbrace x_{1},...,x_{n} \rbrace\subset X,有co{x1,...,xn}⊂⋃i=1nF(xi)co\lbrace x_{1},...,x_{n} \rbrace\subset\bigcup_{i=1}^{n}F(x_{i});
(2)至少有某个x∈Xx\in X使得F(x)F(x)为紧集。
则⋂x∈XF(x)≠∅\bigcap_{x\in X}F(x)\neq\varnothing。

证明:
从上述KKM引理的一般形式可知,有⋂i=1mF(xi)≠∅\bigcap_{i=1}^{m}F(x_{i})\neq\varnothing,而由此处题设(1)可知,对于每一组{1,...,m}\lbrace 1,...,m \rbrace都可以应用上节结果。即对于任意有限个F(xi)F(x_{i})其交集非空。
记满足题设(2)的那个xx为x0x_{0},相应地那个紧集为F(x0)F(x_{0}),而既然任意有限个F(xi)F(x_{i})交集非空,再交上F(x0)F(x_{0})依然非空,即F(x0)⋂(⋂i=1nF(xi))=⋂i=0nF(xi)≠∅F(x_{0})\bigcap(\bigcap_{i=1}^{n}F(x_{i}))=\bigcap_{i=0}^{n}F(x_{i})\neq\varnothing,因为在nn为有限时,n+1n+1依然为有限。
并且⋂i=0nF(xi)\bigcap_{i=0}^{n}F(x_{i})是闭集们的交集,依然为闭集,而⋂i=0nF(xi)⊂F(x0)\bigcap_{i=0}^{n}F(x_{i})\subset F(x_{0})表明⋂i=0nF(xi)\bigcap_{i=0}^{n}F(x_{i})是紧集的闭子集,因此它本身也是紧集。一集合CC为紧集当且仅当任意具有有限交性质(F.I.P.)的非空闭子集族C\mathscr{C}之交集非空。(注:C={B∈P(C):B is closed and nonempty}\mathscr{C}=\lbrace B\in\mathscr{P}(C):B\space is \space closed\space and\space nonempty \rbrace,P(C)\mathscr{P}(C)为CC的幂集。此处只要求闭子集族具有有限交性质,而闭子集族本身可以含有无限多个元素,其每个元素是闭集)。
而我们已经知道了任意有限个闭集F(xi)F(x_{i})们具有非空交集,且⋂i=0mFi\bigcap_{i=0}^{m}F_{i}为紧集,因此⋂x∈XF(x)≠∅\bigcap_{x\in X}F(x)\neq\varnothing。□\square

预备(二)

一些概念

[Partial Order]

非空集合DD,二元关系R⊂D×DR\subset D\times D。如果RR满足反身性、传递性,则称RR为 preorder(常见译名为前序、预序)。如果除了反身性、传递性以外还满足反对称性(antisymmetry,即if aRbaRb and bRabRa then a=ba=b),则称为 partial order (常见译名为偏序、半序)。此时用来定义偏序RR的集合DD称为partially ordered set,简记为poset(常见译名为偏序集)。

[有向集]

偏序集DD,偏序RR。如果满足∀a,b∈D\forall a,b\in D,∃c⊂D\exists c\subset D, s.th. cRacRa且cRbcRb,即总能找到一个比DD中任意两个元素同时都「更RR」的元素,则称此偏序集DD 为有向集。常见的有向集是在≥\geq关系下的自然数集N\mathbb N。

[网]

XX为一拓扑空间,DD为一有向集。{xα:α∈D}\lbrace x_{α}:α\in D \rbrace称为XX中的网。其实就是序列概念的拓展,当DD是特别的有向集,即(在≥\geq关系下的)自然数集N\mathbb N时,网就是序列。这里不限于自然数集,而是拓展到了一般的有向集中。

[Hausdorff 空间]

若对于一个空间中任意相异的两点,都可以分别各用一个开集将其包住,且这两个开集不相交,则称此空间为 Hausdorff 空间。

[Hausdorff 拓扑线性空间]

若在Hausdorff 空间上定义拓扑,使得在此空间上的向量加法和标量乘法为连续函数,则称此Hausdorff 空间为Hausdorff 拓扑线性空间。

[泛函]

f:X→Rf:X\rightarrow \mathbb R。定义域来自一般性的抽象空间(而函数的定义域来自于欧氏空间,取值依然为实值。在这一节里,XX 为 Hausdorff 拓扑空间。

[半连续]

为有所区别,遵照Afa.Ok的做法,将函数/泛函的半连续称为 semi-continuous,将对应的半连续称为 hemi-continuous。此处为泛函的半连续。

半连续定义·版本一[Def Vr.1]

XX为Hausdorff 拓扑空间(此后记为HTS),泛函f:X→Rf:X\rightarrow \mathbb R(此后简记为 fl )。给定点x∈Xx\in X。
如果∀ϵ>0\forall \epsilon>0,总能找到开邻域U(x)U(x),使得∀x′∈U(x′)\forall x^{\prime}\in U(x^{\prime}),有f(x′)<f(x)+ϵf(x^{\prime})<f(x)+\epsilon,则称 flff在xx处上半连续,即 u.s.c. at xx;
如果∀ϵ>0\forall \epsilon>0,总能找到开邻域U(x)U(x),使得∀x′∈U(x′)\forall x^{\prime}\in U(x^{\prime}),有f(x′)>f(x)−ϵf(x^{\prime})>f(x)-\epsilon,则称 flff在xx处下半连续,即 l.s.c. at xx.

半连续定义·版本二[Def Vr.2]

HTS XX , flf:X→Rf:X\rightarrow \mathbb R,
ff is upper semi-continuous on XX iff ∀c∈R\forall c\in \mathbb R,{x∈X:f(x)≥c}\lbrace x\in X:f(x)\geq c \rbraceis closed;
ff is lower semi-continuous on XX iff ∀c∈R\forall c\in \mathbb R,{x∈X:f(x)≤c}\lbrace x\in X:f(x)\leq c \rbraceis closed;
ff is continuous on XX iff it both u.s.c. and l.s.c.

Claim. 上述两种定义方式是等价的。

Proof.

此处只对上半连续情况作出证明。

Part I Def Vr.1⇒\RightarrowDef Vr.2

从 Vr.1 我们知道f(x)f(x)在X上是上半连续的,即∀x∈X,∀ϵ>0,∃U(x)为x的开邻域.s.th.∀x′∈U(x),有f(x′)<f(x)+ϵ\forall x\in X,\forall \epsilon>0,\exists U(x)为x的开邻域.s.th.\forall x^{\prime}\in U(x),有f(x^{\prime})<f(x)+\epsilon,而我们需要证明∀c∈R\forall c\in \mathbb R,{x∈X:f(x)≥c}\lbrace x\in X:f(x)\geq c \rbrace是闭集,意即,我们需要证明,任给来自{x∈X:f(x)≥c}\lbrace x\in X:f(x)\geq c \rbrace的网{xα}\lbrace x_{\alpha} \rbrace如果xα→x∗x_{\alpha}\rightarrow x^{\ast},则有f(x∗)≥cf(x^{\ast})\geq c。(xα→x∗x_{\alpha}\rightarrow x^{\ast}即是说∀U(x∗)为\forall U(x^{\ast})为x∗x^{\ast}的邻域,∃α0,s.th.∀α>α0\exists \alpha_{0},s.th.\forall \alpha>\alpha_{0},都有xα∈U(x∗)x_{\alpha}\in U(x^{\ast}))

既然网{xα}\lbrace x_{\alpha} \rbrace是从{x∈X:f(x)≥c}\lbrace x\in X:f(x)\geq c \rbrace里选择的,那么就有f(xα)≥cf(x_{\alpha})\geq c;
从Vr.1知∀x′∈U(x′)\forall x^{\prime}\in U(x^{\prime})我们有f(x′)<f(x∗)+ϵf(x^{\prime})<f(x^{\ast})+\epsilon 因此 f(xα)<f(x∗)+ϵf(x_{\alpha})<f(x^{\ast})+\epsilon;

将两者结合,有c≤f(xα)<f(x∗)+ϵc\leq f(x_{\alpha})<f(x^{\ast})+\epsilon,由于ϵ\epsilon是任选的,因此有c≤f(x∗)c\leq f(x^{\ast})。

Part II Def Vr.2⇒\RightarrowDef Vr.1

从Vr.2我们得知 ∀c∈R\forall c\in \mathbb R,{x∈X:f(x)≥c}\lbrace x\in X:f(x)\geq c \rbrace为闭集,则 ∀c∈R\forall c\in \mathbb R,{x∈X:f(x)<c}\lbrace x\in X:f(x)< c \rbrace为开集,因为cc是任选的,不妨令c=f(x∗)+ϵc=f(x^{\ast})+\epsilon,因此{x∈X:f(x)<f(x∗)+ϵ}\lbrace x\in X:f(x)<f(x^{\ast})+\epsilon \rbrace为开集,特别地,x∗∈{x∈X:f(x)<f(x∗)+ϵ}x^{\ast}\in\lbrace x\in X:f(x)<f(x^{\ast})+\epsilon \rbrace。而既然x∗x^{\ast}属于一个开集,那么必存在开邻域U(x∗)U(x^{\ast})使得x∗∈U(x∗)⊂{x∈X:f(x)<f(x∗)+ϵ}x^{\ast}\in U(x^{\ast})\subset \lbrace x\in X:f(x)<f(x^{\ast})+\epsilon \rbrace,而这就是说∀x′∈U(x∗)\forall x^{\prime}\in U(x^{\ast}),都有f(x′)<f(x∗)+ϵf(x^{\prime})<f(x^{\ast})+\epsilon,而这正是ff在x∗x^{\ast}上半连续的Def Vr.1。□\square

半连续定义·版本三[Def Vr.3]

ff u.s.c. at x∗x^{\ast} iff ∀xα→x∗,lim sup f(xα)≤f(x∗)\forall x_{\alpha}\rightarrow x^{\ast},lim\space sup\space f(x_{\alpha})\leq f(x^{\ast});
ff l.s.c. at x∗x^{\ast} iff ∀xα→x∗,lim inf f(xα)≥f(x∗)\forall x_{\alpha}\rightarrow x^{\ast},lim\space inf\space f(x_{\alpha})\geq f(x^{\ast}).

Theorem 0

HTSXX,∀λ∈Λ\forall \lambda \in\Lambda,flfλ:X→Rf_{\lambda}:X\rightarrow \mathbb R.
(1)if fλf_{\lambda}u.s.c. on XX, ∀λ∈Λ\forall \lambda\in\Lambda, then infλ∈Λfλ(x)inf_{\lambda\in\Lambda}f_{\lambda}(x) u.s.c on XX;
(2)if fλf_{\lambda}l.s.c. on XX, ∀λ∈Λ\forall \lambda\in\Lambda, then supλ∈Λfλ(x)sup_{\lambda\in\Lambda}f_{\lambda}(x) l.s.c on XX.

Proof. (for case(1)only)

∀c∈R\forall c\in \mathbb R,{x∈X:infλ∈Λfλ(x)≥c}\lbrace x\in X:inf_{\lambda\in\Lambda}f_{\lambda}(x)\geq c \rbrace={x∈X:inffλ(x)≥c,∀λ∈Λ}\lbrace x\in X:inff_{\lambda}(x)\geq c,\forall\lambda\in\Lambda \rbrace=⋂λ∈Λ{x∈X:fλ≥c}\bigcap_{\lambda\in\Lambda}\lbrace x\in X:f_{\lambda}\geq c \rbrace,而既然 fλf_{\lambda}在XX上半连续,则{x∈X:fλ≥c}\lbrace x\in X:f_{\lambda}\geq c \rbrace为闭集,因此⋂λ∈Λ{x∈X:fλ≥c}\bigcap_{\lambda\in\Lambda}\lbrace x\in X:f_{\lambda}\geq c \rbrace为闭集,即{x∈X:infλ∈Λfλ(x)≥c}\lbrace x\in X:inf_{\lambda\in\Lambda}f_{\lambda}(x)\geq c \rbrace是闭集,因此infλ∈Λfλ(x)inf_{\lambda\in\Lambda}f_{\lambda}(x)在XX为上半连续。

接下来可以进入主题了。

樊畿不等式

Theorem 1

Hausdorff 拓扑线性空间 XX,EE 为 XX 中的非空紧凸子集,泛函f:E×E→Rf:E\times E\rightarrow \mathbb R。如果满足
(1)∀x∈E,y→f(x,y)\forall x\in E,y\rightarrow f(x,y)在 EE 为下半连续,且
(2)∀y∈E,x→f(x,y)\forall y\in E,x\rightarrow f(x,y)在 EE 为拟凹的。
则miny∈Esupx∈Ef(x,y)≤supx∈Ef(x,x)min_{y\in E}sup_{x\in E}f(x,y)\leq sup_{x\in E}f(x,x)。

Proof.
由题设(1)有∀x∈E,y→f(x,y)\forall x\in E,y\rightarrow f(x,y)在 EE 为下半连续,根据前述Theorem 0,可知∀x∈E,y→supf(x,y)\forall x\in E,y\rightarrow supf(x,y)在 EE 为下半连续。而 EE 为紧集,可知最小值miny∈Esupx∈Ef(x,y)min_{y\in E}sup_{x\in E}f(x,y)存在。
令b=supx∈Ef(x,x)b=sup_{x\in E}f(x,x),F(x):={y∈E:f(x,y)≤b}F(x):=\lbrace y\in E:f(x,y)\leq b \rbrace。
而y→f(x,y)y\rightarrow f(x,y)在EE为下半连续,根据半连续定义·版本二[Def Vr.2],可知F(x)F(x)为闭集。此外,根据F(x)F(x)的定义方式,有F(x)⊂EF(x)\subset E,作为紧集的闭子集,因此F(x)F(x)也为紧集。
Claim.
∀{x1,...,xn}⊂E,co{x1,...,xn}⊂⋃i=1nF(xi).\forall\lbrace x_{1},...,x_{n} \rbrace\subset E,co\lbrace x_{1},...,x_{n} \rbrace\subset\bigcup_{i=1}^{n}F(x_{i}).
if not, 则 ∃λi≥0(i=1,...,n)\exists \lambda_{i}\geq 0 (i=1,...,n) with∑i=1nλi=1\sum_{i=1}^{n}\lambda_{i}=1 使得 ∑i=1nλixi∉⋃i=1nF(xi)\sum_{i=1}^{n}\lambda_{i}x_{i}\notin \bigcup_{i=1}^{n}F(x_{i}),而既然它不属于并集,那么它必然也不属于其中任何一个集合,有∑i=1nλixi∉F(xj),∀j=1,...,n\sum_{i=1}^{n}\lambda_{i}x_{i}\notin F(x_{j}),\forall j=1,...,n,
根据 F(xj)F(x_{j}) 的定义,这等于说 f(xj,∑i=1nλixi)>b,∀j=1,...,n.f(x_{j},\sum_{i=1}^{n}\lambda_{i}x_{i})>b, \forall j=1,...,n. ,而既然每一个 f(xj,∑i=1nλixi)>bf( x_{j},\sum_{i=1}^{n}\lambda_{i}x_{i} )>b,那么它们的最小值 minjf(xj,∑i=1nλixi>bmin_{j}f(x_{j},\sum_{i=1}^{n}\lambda_{i}x_{i}>b。此外,根据题设(2)∀y∈E,x→f(x,y)\forall y\in E,x\rightarrow f(x,y)在 EE 为拟凹的,因此f(∑i=1nλixi,∑i=1nλixi)≥minjf(xj,∑i=1nλixi)>bf(\sum_{i=1}^{n}\lambda_{i}x_{i},\sum_{i=1}^{n}\lambda_{i}x_{i})\geq min_{j}f(x_{j},\sum_{i=1}^{n}\lambda_{i}x_{i})>b,意即f(∑i=1nλixi,∑i=1nλixi)>bf(\sum_{i=1}^{n}\lambda_{i}x_{i},\sum_{i=1}^{n}\lambda_{i}x_{i})>b,但根据 bb 的定义,b=supx∈Ef(x,x)b=sup_{x\in E}f(x,x),矛盾。因此,必有∀{x1,...,xn}⊂E,co{x1,...,xn}⊂⋃i=1nF(xi).\forall\lbrace x_{1},...,x_{n} \rbrace\subset E,co\lbrace x_{1},...,x_{n} \rbrace\subset\bigcup_{i=1}^{n}F(x_{i}).

根据KKMF引理,⋂x∈EF(x)≠∅\bigcap_{x\in E}F(x)\neq\varnothing,既然非空,可以任选一点y∗∈⋂x∈EF(x)=⋂x∈E{y∈E:f(x,y)≤b}={y∈E:f(x,y)≤b,∀x∈E}y^{\ast}\in\bigcap_{x\in E}F(x)=\bigcap_{x\in E}\lbrace y\in E:f(x,y)\leq b \rbrace=\lbrace y\in E:f(x,y)\leq b,\forall x\in E \rbrace,意即∀x∈E\forall x\in E,f(x,y∗)≤bf(x,y^{\ast})\leq b,既然任给 x∈Ex\in E 都有f(x,y∗)≤bf(x,y^{\ast})\leq b,那么supx∈Ef(x,y∗)≤bsup_{x\in E}f(x,y^{\ast})\leq b.

因此,miny∈E supx∈E f(x,y)≤supx∈Ef(x,y∗)≤b=supx∈Ef(x,x)min_{y\in E}\space sup_{x\in E}\space f(x,y)\leq sup_{x\in E}f(x,y^{\ast})\leq b=sup_{x\in E}f(x,x)。□\square

版本二

Hausdorff 拓扑线性空间 XX,EE 为 XX 中的非空紧凸子集,泛函f:E×E→Rf:E\times E\rightarrow \mathbb R。如果满足
(1)∀x∈E,y→f(x,y)\forall x\in E,y\rightarrow f(x,y)在 EE 为下半连续,且
(2)∀y∈E,x→f(x,y)\forall y\in E,x\rightarrow f(x,y)在 EE 为拟凹的,且
(3)∀x∈E,f(x,x)≤0\forall x\in E,f(x,x)\leq 0。
则∃y∗∈E\exists y^{\ast}\in E, s.th. ∀x∈E\forall x\in E, f(x,y∗)≤0f(x,y^{\ast})\leq 0。

Proof.
取前述证明过程中 b=0b=0 即可。□\square

头一次使用这个神奇的东西来记笔记,打公式真方便,还在学习中。应该各种小错误还不少,慢慢改吧,暂时先不放到公众号了。
预计下次是从樊畿不等式到Fan-Browder不动点定理以及利用樊畿不等式和投影定理来表述Kakutani不动点定理的另一种证明方式。

脱胎于:

Border K C. Fixed point theorems with applications to economics and game theory[M]. Cambridge university press, 1989.

Ichiishi T. Game theory for economic analysis[M]. Elsevier, 2014.

俞建. 博弈论与非线性分析[M]. 科学出版社, 2008.