您當前的位置：首頁 > 文化

不動點定理（Fixed Points Theorem）

作者：由 economics-lover 發表于文化時間：2021-12-02

這篇筆記整理經濟學中常用的四大不動點定理：Brouwer Fixed Points Theorem（布勞威爾不動點定理）、Kakutani Fixed Points Theorem（角谷靜夫不動點定理）、壓縮對映定理和Tarski‘s Fixed Point Theorem。這四大不動點定理在證明均衡存在性和唯一性時經常起著關鍵作用。這篇筆記將分別使用Brouwer Fixed Points Theorem（布勞威爾不動點定理）、Kakutani Fixed Points Theorem（角谷靜夫不動點定理）證明納什均衡存在性和一般均衡存在性。並使用Tarski’s Fixed Point Theorem證明一類策略互補博弈的純策略納什均衡存在性。

Brouwer Fixed Points Theorem（布勞威爾不動點定理）

關於如何使用

Brouwer Fixed Points Theorem

證明納什均衡存在性，請參加下列答主的回答：

此處我自己為了練習，寫一個兩個人版本的證明哈（並不嚴謹，只是為了熟悉直覺）。

參與人有兩個

，並且參與人

的純策略空間

$S=S_i\times S_j$

是有限集合，

是一個純策略組，

$\Sigma=\Sigma_i\times \Sigma_j$

是個體的混合策略空間，

$\sigma=(\sigma_i,\sigma_j)=((\sigma_i(a_1),...,\sigma_i(a_{|S_i|})),( \sigma_j(a_1),...,\sigma_j(a_{|S_j|}) ))$

是一個混合策略組。

一個混合策略給個體帶來的效用是：

$u_i(\sigma)=\sum_{(s_i,s_j)\in S} \sigma_i(s_i)\sigma_j(s_j)u_i(s_i,s_j) \\$

參與人

的效用函式

是連續的，那麼一定存在一個混合策略納什均衡

$\sigma^*=(\sigma_i^*,\sigma_j^*)$

。

證明：定義：

$\phi_{i,s_i}(\sigma)=\max\{0,u_i(s_i,\sigma_{-i})-u_i(\sigma)\}$

上述函式反應了個體

更換策略的傾向。

下面定義從

$\Sigma$

到

$\Sigma$

的對映

，

是一個輸入變數為

$|S_i|\times |S_j|$

維，輸出變數為

$|S_i|\times |S_j|$

的函式。

即任取

$\sigma=(\sigma_i,\sigma_j)\in \Sigma$

，都有

$f(\sigma)\in \Sigma$

。

對映

的構造是核心！

$\sigma_i$

可以發現，

$0\leq \sigma_i$

，並且

$\sum_{a_i\in S_i}\sigma_i$

，對於

而言同理，因此確實是自身到自身的對映。

根據上式可知，如果給定

策略不變，

將

$\sigma_i$

變為

的效用更高，那麼在新的局勢裡面，或者說給定

$\sigma$

，在

$f(\sigma)$

中，

給純策略

賦予的權重會更大，反之則會更小。

因為

$\Sigma$

是一個緊凸集，而

是一個連續函式，因此一定存在不動點

$\sigma^*=f(\sigma^*)$

。下面證明

$\sigma^*$

是納什均衡它是

的一個不動點。

先證必要性，顯然，如果

$\sigma^*$

是納什均衡，那麼

$\sigma_i$

，那麼

$\forall a_i\in S_i$

，

$\phi_{i,a_i}(\sigma^*)=0$

，即

$\sigma_i$

，即

$\sigma^*$

是一個不動點。

即

$\forall s_i\in S_i$

，均有：

$\sigma_i^*(s_i)=\frac{\sigma_i^*(s_i)+\phi_{i,s_i}(\sigma^*)}{1+\sum_{a_i\in S_i}\phi_{i,a_i} (\sigma^*) ) }$

我們的核心實現證明，存在一個

$a_i\in S_i$

同時滿足

$\sigma_i^*(s_i)>0$

且

$\phi_{i,s_i}(\sigma^*)=0$

，一旦證明了這個。我們就能發現上式的分母中

$\sum_{a_i\in S_i}\phi_{i,a_i} (\sigma^*)) =0$

，即給定對方的混合策略，任何個體都不願意偏離當前的策略到一個純策略上（當然，這裡還沒有論證偏離到一個混合策略會不會更好是吧，不過實際上只需要論證純策略即可，到時候前面再補充一下這個就行）

那麼是否存在呢？

假設給定

$\sigma_j^*$

，

