介紹一些簡單的格點知識、超模概念以及塔斯基不動點定理。

格 Lattice

偏序集

給定一個集合 XX,如果能夠在 XX 上定義一個序關係 ≥\geq,使得 ≥\geq 在 XX 上滿足自反性、反對稱性和傳遞性,那麼 (X,≥)(X,\geq) 便是一個偏序集。

【舉例】向量的序關係

∀i\forall i

x=yx = y iff xi=yix_{i} = y_{i};

x≥yx\geq y iff xi≥yix_{i}\geq y_{i};

x>yx>y iff xi≥yix_{i}\geq y_{i}且至少有一個不等式嚴格成立;

x>>yx>>y iff xi>yix_{i}>y_{i}.

meet 與 join

給定偏序集 (X,≥)(X,\geq) 上的一對元素 x,y∈Xx,y\in X,定義元素 xx 和 yy 的 meet (∧\wedge) 和 join (∨\vee) 為

x∧y:=sup⁡{z∈X;x≥z,y≥z}x∨y:=inf⁡{z∈X;z≥x,z≥y}\begin{aligned} x \wedge y &:=\sup\left\{z\in X;x\geq z,y\geq z\right\}\\ x \vee y &:= \inf\left\{z\in X;z\geq x,z\geq y\right\} \end{aligned}

其中 sup⁡\sup 和 inf⁡\inf 是相對於偏序集 (X,≥)(X,\geq) 上的序關係而言的,例如 ≥\geq 可以是歐式空間中的逐維大小關係、集合中的包含關係等等。

【舉例】

x=(x1,...,xn)x = (x_{1},...,x_{n});

y=(y1,...,yn)y = (y_{1},...,y_{n}).

meet: x∧y=z=(z1,...,zn)x\wedge y = z = (z_{1},...,z_{n})

其中對於每個ii,ziz_{i}都是從相應的第ii項xix_{i}與yiy_{i}之間選取較小的那個;即∀i\forall i,zi=min{xi,yi}z_{i} = min\lbrace x_{i},y_{i} \rbrace;

join: x∨y=z=(z1,...,zn)x\vee y = z = (z_{1},...,z_{n})

其中對於每個ii,ziz_{i}都是從相應的第ii項xix_{i}與yiy_{i}之間選取較大的那個;即∀i\forall i,zi=max{xi,yi}z_{i} = max\lbrace x_{i},y_{i} \rbrace;

Def: Lattice

給定一個偏序集 (X,≥)(X,\geq) 如果對於集合中的任意一對元素 xx 和 yy,都滿足

x∧y:=sup⁡{z∈X;x≥z,y≥z}∈Xx∨y:=inf⁡{z∈X;z≥x,z≥y}∈X\begin{aligned} x \wedge y &:=\sup\left\{z\in X;x\geq z,y\geq z\right\}\in X\\ x \vee y &:= \inf \left\{z\in X;z\geq x,z\geq y\right\}\in X \end{aligned}

則稱偏序集 (X,≥)(X,\geq) 為一個 Lattice。

【舉例】給定一個集合X⊂RnX\subset\mathbb R^{n},如果集合XX中的任意一對元素 xx 和 yy 之meet和join都還在XX之內,則稱XX為一個Lattice。即∀x,y\forall x,y,都有x∧y∈Xx\wedge y\in X 並且 x∨y∈Xx\vee y\in X。

註意,此處我們不要求任意子集的 meet 和 join 都在集合之內 (那是完備格的要求),而只要求任意一對元素。

Def: Sublattice

給定一個格 (X,≥)(X,\geq) 和一個子集 S⊂XS\subset X,如果對於任何一對 x,y∈Sx,y\in S,都滿足 x∧y∈Sx\wedge y\in S 和 x∨y∈Sx\vee y\in S,則稱 SS 是 XX 在 ≥\geq 下的一個子格。

Fact: 子格

給定一個格 (X,≥)(X,\geq) 和一個子集 S⊂XS\subset X,SS 是 XX 在 ≥\geq 下的一個子格當且僅當 S≥SS\geq S。

