在一個博弈中是否存在只有兩個純策略而不存在混合策略的納什均衡？如果不存在請給出證明？

01-04

感覺題目問得有些不清楚，有可能是「博弈中所有均衡都是兩個純策略構成的」，也有可能是「博弈只存在兩個純策略納什均衡」。如果是前者，直接構造一個雙方都有嚴格佔優策略的2*2博弈就能解決問題，所以就當問的是後一個吧。這樣的博弈當然存在，如下圖所示。

不過，如果博弈參與者人數有限，每位參與者純策略個數有限，我們可以說明具有這樣性質的博弈測度為0。Wilson證明了幾乎所有有限博弈其納什均衡個數都是奇數，用的是單純性法Harsanyi做過一個特別優美的證明，技巧是去構造一個新的博弈，利用代數曲線方法說明原博弈除了一個特別的均衡外其它均衡必然成對出現。

另一個類似的性質來自Gul，Pearce和Stacchetti，他們證明了：對幾乎所有有限博弈，且有 $alpha$ 個純策略均衡，那麼這個博弈至少有 $alpha -1$ 個混合策略均衡。這也意味著對於幾乎所有有限博弈，如果它有2個純策略納什均衡，那它至少也應該有1個混合策略納什均衡。命題的嚴格證明使用了Lefschetz不動點的性質，這個定理意味著映射在不動點附近的導數有足夠好的性質，使得我們可以直接計算出不動點的數目。

最後，兩個命題中「幾乎所有」的含義都是博弈本身是regular的。博弈本身regular，意味著這個博弈中所有納什均衡都是regular的。Regularity的嚴格定義比較複雜，大致就是最優反應映射在均衡點附近可逆，嚴格定義可以看Van Damme書中regular equilibrium一章。可以證明，幾乎所有博弈的所有均衡都是regular的，並且，滿足regulaity條件的博弈是處處稠密的。這也是上面兩個定理的來源。

以上圖片來自Van Damme，更多相關內容同樣請參見Van Damme的Stability and Perfection of Nash Equilibrium，非常好的一本書！兩個命題的詳細證明請在參考文獻中找。

參考文獻：

Gül F, Pearce D, Stacchetti E. A bound on the proportion of pure strategy equilibria in generic games[J]. Mathematics of Operations Research, 1993, 18(3): 548-552.

Harsanyi J C. Oddness of the number of equilibrium points: a new proof[J]. International Journal of Game Theory, 1973, 2(1): 235-250.

Van Damme E. Stability and perfection of Nash equilibria[M]. Berlin: Springer-Verlag, 1991.

以下補充證明，這是是不是所有2×2博弈中，有兩個純策略納什均衡就一定有一個混合策略納什均衡？ - Manolo 的回答。

答主提的這個博弈是一經典例子，恰好落在@Richard Xu 給的奇數定理中「幾乎所有」之外，只有兩個納什均衡（正，正）和（反，反）。這個問題已見過不止一次，不如直接寫個證明。

奇數定理可分步作更嚴格表述：首先，幾乎所有博弈都是准強（quasi-strong）的；其次，幾乎所有博弈都是正則（regular）的；再次，所有正則和准強的博弈都只有奇數個均衡；因此，幾乎所有博弈都只有奇數個均衡。這裡選用證明來自Harsanyi（1973），完全是幾何的思路，非常優美。由於答主懶惰，大部分地方只給證明概要，強烈建議照著原文做一次。答案以下部分按符號說明、幾何直覺和證明主體順序排列。結尾簡單提及其它證明思路。

首先是符號，都是博弈論教材和書籍中常用記法。記有限博弈 $Gamma$ 中有 $n$ 位參與者，其中第 $i$ 位參與者策略空間是 $A_i$ ， $A_i$ 是有限集。令第 $k$ 位參與者策略集中第 $i$ 個策略為 $a_{i}^{k}$ ，則 $(a_1^{k_1},a_2^{k_2},...,a_n^{k_n})=(a_1^{k_1},a_1^{-1}) inprod_{i=1}^{n} A_i$ 是全體參與者的一組純策略。每個參與者以一定概率選取不同純策略稱為混合策略，我們記第 $k$ 位參與者在第 $i$ 個策略上賦予概率 $p_{i}^{k}$ ，則一組混合策略剖面可記為 $(p_1,p_2,...p_n) in P$ ，其中 $p_i$ 代表第 $i$ 個參與者在 $A_i$ 上選取的概率分布。令 $u^Gamma :prod_{i=1}^{n} A_i ightarrow R^n$ 代表參與者收益，則 $(a,u)$ 完整描述了有限博弈 $Gamma$ 。