$\sigma_i^*$

的策略實際上是一個純策略，即對於某個

$a_i\in S_i$

，

$\sigma_i^*(a_i)=1$

，那麼顯然滿足上面的我們的要求。

假設

$\sigma_i^*$

以正的機率分配到多於一個純策略上，即分配在了

$A_i\subseteq S_i$

上。

個體

採用純策略

$a_i \in A_i$

的效用是

$u_i(a_i,\sigma_j^*)=\sum_{s_j\in S} \sigma_j^*(s_j)u_i(a_i,s_j)$

至少存在一個

$a_i\in S_i$

，使得

$u_i(a,\sigma_{j}^*)-u_i(\sigma^*)\leq 0$

為什麼怎麼說呢，對每一個

$a_i\in A_i$

，計算

$u_i(a_i,\sigma_j^*)$

，一定有一個最小的

$u_i(a_{min},\sigma_j^*)$

，那麼由於

$u_i(\sigma^*)$

$\phi_{i,a_i}(\sigma)=0$

是不同的

$a_i\in A_i$

的加權平均，如果我們使用最小的

$a_{min}$

，那麼一定有：

$u_i(a,\sigma_{j}^*)-u_i(\sigma^*)\leq 0$

。這個時候，就找到了這麼一個

，同時滿足

$\sigma_i^*(s_i)>0$

且

$\phi_{i,s_i}(\sigma^*)=0$

，一旦證明了這個。我們就能發現上式的分母中

$\sum_{a_i\in S_i}\phi_{i,a_i} (\sigma^*)) =0$

，這個式子的每一項都必須等於0。也就是說，當對方採取混合策略

$\sigma_j$

時，

不能透過偏離到一個純策略獲得更高效用。因此，

$\sigma^*$

是一個納什均衡。

當然，推廣到有限多個人也是類似的證明。有時間補充到

個人的情況。核心還是如何構造

，這是最為關鍵的一步！它的應用可見我的另一篇筆記：

當然，這裡我還有一個疑惑？為什麼Nash當時不使用下面的最優反應函式作為

的構造呢？這個似乎更為直接：

上面的似乎也不需要多想，就能構造出來了。但是Nash構造的需要比較高的技巧。

Kakutani Fixed Points Theorem（角谷靜夫不動點定理）

該定理比Brouwer Fixed Points Theorem更為強大，但是理解起來也更為困難，需要稍微熟悉一下凸集、閉集這些東西。首先對其每一部分進行解讀。我們的研究空間均為歐式空間

$\mathbb{R}^n$

。

緊集是一個有界閉集，凸集就是如果兩個點在裡面，那麼其加權平均也在裡面。

是一個集值函式（multifunction），即任取

$x\in K$

，

是一個集合而不是一個點。根據定義，這個集合是一個緊集、凸集，且

$F(x)\subseteq K$

。

上半連續（upper semicontinuous）與下半連續（lower semicontinuous）：

直覺上來講：

上半連續與下半連續的兩個影象：

關於函式

的上半連續性和其像之間的關係，有：

納什均衡存在性

導師說，使用的工具越高階，就越不需要複雜的構造計較。如果個體的效用函式

$u_i(\sigma_i,\sigma_{-i})$

是連續函式，定義域

$\Sigma \subset \mathbb{R}^{n\times n}_{+}$

是一個非空緊凸集。

根據伯格極大值定理，

$\forall \sigma\in \Sigma$

，個體

的最優反應對應

$B_i(\sigma)=arg\max_{\sigma_i\in \Sigma_i} u_i(\sigma_i,\sigma_{-i})$

是非空的，緊值的，上半連續的。當然，肯定也是凸值的，且

$B_i(\sigma)\subseteq \Sigma_i$

，或者說

$B_i(\sigma)\in 2^{\Sigma_i}$

。

函式：

$B(\sigma)=(B_1(\sigma),...,B_n(\sigma))$

的定義域是

$\Sigma$

，值域是

$2^{\Sigma}$

因此一定存在一個不動點，使得：

$\sigma^*\in B(\sigma^*)$

，因此純策略納什均衡一定存在。

之後將補充如何使用Kakutani Fixed Points Theorem證明一般均衡存在性

壓縮對映定理和Tarski‘s Fixed Point Theorem作為之後進一步學習時整理！

標簽： fixed Theorem 不動點 points 納什

上一篇:我太鋒利了，的確強人所難。我做不做得到，是衡量一切選擇的第一準則。

下一篇：藏汙納垢、危害健康，廚房裡最該扔掉的東西

猜你喜歡