Def: 最大(最小)元

給定一個 Lattice集合 ⊂Rn\subset\mathbb R^{n},如果 ∀x∈X\forall x\in X 都有 x∗≥xx^{\ast}\geq x(x∗≤xx^{\ast}\leq x),則稱元素 x∗∈Xx^{\ast}\in X 為格 XX 的最大(最小)元。

Th3

非空緊格必有最大及最小元。

證明

對於每個i∈{1,2,...,n}i\in\lbrace 1,2,...,n \rbrace,從各x∈Xx\in X中選擇使得第ii個坐標取到最大值的那一個作為zi∈Xz^{i}\in X,即zi∈argmaxx∈Xxiz^{i}\in arg max_{x\in X}x_{i}。
由於XX為緊集,因此對於任何一個ii,如上所述的最大元ziz^{i}都是可以找到的。令y=z1∨z2∨...∨zny = z^{1}\vee z^{2}\vee ...\vee z^{n}。而由於XX是格,格內元素之join仍在格內,即y∈Xy\in X。取y=(z11,...,znn)y = (z_{1}^{1},...,z_{n}^{n}),即yy的每個坐標都是那些能出現在該坐標的備選項中最大的,因此有y≥xy\geq x對於所有x∈Xx\in X。

Def 強集序

給定格 (X,≥for elements)(X,\geq_{\text{for elements}}) ,對於任何子集 A,B⊂XA,B\subset X,定義強集序 ≥for sets\geq_{\text{for sets}} 為

A≥for setsB iff (∀x∈A,y∈B) [x∨y∈A and x∧y∈B].A\geq_{\text{for sets}} B\text{ iff }(\forall x\in A,y\in B)\,[x\vee y\in A\text{ and }x\wedge y\in B].

此處關於序關係的下標是為了明確表明是應用於元素還是集合,但通過語境可以做出此種區分,因此後文將不再明確寫出。

對於來自於同一個格的兩個子集來説,一個子集“大”於另一個子集,意思是任選x∈Ax\in A和y∈By\in B,把二者逐坐標取較大者仍落在AA中,逐坐標取較小者仍落在BB中。這一定義同時處理了可比較和不可比較的元素對。

但這並不意味著,從更“大”的集合中任選一個元素,從更“小”的集合中任選一個元素,前一個元素一定“大於”後一個元素。但確實意味著,更“大”的集合中的“最大元”一定“大於”更“小”集合中的“最大元”,並且更“大”集合中的“最小元”一定“大於”更“小”集合中的“最小元”,即:強集序只能保證極端元素的排序關係,更不能保證其中每個元素的排序關係,這也是為什麼在超模博弈中,只有極端納什均衡具有單調比較靜態關係,但無法保證任意納什均衡具有單調比較靜態關係。

Def4: 超模性

給定一個格 (X,≥)(X,\geq) 以及函數 f:X→Rf:X\rightarrow\mathbb{R}。如果對於所有的 z,z′∈Xz,z^{\prime}\in X 都滿足

f(z)+f(z′)≤f(z∨z′)+f(z∧z′)f(z)+f(z^{\prime})\leq f(z\vee z^{\prime})+f(z\wedge z^{\prime})

則稱函數 ff 具有超模性。

兩個小性質:超模任意正的常數倍仍是超模;兩個超模的和仍是超模。

如果 XX 不僅是個偏序集,而且是個線序集 (任何兩個元素都可以比較大小,例如 R\mathbb{R}),那麼所有的函數都具有超模性 (前述不等式以等式成立)。因此可知,超模性具有 bites 僅當函數的定義域並非線序時 (例如 RN\mathbb{R}^{N}),否則超模性是平凡地成立的。

超模性是基數性質,未必在單調正變化下保持 (那是擬超模性的性質)。

Th5

任選取兩個格x⊂Rnx\subset\mathbb R^{n},y⊂Rny\subset\mathbb R^{n},取定義在X×YX\times Y上的一個超模f:X×Y→Rf:X\times Y\rightarrow\mathbb R。如果對於任意的y∈Yy\in Y,h(y)=maxx∈Xf(x,y)h(y) = max_{x\in X}f(x,y)都有良好定義,則hh也是XX上的超模。(類比Berge極大值定理)

