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

納什均衡點

维基百科,自由的百科全书
跳转至: 导航搜索

納什平衡,又稱為非合作賽局平衡,是博弈论的一個重要概念,以约翰·納什命名。

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

例子[编辑]

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

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

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

学术争议和批评[编辑]

第一,纳什的关于非合作博弈论的平衡不动点解(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. ^ p_i(s)= max_{r_i} [ p_i(s; r_i)], ,則納什稱 s 為平衡點(Equilibrium point)。----其中 p_i為參與者 i 的收穫(payoff),s_i代表所有參與者之策略,r_i代表參與者 i 的 一種可能策略,(s; r_i) 指參與者 i 單方面改變策 略成 r_i。 --- P.287, Annals of Mathematics 1951
  2. ^ Constantinos Daskalakis, The Complexity of Nash Equilibria

參考[编辑]

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

外部链接[编辑]