納許均衡

納許均衡

定理、​解決方案概念、​平衡類型

上級分類	解決方案概念
話題方面	賽局理論
得名自	約翰·富比士·納許
公式定義	$\forall i,x_{i}\in S_{i}f_{i}(x_{i}^{*},x_{-i}^{*})\geq f_{i}(x_{i},x_{-i}^{*}).$
理論提出者	約翰·富比士·納許

「納許均衡」的各地常用名稱
中國大陸	納什均衡
臺灣	納許均衡、奈許均衡
港澳	納殊均衡、拿殊均衡

在賽局理論中，納許均衡（英語：Nash equilibrium，或稱納許均衡點）是指在包含兩個或以上參與者的非合作賽局（Non-cooperative game）中，假設每個參與者都知道其他參與者的均衡策略的情況下，沒有參與者可以透過改變自身策略使自身受益時的一個概念解。該術語以約翰·富比士·納許命名。在賽局理論中，如果每個參與者都選擇了自己的策略，並且沒有玩家可以透過改變策略而其他參與者保持不變而獲益，那麼當前的策略選擇的集合及其相應的結果構成了納許均衡。即若$p_{i}(s)=max_{r_{i}}[p_{i}(s;r_{i})]$，則稱s為納許均衡點，其中：$p_{i}$為參與者i的收穫（payoff），$s_{i}$代表所有參與者之策略，$r_{i}$代表參與者i的一種可能策略，$(s;r_{i})$ 指參與者i單方面改變策略為$r_{i}$。

發展歷史

納許平衡的命名來由為美國數學家約翰·富比士·納許。該概念的其中一個版本已知最早於1838年被安托萬·奧古斯丁·庫爾諾運用於他的寡占理論中。在庫爾諾的理論中，商行們需選擇合適的產量以獲得最大利潤，然而一家商行的理想產量取決於其他商行的產量。當每一家商行的理想產量都需要根據已知其他商行的產量來做出調整，以達到最大利潤時，一種純策略的納許平衡——庫爾諾平衡就形成了。在分析平衡穩定性的過程中，庫爾諾還提出了最適反應動態（或最佳反應動態）的概念。然而納許對平衡的定義比庫爾諾的更為廣泛，也比帕勒托效率平衡的定義更為廣泛，因為納許的定義沒有針對「形成哪種平衡最為理想」作出評判。

與此相反，現代賽局理論中的納許平衡概念是用混合策略來定義的，其中的參與者傾向於符合機率分布，而非動作合理性。約翰·馮·諾伊曼和摩根斯頓在1944年出版的《賽局理論與經濟行為》（英語：Theory of Games and Economic Behavior）一書中提出混合策略納許平衡的概念，然而他們的分析侷限於零和賽局這一特例。書中表明對於任何零和賽局，只要動作集合有限，就存在混合策略納許平衡。納許在1951年發表了文章《非合作賽局》（英語：Non-Cooperative Games），意在定義上述這種混合策略納許平衡，並證明這樣一場賽局至少存在一個（混合策略）納許平衡。之所以納許對上述存在性的證明能夠比馮·諾伊曼的更具普遍性，關鍵在於他對平衡所下的定義。根據納許的說法，「平衡點是當其餘參與者的策略保持不變時，能夠令參與者的混合策略極大化其收益的一個n元組」。在1950年發表的一篇論文中，僅憑著將問題置於該框架中的做法，納許就成功運用了角谷不動點定理；在1951年發表的改版論文中，納許運用了布勞威爾不動點定理。上述兩者共同證明了，存在至少一種混合策略的策略組合（英語：strategy profile），能夠針對有限參與者賽局（不一定是零和賽局）的情況自我映射，即一種不需要為提高收益而變更策略的策略組合。

自納許平衡概念形成以來，已經有賽局理論家發現，在某些情況下該概念所做的預測頗具誤導性（或缺乏唯一性）。這些理論家提出了許多相關的解概念（也稱為納許平衡的「微調」），意在彌補納許平衡概念中已知的瑕疵。其中一個尤為重要的問題是，某些納許平衡所依據的並非「實質性」威脅。1965年賴因哈德·澤爾騰提出子賽局完全平衡，以排除基於非實質性威脅的平衡。納許平衡的其他延伸概念闡述了重複賽局產生的影響，或資訊不完整對賽局的影響。然而，後人的微調與延伸都用到了一個關鍵性理解，也是納許概念的存在基礎：一切平衡概念都是在分析在每個參與者都考慮其他參與者的決定的情況下，最終選擇是什麼。