證明

選取y1,y2∈Yy^{1},y^{2}\in Y,以及x1,x2∈Xx^{1},x^{2}\in X,使得h(yi)=f(xi,yi)h(y^{i}) = f(x^{i},y^{i})對於i=1,2i = 1,2均成立。則有

h(y1)+h(y2)=f(x1,y1)+f(x2,y2)h(y^{1})+h(y^{2}) = f(x^{1},y^{1})+f(x^{2},y^{2})

(根據我們對於h(⋅)h(\cdot)的設定)

≤f(x1∧x2,y1∧y2)+f(x1∨x2,y1∨y2)\leq f(x^{1}\wedge x^{2},y^{1}\wedge y^{2})+f(x^{1}\vee x^{2},y^{1}\vee y^{2})

(根據我們對於f(⋅)f(\cdot)是超模的設定)

≤h(y1∧y2)+h(y1∨y2)\leq h(y^{1}\wedge y^{2})+h(y^{1}\vee y^{2})

(再次根據我們對於h(⋅)h(\cdot)的設定)。□\square

Def: 乘積格

給定偏序集們 (Xi,≥i)i∈Nfinite(X_{i},\geq_{i})_{i\in N^{\text{finite}}},定義偏序集 X:=Πi∈NfiniteXiX:=\Pi_{i\in N^{\text{finite}}}X_{i},以及對於 x,y∈Xx,y\in X

x≥y iff xi≥iyi,∀ix\geq y\text{ iff }x_{i}\geq_{i}y_{i},\forall i

則稱 (X,≥)(X,\geq) 為乘積格。

Def: 增差

給定一個乘積格 (X,≥)(X,\geq),函數 f:X→Rf:X\rightarrow\mathbb{R} 滿足增差條件,當且僅當,任選維度 i≠j;i,j∈Ni\neq j;i,j\in N,給定 (i,j;xij;xi,xi′;xj,xj′)(i,j;x_{ij};x_{i},x_{i}^{\prime};x_{j},x_{j}^{\prime}),每當 xi′≥xix_{i}^{\prime}\geq x_{i} 和 xj′≥xjx_{j}^{\prime}\geq x_{j} 都有

f(xi′,xj′;x−ij)−f(xi,xj′;x−ij)≥f(xi′,xj;x−ij)−f(xi,xj;x−ij)f(x_{i}^{\prime},x_{j}^{\prime};x_{-ij})-f(x_{i},x_{j}^{\prime};x_{-ij})\geq f(x_{i}^{\prime},x_{j};x_{-ij})-f(x_{i},x_{j};x_{-ij})

注意前式要對任意選取的一對 i≠j;i,j∈Ni\neq j;i,j\in N 都成立。

【舉例】令X⊂RnX\subset\mathbb R^{n}為一個格,函數f:X→Rf:X\rightarrow\mathbb R。對於每個z∈Xz\in X,每對不同的指標i,ji,j以及相應的zi∗≥ziz_{i}^{\ast}\geq z_{i},zj∗≥zjz_{j}^{\ast}\geq z_{j},如果都有

f(z−ij,zi∗,zj∗)−f(z−ij,zi∗,zj)≥f(z−ij,zi,zj∗)−f(z−ij,zi,zj)f(z_{-ij},z_{i}^{\ast},z_{j}^{\ast})-f(z_{-ij},z_{i}^{\ast},z_{j})\geq f(z_{-ij},z_{i},z_{j}^{\ast})-f(z_{-ij},z_{i},z_{j})

則稱函數ff對於XX中的每對元素滿足增差性。

增差是基數性質,未必在單調正變換下保持。

Th7

X⊂RnX\subset\mathbb R^{n}而f:X→Rf:X\rightarrow\mathbb R。則函數ff為超模當且僅當ff在XX上滿足增差性。

Def. 單交叉(一)