Harsanyi證明思路如下：首先，構造一個新博弈 $L$ ，其中 $U^L_{i}(p_i)=sum_{j=1}^{left| A_i ight| }{log p_i^{j}}$ 。這是退化（degenerate）博弈，個體支付與他人決策無關，有唯一納什均衡 $p_1=p_2=...=p_{left| A_i ight| }$ 。接著再構造一個博弈 $Lambda (t)$ ，其中支付函數 $u^Lambda_{i} (p_i;t)=(1-t)u^Gamma_{i} (p_i)+tu^L_{i} (p_i)$ 。當 $t=1$ 時，這個博弈就是 $L$ ，有唯一均衡點；當 $t=0$ 時，這個博弈就是原博弈 $Gamma$ 。當 $t$ 在 $[0,1]$ 上左右移動時，策略空間和確定納什均衡所需條件交出一組代數曲線。 $Lambda (t)$ 全體混合策略空間 $P$ 是緊凸集，故這組曲線在策略空間內可以取到起點和終點。不妨令 $t=1$ 處均衡為起點，因此處雅可比行列式大於 $0$ ，根據隱函數定理知這不可能是終點，故 $t=0$ 處必然還有一個均衡構成曲線起點。如果 $t=0$ 處，即原博弈，還有其它均衡，它必然是代數曲線上一支的解析延長。又此分支向另一端解析延長不可能交邊界點於 $t=1$ 處，故這個交點必然在 $t=0$ 處，而這意味著除了之前那個構成起點均衡，其它納什均衡必然成對出現。為得到以上證明需要准強和正則條件，所以接下來說明「幾乎所有博弈都准強」和「幾乎所有博弈都正則」即可。證明前者需要說明非准強博弈構成歐氏空間中緊凸集邊界，再用Sard定理即可證明後者，這就構成了完整證明。