例子

其經典的例子就是囚犯困境。囚犯困境是一個非零和賽局。大意是：一個案子的兩個嫌疑犯被分開審訊，警官分別告訴兩個囚犯，如果你招供，而對方不招供，則你將被立即釋放，而對方將被判刑10年；如果兩人均招供，將均被判刑2年。如果兩人均不招供，將最有利，只被判刑半年。於是兩人同時陷入招供還是不招供的兩難處境。但兩人無法溝通，於是從各自的利益角度出發，都依據各自的理性而選擇了招供，這種情況就稱為納許均衡點。這時個體的理性利益選擇是與整體的理性利益選擇不一致的。

囚犯的賽局矩陣		囚犯乙
		招供	不招供
囚犯甲	招供	各判刑2年	甲立即釋放，乙判刑10年
	不招供	甲判刑10年，乙立即釋放	各判刑半年

基於經濟學中「理性經濟人」的前提假設，兩個囚犯符合自己利益的選擇是坦白招供，原本對雙方都有利的策略不招供從而均被判刑半年就不會出現。事實上，這樣兩人都選擇坦白的策略以及因此被判兩年的結局被稱作是「納許均衡」（也叫非合作均衡），換言之，在此情況下，無一參與者可以「獨自行動」（即單方面改變決定）而增加收穫。

學術爭議和批評

第一，納許的關於非合作賽局理論的平衡不動點解（equilibrium/fixpoint）學術證明是非建設性的（non-constructive），就是說納許用角谷不動點定理證明了平衡不動點解是存在的，但卻不能指出以什麼建設性的算法如何去達到這個平衡不動點解。這種非建設性的發現對現實生活裡的賽局的作用是有限的，即使知道平衡不動點解存在，在很多情況下卻找不到，因此仍不能解決問題。

第二，納許的非合作賽局理論模型僅僅是突破了賽局理論中的一個局限。一個更大的局限是，賽局理論面對的往往是由幾十億節點的龐大對象構成的社會、經濟等複雜行為，但馮·諾伊曼和納許的研究是針對兩三個節點的小規模賽局理論（有人稱之為tiny-scale toy case）。

這個假設的不完善處，可能比假設大家都是合作的更嚴重。因為在經濟學中，一個龐大社會裡的人極不可能全部都是合作的，非合作的情況通常在龐大對象的情形中更普遍，而在兩三個節點的小規模經濟中倒反而影響較小。既然改了合作前提為非合作前提，卻仍然停留在兩三個節點的小規模賽局理論中，這是一個不可忽視的缺陷。MIT的一位計算機科學博士生的博士論文——獲得2008年度美國計算機協會學位論文獎——認為經濟學家的推測是錯誤的，找到納許均衡點是幾乎不可能的事。 目前擔任MIT電機工程和計算機科學系助理教授的Constantinos Daskalakis與 UC伯克利的Christos Papadimitriou、英國利物浦大學的Paul Goldberg合作，證明對某些賽局來說，窮全世界所有計算機之力，在整個宇宙壽命的時間內也計算不出納許均衡點。Daskalakis相信，計算機找不到，人類也不可能找到。納許均衡屬於NP問題，Daskalakis證明它屬於NP問題的一個子集，不是通常認為的NP-完全問題，而是PPAD-完全問題。這項研究成果被一些計算機科學家認為是十年來賽局理論領域的最大進展。

不過在同一篇論文裡，Daskalakis也指出，在參與者匿名的情況下，則僅需多項式時間即可逼近納許均衡。

參見

• 囚犯困境
• 帕雷托最適
• 賽局理論
• P/NP問題
• PPAD

參考書目

• Non-Cooperative Games, 約翰·納許, The Annals of Mathematics 1951

外部連結

• 納許賽局理論的原理與應用 （頁面存檔備份，存於網際網路檔案館） 北京晚報 (2002年3月21日)