假設自變量集為 X⊂RX\subset\mathbb{R},參數集為 T⊂RT\subset\mathbb{R}。一個函數 f:X⋅T→Rf:X\cdot T\rightarrow\mathbb{R} 對於 (x,t)(x,t) 滿足單交叉性質,如果對於任何 x′>xx^{\prime}> x 和 t′>tt^{\prime}> t 都有

f(x′,t)≥f(x,t)⇒f(x′,t′≥f(x,t′))f(x′,t)>f(x,t)⇒f(x′,t′>f(x,t′))\begin{aligned} f(x^{\prime},t)\geq f(x,t)&\Rightarrow f(x^{\prime},t^{\prime}\geq f(x,t^{\prime}))\\ f(x^{\prime},t)> f(x,t)&\Rightarrow f(x^{\prime},t^{\prime}> f(x,t^{\prime})) \end{aligned}

Def. 單交叉(二)

假設自變量集 XX 是一個格,參數集 TT 是一個偏序集。一個函數 f:X⋅T→Rf:X\cdot T\rightarrow\mathbb{R} 對於 (x,t)(x,t) 滿足單交叉性質,如果對於任何 x′>xx^{\prime}> x 和 t′>tt^{\prime}> t 都有

f(x′,t)≥f(x,t)⇒f(x′,t′≥f(x,t′))f(x′,t)>f(x,t)⇒f(x′,t′>f(x,t′))\begin{aligned} f(x^{\prime},t)\geq f(x,t)&\Rightarrow& f(x^{\prime},t^{\prime}\geq f(x,t^{\prime}))\\ f(x^{\prime},t)> f(x,t)&\Rightarrow& f(x^{\prime},t^{\prime}> f(x,t^{\prime})) \end{aligned}

單交叉是序數性質,可以在單調正變換下保持。

塔斯基不動點定理

完備格的定義和非減自映射的性質是證明Lemma 2進而證明塔斯基不動點定理的關鍵。

Def. 完備格

我們稱(A,≤)(A,\leq)是一個完備格當且僅當(A,≤)(A,\leq)是偏序集並且AA的每個子集都有上確界(當然也有下確界性質)。

註意,格的定義要求任意一對兒元素的 meet 和 join 仍在集合之內,而完備格的定義的相應要求施加於任何子集 (不僅任意一對,還得任意三個、任意四個……) 之上。

Def. 非減自映射

任給偏序集(A,≤)(A,\leq)。函數(自映射)f:A→Af:A\rightarrow A 稱為(A,≤)(A,\leq)上的非減自映射當且僅當對AA中任意兩個元素x,y∈Ax,y\in A ,每當x≤yx\leq y便有f(x)≤f(y)f(x)\leq f(y)。

Lemma 1

任給完備格(A,≤)(A,\leq)。f:A→Af:A\rightarrow A為(A,≤)(A,\leq)上的任一非減自映射,則:

(1)對所有的a,b∈A​a,b\in A​ ,若a≤b​a\leq b​,則([a,b],≤)​(\left[a,b\right],\leq)​也是一個完備格。其中,[a,b]={x∈A∣a≤x≤b}​\left[a,b\right]=\lbrace x\in A\mid a\leq x\leq b \rbrace ​。

(2)對所有的a,b∈Aa,b\in A ,若a≤ba\leq b、a≤f(a)a\leq f(a)且f(b)≤bf(b)\leq b,則f∣[a,b]f\mid_{\left[a,b\right]}是([a,b],≤)(\left[a,b\right],\leq)上的非減自映射。其中,f∣[a,b]f\mid_{\left[a,b\right]}表示函數ff在[a,b]\left[a,b\right]上的限制。

Lemma 2

任給完備格(A,≤)(A,\leq),f:A→Af:A\rightarrow A為(A,≤)(A,\leq)上的任一非減自映射,則ff有一個最大的不動點和一個最小的不動點。

註意,這裡確界的存在來自於完備格的定義,只要是完備格那麼根據定義其確界都在集合之內。這跟我們採用的是 R\mathbb{R} 還是 RN\mathbb{R}^{N} 作為例子是無關的,完備格這個偏序集使用的序關係不必與實數集或歐式空間上的序關係相同。

