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

奈許均衡點

維基百科,自由的百科全書
前往: 導覽搜尋

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

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

例子[編輯]

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

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

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

學術爭議和批評[編輯]

第一,奈許的關於非合作博弈論的平衡不動點解(equilibrium/fixpoint)學術證明是非構造性的(non-constructive),就是說奈許用角谷靜夫不動點定理英語Kakutani fixed point theorem證明了平衡不動點解是存在的,但卻不能指出以什麼構造算法如何去達到這個平衡不動點解。這種非構造性的發現對現實生活里的博弈的作用是有限的,即使知道平衡不動點解存在,在很多情況下卻找不到,因此仍不能解決問題。[來源請求]

第二,奈許的非合作博弈論模型僅僅是突破了博弈論中的一個局限。一個更大的局限是,博弈論面對的往往是由幾十億節點的龐大對象構成的社會、經濟等複雜行為,但馮·諾伊曼和奈許的研究是針對兩三個節點的小規模博弈論(有人稱之為tiny-scale toy case)。[來源請求]

這個假設的不完善處,可能比假設大家都是合作的更嚴重。因為在經濟學里,一個龐大社會裡的人極不可能全部都是合作的,非合作的情況通常在龐大對象的情形中更普遍,而在兩三個節點的小規模經濟中倒反而影響較小。既然改了合作前提為非合作前提,卻仍然停留在兩三個節點的小規模博弈論中,這是一個不可忽視的缺陷。MIT的一位計算機科學博士生的博士論文[2]——獲得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. ^ Constantinos Daskalakis, The Complexity of Nash Equilibria

參考[編輯]

《Non-Cooperative Games》,約翰 · 奈許 , The Annals of Mathematics 1951

外部連結[編輯]