是不是所有 2×2 博弈中，有兩個純策略納什均衡就一定有一個混合策略納什均衡？

01-04

第一，如何找過個策略納什均衡。第二，如題。第三，如果ab兩個玩家，只有兩個同時選擇正面時才能沒人得到1的好處，否則沒人能得到好處。就是除了（正，正）是（1，1）。（正，反），（反，正），（反，反）都是（0,0）。請問這個博弈中的，混合策略納什均衡是什麼？@董可人

答主提的這個博弈是一經典例子，恰好落在@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證明更優，故介紹這個版本。再次強烈推薦閱讀原文。

參考文獻：

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

Wilson R. Computing equilibria of n-person games[J]. SIAM Journal on Applied Mathematics, 1971, 21(1): 80-87.

奇數定理：幾乎所有有限策略博弈都有奇數個納什均衡。

從我有限的科普級知識來看顯然大家趨向於選一【前提是我選一併不付出額外代價】

如果雙方信息不能互通並假設兩人理性無額外成本那麼一是最佳選擇

因為在對方選一時【共贏】

在對方選二時【我也不虧】

那麼我選一就是最佳不管對方選什麼而且根據我的分析對方必然選一

然後因為兩邊的選擇與後果是對稱的那麼大概就會有奇數個均衡解吧【並不是很清楚這個在兩邊的選擇不對稱是是否能證】

最後題主你有字打錯了【每人】打成了【沒人】

僅答第三問。

兩個參與者在進行決策時。均會考慮到選正的收益上限為1，收益下限為0；選反的收益上限為0，收益下限為0，所以兩個參與者均會選擇正。

混合策略納什均衡就是加上一個概率算一下，結果是一樣的。

這個問題中ms和ps相同，都是正正，ms寫出來是（1*正，1*正），ps是（正，正）

正好在學博弈論，初學者，強答一個吧

第一問

找納什均衡最通俗的辦法就是:猜對手的策略，然後針對自己的猜測找佔優策略，對其他所有player採取這個方法，最後得出解，但前提是猜測正確

檢驗起來也不複雜，要用數學符號表示可能會非常複雜，用文字也可以描述，我用自己的話概括了一下:

1你們都這麼玩，誰不這麼玩就傻逼了，不信自己試

2咱們都這麼玩，對大家都好

2這麼玩結果最好，再給我一次機會選，我也不換

但是這些辦法仍然有一定局限性，解決簡單問題還是適用的

第二問是的

第三問正，正;反，反

所有純策略其實都是混合策略