證明

任給完備格(A,≤)(A,\leq),f:A→Af:A\rightarrow A為(A,≤)(A,\leq)上的任一非減自映射。

我們令$D=\lbrace x\in A \mid x\leq f(x) \rbrace $, $E = \lbrace x\in A \mid x\geq f(x) \rbrace 。設。設B是是f$的所有不動點的集合。

取dd為DD的上確界(因為DD是AA的子集,根據(A,≤)(A,\leq)是完備格的定義,這個上確界是存在的),那麼我們有:對每一個 x∈Dx\in D,f(d)=f(sup⁡D)≥f(x)≥xf(d) = f(\sup D) \geq f(x) \geq x (因為ff是非減自映射,集合上確界的函數總是不小於集合中任何其他元素的函數)。所以f(d)f(d)也是DD的一個上界。從而f(d)≥df(d) \geq d,滿足我們對集合DD的設定(即$D=\lbrace x\in A\mid x\leq f(x) \rbrace ),即),即d \in D$ 。DD有屬於自身的上確界dd,所以dd是DD中的最大元。

另一方面,因為f(d)≥df(d) \geq d,利用ff的非減性,有f(f(d))≥f(d)f(f(d))\geq f(d),再次滿足我們對集合DD的設定,故而f(d)∈Df(d)\in D。而dd是DD的最大元,故d≥f(d)d\geq f(d)。結合我們上一步得到的f(d)≥df(d) \geq d有 f(d)=df(d)=d ,即dd是ff的一個不動點,d∈Bd \in B。

由於B=D∩EB=D\cap E從而B⊂DB \subset D,同時d∈Bd\in B所以DD的最大元dd 也是BB的最大元。即ff有最大不動點,這個最大不動點就是DD的上確界。

同理可證EE的下確界是ff的最小不動點。□\square

Th. 塔斯基不動點定理

完備格(A,≤)(A,\leq)上的任一非減自映射ff都有不動點,並且ff的全體不動點在≤\leq下組成一個完備格。

證明

Step 1. 由Lemma 2 ,我們知道函數 ff 在完備格 (A,≤)(A,\leq) 上存在一個不動點。

Step 2. 設ff的所有不動點的集合是 BB,我們證明(B,≤)(B,\leq)是一個完備格。

按照完備格的定義,我們只需證明在≤\leq下的偏序集BB的每個子集CC在BB中有上確界。

Step 3. 任選一個集合C⊂BC\subset B,取aa為CC在AA中的上確界,取bb為AA的最大元(即AA在AA中的上確界),根據完備格的定義,我們知道它們在 AA 中存在,而我們需要證明它們也在 CC 中。

因為對每一個x∈Cx \in C ,f(a)=f(sup⁡C)≥f(x)=xf(a) = f(\sup C) \geq f(x) = x,所以 f(a)f(a)是 CC 的上界。從而 f(a)≥sup⁡C=af(a) \geq \sup C = a 。

而bb為AA的最大元,從而f(b)≤bf(b) \leq b,所以按照Lemma 1(1)([a,b],≤)\left( \left[ a , b \right] , \leq \right),而按照Lemma 1(2),f∣[a,b]f\mid _{\left[ a ,b\right]}是完備格 ([a,b],≤)\left( \left[ a , b \right] , \leq \right)上的非減自映射。

按照Lemma 2 ,f∣[a,b]f \mid _{\left[ a , b \right]}在 ([a,b],≤)\left( \left[ a , b \right] , \leq\right) 上有一個最小的不動點,即滿足“不小於CC中任一元素”的最小不動點。從而這個不動點就是CC在BB中的上確界。□\square

脫胎於:
[1] Vohra R V. Advanced mathematical economics[M]. Routledge, 2004.
[2] Corbae D, Stinchcombe M B, Zeman J. An introduction to mathematical analysis for economic theory and econometrics[M]. Princeton University Press, 2009.