这一部分是樊畿不等式。

预备（一）

之前我们已经使用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:X→Rf:X\rightarrow \mathbb R。如果满足
（1）∀x∈X,y→f(x,y)\forall x\in X,y\rightarrow f(x,y)在 XX 为下半连续，且
（2）∀y∈X,x→f(x,y)\forall y\in X,x\rightarrow f(x,y)在 XX 为拟凹的。
则miny∈Xsupx∈Xf(x,y)≤supx∈Xf(x,x)min_{y\in X}sup_{x\in X}f(x,y)\leq sup_{x\in X}f(x,x)。

Proof.
由题设（1）有∀x∈X,y→f(x,y)\forall x\in X,y\rightarrow f(x,y)在 XX 为下半连续，根据前述Theorem 0，可知∀x∈X,y→supf(x,y)\forall x\in X,y\rightarrow supf(x,y)在 XX 为下半连续。而 XX 为紧集，可知最小值miny∈Xsupx∈Xf(x,y)min_{y\in X}sup_{x\in X}f(x,y)存在。
令b=supx∈Xf(x,x)b=sup_{x\in X}f(x,x)，F(x):={y∈X:f(x,y)≤b}F(x):=\lbrace y\in X:f(x,y)\leq b \rbrace。
而y→f(x,y)y\rightarrow f(x,y)在XX为下半连续，根据半连续定义·版本二[Def Vr.2]，可知F(x)F(x)为闭集。此外，根据F(x)F(x)的定义方式，有F(x)⊂XF(x)\subset X，作为紧集的闭子集，因此F(x)F(x)也为紧集。
Claim.
∀{x1,...,xn}⊂X,co{x1,...,xn}⊂⋃i=1nF(xi).\forall\lbrace x_{1},...,x_{n} \rbrace\subset X,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∈X,x→f(x,y)\forall y\in X,x\rightarrow f(x,y)在 XX 为拟凹的，因此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∈Xf(x,x)b=sup_{x\in X}f(x,x)，矛盾。因此，必有∀{x1,...,xn}⊂X,co{x1,...,xn}⊂⋃i=1nF(xi).\forall\lbrace x_{1},...,x_{n} \rbrace\subset X,co\lbrace x_{1},...,x_{n} \rbrace\subset\bigcup_{i=1}^{n}F(x_{i}).

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

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

版本二

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