本页使用了标题或全文手工转换

納什均衡點

维基百科,自由的百科全书
(重定向自纳什均衡
跳到导航 跳到搜索

納什平衡英语:Nash equilibrium),又稱為非合作賽局博弈,是在非合作博弈Non-cooperative game)狀況下的一個概念解,在博弈论中有重要地位,以约翰·納什命名。

如果某情況下無一參與者可以通过獨自行動而增加收益,則此策略組合被稱為納什均衡點[1]

發展歷史[编辑]

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

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

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

例子[编辑]

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

囚犯的博弈矩阵 囚犯乙
招供 不招供
囚犯甲 招供 各判刑2年 甲立即释放,乙判刑10年
不招供 甲判刑10年,乙立即释放 各判刑半年

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

学术争议和批评[编辑]

第一,纳什的关于非合作博弈论的平衡不动点解(equilibrium/fixpoint)学术证明是非构造性的(non-constructive),就是说纳什用角谷静夫不动点定理英语Kakutani fixed point theorem证明了平衡不动点解是存在的,但却不能指出以什么构造算法如何去达到这个平衡不动点解。这种非构造性的发现对现实生活里的博弈的作用是有限的,即使知道平衡不动点解存在,在很多情况下卻找不到,因此仍不能解决问题。[來源請求]

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

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

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

相關鏈接[编辑]

[编辑]

  1. ^ , ,則納什稱 s 為平衡點(Equilibrium point)。----其中 為參與者 i 的收穫(payoff),代表所有參與者之策略,代表參與者 i 的 一種可能策略, 指參與者 i 單方面改變策 略成 。 --- P.287, Annals of Mathematics 1951
  2. ^ Carmona, Guilherme; Podczeck, Konrad. On the existence of pure-strategy equilibria in large games. Journal of Economic Theory. 2009-05, 144 (3): 1300–1319. ISSN 0022-0531. doi:10.1016/j.jet.2008.11.009. 
  3. ^ Constantinos Daskalakis, The Complexity of Nash Equilibria

參考[编辑]

《Non-Cooperative Games》,约翰 · 纳什 , The Annals of Mathematics 1951

外部链接[编辑]