接下來開始描述證明梗概。考慮博弈 $Lambda (p_i;p_{-1},t)$ ，一組策略 $(p_1,p_2,...,p_n)$ 構成納什均衡條件為對所有參與者 $i$ ，有 $U^Lambda_{i} (p_i;p_{-1},t)geq U^Lambda_{i} (p_i^{$ 。記個體 $i$ 在策略 $p_i$ 中賦予正概率的所有純策略集合為 $C_i(p_i)$ ，稱支撐集。則上式可化簡為以下兩類條件：一是支撐集內部所有純策略收益相等，即對 $forall a_i^{k},a_i^{k^{$ ，有 $U^Lambda_{i} (a_i^{k};p_{-1},t)= U^Lambda_{i} (a_i^{k^{$ ，二是支撐集內任一策略收益至少和不在支撐集中純策略收益一樣大，即對 $forall a_i^{k} in C_i(p_i),a_i^{k^{$ ，有 $U^Lambda_{i} (a_i^{k};p_{-1},t)geq U^Lambda_{i} (a_i^{k^{$ 。如果這些不等式全是嚴格不等號，我們稱這一均衡是准強的。否則，我們稱這一均衡是極弱的（extra-weak）。

注意到當 $t>0$ 時，支撐集必然包含全體純策略，否則，不在支撐集中策略將給出給出 $-infty$ 收益。因此，當 $t>0$ 時，只需要第一個條件，再對概率做一點規定即可確保滿足條件的策略必然構成納什均衡，這等價於對任意參與者 $i$ 的第 $k$ 個策略，我們都有 $frac{partial U^Lambda_{i} (p_i;p_{-1},t) }{partial p_i^{k}} |_{sum_{i}{p_i^{k}}=1 }=0$ 。注意到 $U^Lambda_{i} (p_i;p_{-1},t)$ 對任意 $p_i^{k}$ 是嚴格凹的，二階條件自動滿足。所以上式給出了納什均衡的必要條件。在此基礎上，利用事實 $p_i^{k}=1-sum_{k=2}^{left| A_i ight|} {p_i^{k}}$ ，我們可進一步化簡均衡條件為如下形式：對任意參與者 $i$ 的第 $2$ 到第 $left| A_i ight|$ 個策略，有 $(1-t)p_i^{1}p_i^{k}[U_i^Lambda (a_i^k,p^{-1})-[U_i^Lambda (a_i^1,p^{-1})]+t(p_i^1-p_i^k)=0$ 。這裡有 $sum_{i=1}^{n}{left| A_i ight| } -n$ 個等式約束，加上 $sum_{k=1}^{left| A_i ight|} {p_i^{k}}=1$ 這 $n$ 個約束，共計 $sum_{i=1}^{n}{left| A_i ight| }$ 個等式約束。再加上對任意 $i$ 和 $k$ ， $p_i^k>0$ 這 $sum_{i=1}^{n}{left| A_i ight| }$ 個不等式約束，這 $2sum_{i=1}^{n}{left| A_i ight| }$ 個約束共同給出了 $t>0$ 時 $Lambda$ 一組均衡。

記 $R=P imes I, I=[0,1]$ ，這是一 $(sum_{i=1}^{n}{left| A_i ight| }+1)$ 維歐式子空間。令集體 $S$ 是全體滿足以上 $sum_{i=1}^{n}{left| A_i ight| }$ 個等式約束的全體 $(p,t)$ 的集合，在非退化情形里， $S$ 是一維代數射影。再令集合 $T$ 是具備以下特徵全體 $(t,p)$ 的集合：不僅滿足前 $sum_{i=1}^{n}{left| A_i ight| }$ 個約束，還滿足後 $sum_{i=1}^{n}{left| A_i ight| }$ 個不等式約束。這意味著 $T$ 給出了全體 $Lambda (t)$ 博弈的解。令 $E(t)$ 是博弈全體均衡集合，根據前面分析，可證原文定理1：當 $t=0$ 時， $E(t) subseteq T(t)$ ；當 $0<t leq 1$ 時， $E(t) =T(t)$ 。

我們現在定義正則。考慮對應 $mu :t ightarrow T(t)$ ，我們可以寫出其雅可比行列式：對任意個體 $i$ 的混合策略 $p_i$ ， $J(t,p)=frac{partial (F_1^{1},...F_i^{k},...,F_n^{k_n})}{partial (p_1^{1},...p_i^{k},...,p_n^{k_n})}$ 。其中對任意 $i$ ， $F_i^{1}(t,p)=sum_{i=1}^{n}{p_i^k} -1$ 。對 $2$ 到 $left| A_i ight|$ 之間 $k$ ， $F_i^{k}=(1-t)p_i^{1}p_i^{k}[U_i^Lambda (a_i^k,p^{-1})-[U_i^Lambda (a_i^1,p^{-1})]+t(p_i^1-p_i^k)$ 。考慮原博弈 $Gamma$ 的一個均衡 $p$ ，如果 $J(0,p)>0$ ，我們就稱均衡 $p$ 是正則的，否則就是非正則均衡。博弈 $Gamma$ 是正則的，當且僅當它的所有均衡都是正則均衡，雅可比行列式大於 $0$ 。

作者接下來引入幾個代數幾何中的定理，這裡簡要敘述。首先是原文定理2：記 $(x^0,x^*)$ 是 $u$ 維歐氏空間 $X^{ u}$ 中代數曲線 $S$ 上一段弧且 $x^0 e x^{ u}$ ，則 $(x^0,x^*)$ 可在 $x^0$ 或 $x^{ u}$ 處解析延長。證明按 $x^0$ 或 $x^{ u}$ 是否奇異點分類討論即可。非奇異點情形用隱函數定理馬上證出，奇異點情形用Puiseux定理構造收斂列即可。這一定理馬上導出關鍵引理：令 $S$ 是一代數曲線， $x$ 是任意一點，則通過 $x$ 點的 $S$ 的弧永遠是偶數條（可能不存在）且成對出現。成對出現意指：它們是彼此的解析延長而不是任何其它弧的解析延長。原文定理3如下：記 $(x^0,x^*)$ 是代數曲線 $S$ 的弧且整體坐落在有非空內部的緊凸集 $R$ 內。不失一般性，假設 $x^0$ 是 $R$ 的邊界點，那麼根據定理2和代數曲線性質，我們總可以在 $x^*$ 處作足夠遠的解析延長，使 $S$ 交 $R$ 於邊界點 $x^{00}$ 。

回憶前面記號， $R=P imes I$ 恰是一緊凸集，我們記其邊界為 $ar{R}$ ，再記解集合 $T$ 與 $ar R$ 交於 $ar T$ 考慮 $(t,p) in ar T$ ，如果 $(t,p)$ 不是孤立點，那麼以下二點必居其一且僅居其一： $(t,p)$ 是博弈 $Lambda(1)$ 的均衡； $(t,p)$ 是博弈 $Lambda(0)$ 的均衡。我們分兩步證明這一點。首先，當 $0<t leq1$ 時，所有均衡支集都包含所有策略，這意味著 $p$ 在 $P$ 內部。而這又意味著當 $0<t <1$ 時，納什均衡不可能是邊界點，故只有 $t=1$ 時均衡在邊界點上。當 $t=0$ 時，因 $(t,p)$ 不是孤立點，這意味著我們可以用一組序列 $(t_1,p_1),(t_2,p_2),...(t_3,p_3)$ 去逼近。又由於Debreu證明了對應 $mu ^*:t ightarrow E(t)$ 是上半連續的，故 $(t,p)$ 必然是一組均衡。再計算均衡 $(1,p)$ 處雅可比行列式可知 $J(1,p)>0$ ，故這是非奇異點，僅是代數曲線上一個分支的終點，以上證畢定理4和5.

命題6要求我們證明如果博弈 $Gamma$ 是准強且正則的，則 $t=0$ ，即博弈 $Gamma$ 處任意一個均衡都是非奇異點，且僅是代數曲線上一個分支的終點。令這個均衡是 $(0,p)$ ，如果 $p$ 在 $P$ 內部，直接使用定理5證法即證。如果不是這樣，說明部分純策略不在支撐集中。證明此命題等價於說明對任意不在支集中的策略 $k$ ，有 $frac{dp_i^k}{dt} |_{(0,p)}>0$ 。不失一般性，我們首先假設 $p_i^1>0$ （1），再將 $(1-t)p_i^{1}p_i^{k}[U_i^Lambda (a_i^k,p^{-1})-[U_i^Lambda (a_i^1,p^{-1})]+t(p_i^1-p_i^k)=0$ 兩邊對 $t$ 微分，再令 $t=p_i^k=0$ ，馬上得到 $p_i^{1}[U_i^Lambda (a_i^k,p^{-1})-[U_i^Lambda (a_i^1,p^{-1})]+p_i^1=1$ （2）。注意到因為策略 $k$ 不在支撐集中，又博弈是准強的，這意味著 $U^Lambda_{i} (a_i^{k};p_{-1},t)<U^Lambda_{i} (a_i^1;p_{-1},t)$ （3）。結合（1）（2）（3）就得到了 $frac{dp_i^k}{dt} |_{(0,p)}>0$ ，證畢。此時，我們已準備好了一切工具。

現在即可證明核心命題：令 $Gamma$ 是一準強且正則博弈，則 $Gamma$ 至多只有有限個納什均衡。 $Gamma$ 在 $(0,p)$ 處存在唯一突出均衡(distinguished equilibrium）與對應博弈 $Lambda$ 在 $(1,p^*)$ 處唯一均衡相互連接。 $Gamma$ 其它所有均衡均成對出現，彼此相互連接。因此，任一準強且正則均衡必然有奇數個均衡。我們首先證明有限性。回憶最開始 $T$ 的定義：代數射影 $S$ 和緊凸集 $R$ 的重合部分。這意味著 $T$ 至多只有有限個分支。又 $Gamma=Lambda(0)$ 的均衡必然坐落在 $T$ 某個分支終點上。分支數量有限，結合一個分支至多只有兩個端點，有限性證畢。再考慮博弈 $Lambda$ 在 $(1,p^*)$ 處唯一均衡，由於這個均衡是 $T$ 中一個分支的非奇異邊界點，這個分支必然可以延伸到 $t=0$ 處。否則，這個分支另一邊界點是 $(1,p^*)$ 自身，矛盾。不妨記 $t=0$ 處邊界點是 $(0,p)$ ，這就找到了前述突出均衡，第二部分證畢。假設 $t=0$ 處還有其它均衡，它們都是非奇異邊界點，恰好在一個分支上。由定理5可知它們不能延伸到自身和突出均衡處，由定理4和前述分析知它們不能延伸至 $0<t leq1$ 處，故其只能成對出現，證畢。

接下來只需要證明以下兩個命題：全體非准強博弈構成零測集；全體非正則博弈構成零測集。這裡思路簡單，符號繁瑣，只給概要。為證明前一命題，只要看到非准強意味著確定納什均衡條件中部分不等式取等號，而這意味著全體非准強博弈構成歐氏空間中一內部非空緊凸集合的邊界，必定是零測集。後一命題需要Sard定理：如果映射「足夠」連續可微，定義域中雅可比行列式為0點的像構成0測集。重排策略後構造映射再用Sard定理即證。綜合以上所有命題，我們即可得到 @Richard Xu回答的奇數定理：幾乎所有有限博弈都只有奇數個納什均衡。

這個定理最早由Wilson在1971給出，證明用單純形法，也很優美。不過自己覺得無論是優美程度還是幾何直覺，都屬Harsanyi證明更優，故介紹這個版本。再次強烈推薦閱讀原文。

在一個博弈中 是否存在只有兩個純策略 而不存在混合策略的納什均衡？如果不存在 請給出證明？

在一個博弈中是否存在只有兩個純策略而不存在混合策略的納什均衡？如果不存在請給出證明？