纳什均衡

此條目需要补充更多来源。 (2018年8月31日) 请协助補充多方面可靠来源以改善这篇条目，无法查证的内容可能會因為异议提出而被移除。 致使用者：请搜索一下条目的标题（来源搜索："纳什均衡" — 网页、新闻、书籍、学术、图像），以检查网络上是否存在该主题的更多可靠来源（判定指引）。

纳什均衡

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

上级分类	解決方案概念
话题方面	博弈论
得名自	约翰·福布斯·纳什
公式定義	${\displaystyle \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）中，假設每個參與者都知道其他參與者的均衡策略的情況下，沒有參與者可以透過改變自身策略使自身受益時的一個概念解。^[1]該術語以约翰·福布斯·納什命名。在博弈論中，如果每個參與者都選擇了自己的策略，並且沒有玩家可以透過改變策略而其他參與者保持不變而獲益，那麼當前的策略選擇的集合及其相應的結果構成了納什均衡。即若${\displaystyle p_{i}(s)=max_{r_{i}}[p_{i}(s;r_{i})]}$，則稱s為納許均衡點，其中：${\displaystyle p_{i}}$為參與者i的收穫（payoff），${\displaystyle s_{i}}$代表所有參與者之策略，${\displaystyle r_{i}}$代表參與者i的一種可能策略，${\displaystyle (s;r_{i})}$ 指參與者i單方面改變策略為${\displaystyle r_{i}}$。^[2]

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

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

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

其經典的例子就是囚徒困境。囚徒困境是一个非零和博弈。大意是：一个案子的两个嫌疑犯被分开审讯，警官分别告诉两个囚犯，如果你招供，而对方不招供，则你将被立即释放，而对方将被判刑10年；如果两人均招供，将均被判刑2年。如果两人均不招供，将最有利，只被判刑半年。于是两人同时陷入招供还是不招供的两难处境。但两人无法沟通，于是从各自的利益角度出发，都依据各自的理性而选择了招供，这种情况就称为纳什均衡点。这时个体的理性利益选择是与整体的理性利益选择不一致的。

基于经济学中“理性经济人”的前提假设，两个囚犯符合自己利益的选择是坦白招供，原本对双方都有利的策略不招供从而均被判刑半年就不会出现。事實上，这样两人都选择坦白的策略以及因此被判两年的结局被稱作是“纳什均衡”（也叫非合作均衡），換言之，在此情況下，無一參與者可以「獨自行動」（即單方面改變決定）而增加收穫。

第一，纳什的关于非合作博弈论的平衡不动点解（equilibrium/fixpoint）学术证明是非建設性的（non-constructive），就是说纳什用角谷不动点定理证明了平衡不动点解是存在的，但却不能指出以什么建設性的算法如何去达到这个平衡不动点解。这种非建設性的发现对现实生活裡的博弈的作用是有限的，即使知道平衡不动点解存在，在很多情况下卻找不到，因此仍不能解决问题。^{[來源請求]}

第二，纳什的非合作博弈论模型仅仅是突破了博弈论中的一个局限。一个更大的局限是，博弈论面对的往往是由几十亿节点的庞大对象构成的社会、经济等复杂行为，但冯·诺伊曼和纳什的研究是针对两三个节点的小规模博弈论（有人称之为tiny-scale toy case）。^{[來源請求]}

这个假设的不完善处，可能比假设大家都是合作的更严重。因为在经济学中，一个庞大社会裡的人极不可能全部都是合作的，非合作的情况通常在庞大对象的情形中更普遍，而在两三个节点的小规模经济中倒反而影响较小。既然改了合作前提为非合作前提，却仍然停留在两三个节点的小规模博弈论中，这是一个不可忽视的缺陷。MIT的一位计算机科学博士生的博士论文^[4]——获得2008年度美国计算机协会学位论文奖——认为经济学家的推测是错误的，找到纳什均衡点是几乎不可能的事。 目前担任MIT电机工程和计算机科学系助理教授的Constantinos Daskalakis与 UC伯克利的Christos Papadimitriou、英国利物浦大学的Paul Goldberg合作，证明对某些博弈来说，穷全世界所有计算机之力，在整个宇宙寿命的时间内也计算不出纳什均衡点。Daskalakis相信，计算机找不到，人类也不可能找到。纳什均衡属于NP问题，Daskalakis证明它属于NP问题的一个子集，不是通常认为的NP-完全问题，而是PPAD（英语：PPAD）-完全问题。这项研究成果被一些计算机科学家认为是十年来博弈论领域的最大进展。

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

• 囚徒困境
• 帕累托最优
• 博弈论
• P/NP问题
• PPAD（英语：PPAD (complexity)）

• 纳什博弈论的原理与应用 （页面存档备份，存于互联网档案馆） 北京晚报 (2002年3月21日)