本頁使用了標題或全文手工轉換

奈許均衡點

維基百科,自由的百科全書
跳至導覽 跳至搜尋

奈許平衡英語: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

外部連結[編輯]