纳什均衡点,应怎样理解

纳什平衡,又称为非合作赛局平衡,是博弈论的一个重要概念,以约翰·纳什命名.
如果某情况下无一参与者可以独自行动而增加收益,则此策略组合被称为纳什均衡点
经典的例子就是囚徒困境,囚徒困境是一个非零和博弈. 大意是：一个案子的两个嫌疑犯被分开审讯,警官分别告诉两个囚犯,如果你招供,而对方不招供,则你将被立即释放,而对方将被判刑十年；如果两人均招供,将均被判刑两年.如果两人均不招供,将最有利,只被判刑半年. 于是,两人同时陷入招供还是不招供的两难处境. 但两人无法沟通,于是从各自的利益角度出发,都依据各自的理性而选择了招供, 这种情况就称为纳氏均衡点. 这时,个体的理性利益选择是与整体的理性利益选择不一致的.
学术争议和批评
第一,纳什（Nash）的关于非合作（non-cooperative）博弈论的平衡不动点解（equilibrium/fixpoint）学术证明是非构造性的（non-constructive）,就是说纳什用角谷静夫不动点定理（Kakutani fixed point theorem） 证明了平衡不动点解是存在的,但却不能指出以什么构造算法如何去达到这个平衡不动点解.这种非构造性的发现对现实生活里的博弈的作用是有限的,即使知道平衡不动点解存在,在很多情况下却找不到,因此仍不能解决问题.[来源请求]在数学意义上,纳什并没有超越角谷静夫不动点定理.
经过《美丽心灵》的Sylvia Nasar（书作者）和Ron Howard（电影作者）这样的主流媒体的介入,角谷静夫（Kakutani）在这些人的作品里被完全忽略.有人认为,“纳什平衡”（Nash equilibrium）的更合适的名字应该叫作“角谷静夫—纳什博弈论不动点”（Kakutani-Nash game-theoretic fixed point）或“角谷静夫—纳什平衡”（Kakutani-Nash equilibrium）,没有角谷静夫不动点定理,纳什的证明没有多大学术意义.《美丽心灵》完全忽视角谷静夫之关键贡献的作法有待商榷.
第二,纳什的非合作（non-cooperative）博弈论模型仅仅是突破了博弈论中的一个局限.一个更大的局限是,博弈论面对的往往是由几十亿节点的庞大对象构成的社会、经济等复杂行为,但冯·诺伊曼（Von Neumann）和纳什的研究是针对两三个节点的小规模博弈论（有人称之为tiny-scale toy case）.[来源请求]
这个假设的不完善处,可能比假设大家都是合作的（cooperative）更严重.因为在经济学里,一个庞大社会里的人极不可能全部都是合作的,非合作的情况通常在庞大对象的情形中更普遍,而在两三个节点的小规模经济中倒反而影响较小.既然改了合作前提为非合作前提,却仍然停留在两三个节点的小规模博弈论中,这是一个不可忽视的缺陷.最近香港城市大学和北京清华大学的学者群邓小铁、姚期智在基于复杂度理论的大规模博弈论上有所进展.
MIT的一位计算机科学博士生的博士论文(PDF http://people.csail.mit.edu/costis/thesis.pdf )——获得2008年度美国计算机协会学位论文奖——认为经济学家的推测是错误的,找到纳什均衡点是几乎不可能的事. 目前担任MIT电机工程和计算机科学系助理教授的Constantinos Daskalakis与 UC伯克利的Christos Papadimitriou、英国利物浦大学的Paul Goldberg合作,证明对某些博弈来说,穷全世界所有计算机之力,在整个宇宙寿命的时间内也计算不出纳什均衡点.Daskalakis相信,计算机找不到,人类也不可能找到.纳什均衡属于NP问题,Daskalakis证明它属于NP问题的一个子集,不是通常认为的NP-完全问题,而是PPAD-完全问题.这项研究成果被一些计算机科学家认为是十年来博弈论领域的最大进展.
不过在同一篇论文里,Daskalakis也指出,在参与者匿名的情况下,则仅需多项式时间即可逼近纳什均衡.
现实的例子
上述例子可能显得不甚自然,但现实中,无论是人类社会或大自然都可以找到类似囚徒困境的例子,将结果划成同样的支付矩阵.社会科学中的经济学、政治学和社会学,以及自然科学的动物行动学、进化生物学等学科,都可以用囚徒困境分析,模拟生物面对无止境的囚徒困境博弈.囚徒困境可以广为使用,说明这种博弈的重要性.以下为各界例子：
[编辑] 政治学例子：军备竞赛
在政治学中,两国之间的军备竞赛可以用囚徒困境来描述.两国都可以声称有两种选择：增加军备（背叛）、或是达成削减武器协议（合作）.两国都无法肯定对方会遵守协议,因此两国最终会倾向增加军备.似乎自相矛盾的是,虽然增加军备会是两国的“理性”行为,但结果却显得“非理性”（例如会对经济造成都有损坏等）.这可视作遏制理论的推论,就是以强大的军事力量来遏制对方的进攻,以达到和平.
[编辑] 经济学例子：关税战
两个国家,在关税上可以有以两个选择:
提高关税,以保护自己的商品.（背叛）
与对方达成关税协定,降低关税以利各自商品流通.（合作）
当一国因某些因素不遵守关税协定,而独自提高关税（背叛）时,另一国也会作出同样反应（亦背叛）,这就引发了关税战,两国的商品失去了对方的市场,对本身经济也造成损害（共同背叛的结果）.然后二国又重新达成关税协定.（重复博弈的结果是将发现共同合作利益最大.）
[编辑] 商业例子：广告战
商业活动中亦会出现各种囚徒困境例子.以广告竞争为例.
两个公司互相竞争,二公司的广告互相影响,即一公司的广告较被顾客接受则会夺取对方的部分收入.但若二者同时期发出质量类似的广告,收入增加很少但成本增加.但若不提高广告质量,生意又会被对方夺走.
此二公司可以有二选择：
互相达成协议,减少广告的开支.（合作）
增加广告开支,设法提升广告的质量,压倒对方.（背叛）
若二公司不信任对方,无法合作,背叛成为支配性策略时,二公司将陷入广告战,而广告成本的增加损害了二公司的收益,这就是陷入囚徒困境.在现实中,要二互相竞争的公司达成合作协议是较为困难的,多数都会陷入囚徒困境中.
[编辑] 自行车赛例子
自行车赛事的比赛策略也是一种博弈,而其结果可用囚徒困境的研究成果解释.例如每年都举办的环法自行车赛中有以下情况：选手们在到终点前的路程常以大队伍（英文:Peloton）方式前进,他们采取这策略是为了令自己不至于太落后,又出力适中.而最前方的选手在迎风时是最费力的,所以选择在前方是最差的策略.通常会发生这样的情况,大家起先都不愿意向前（共同背叛）,这使得全体速度很慢,而后通常会有二或多位选手骑到前面,然后一段时间内互相交换最前方位置,以分担风的阻力（共同合作）,使得全体的速度有所提升,而这时如果前方的其中一人试图一直保持前方位置（背叛）,其他选手以及大队伍就会赶上（共同背叛）.而通常的情况是,在最前面次数最多的选手（合作）通常会到最后被落后的选手赶上（背叛）,因为后面的选手骑在前面选手的冲流之中,比较不费力.
[编辑] 与囚徒困境相关的各事件
[编辑] 异想
威廉·庞德斯通（William Poundstone）在他的著作中,以一新西兰的例子来说明囚徒困境.在新西兰,报亭既无管理员也不上锁,买报纸的人自行放下钱后拿走报纸.当然某些人可能取走报纸却不付钱（背叛）,但由于大家认识到如果每个人都偷窃报纸（共同背叛）会造成以后不方便的有害结果,这种情形很少发生.这例子特别之处是新西兰人并没有被任何其他因素影响而能脱离囚徒困境.并没有任何人特别去注意报亭,人们守规则是为了避免共同背叛带来的恶果.这种避免囚徒困境的大家共同的推理或想法被称为“异想（magical thinking）”.[3]
[编辑] “认罪减刑”不可行
囚徒困境的结论是许多国家中认罪减刑（英文：plea bargain）被禁止的原因之一.囚徒困境带来的结论是：如果有二个罪犯,其中一人犯罪而另外一人是无辜的,犯罪者会为了减刑坦白一切甚至冤枉清白者（单独背叛）.最糟糕的情况是,如果他们二人都被判入狱,坦白的犯罪者刑期少,坚持无罪的冤枉者刑期反而更多.
[编辑] 公用品悲剧
现实的博弈参与者不只一方,会有多方参与的囚徒困境.加勒特·詹姆斯·哈丁（Garrett James Hardin）的公用品悲剧就是一例：“公用品悲剧是指凡是属于最多数人的公共财产常常是最少受人照顾的事物”,例如渔业,公海中的鱼是属于公共的,而在本身不滥捕其他人也滥捕的思想下,渔民会没有节制的大捞特捞,结果海洋生态破坏,渔民的生计也受影响（共同背叛的结果）.但是,多方囚徒困境的提法有待商榷,因为其总是可以被分解为一组组经典的二方囚徒困境.就是说只有二方的囚徒困境,没有多方的.所谓多方的囚徒困境只是由多个二方囚徒困境混杂在一起而形成的错觉.
[编辑] 重复的囚徒困境
罗伯特·阿克塞尔罗德在其著作《合作的进化》中,探索了经典囚徒困境情景的一个扩展,并把它称作“重复的囚徒困境”（IPD）.在这个博弈中,参与者必须反复地选择他们彼此相关的策略,并且记住他们以前的对抗.阿克塞尔罗德邀请全世界的学术同行来设计计算机策略,并在一个重复囚徒困境竞赛中互相竞争.参赛的程序的差异广泛地存在于这些方面：算法的复杂性、最初的对抗、宽恕的能力等等.
阿克塞尔罗德发现,当这些对抗被每个选择不同策略的参与者一再重复了很长时间之后,从利己的角度来判断,最终“贪婪”策略趋向于减少,而比较“利他”策略更多地被采用.他用这个博弈来说明,通过自然选择,一种利他行为的机制可能从最初纯粹的自私机制进化而来.
最佳确定性策略被认为是“以牙还牙”,这是阿纳托尔·拉波波特（Anatol Rapoport）开发并运用到锦标赛中的方法.它是所有参赛程序中最简单的,只包含了四行BASIC语言,并且赢得了比赛.这个策略只不过是在重复博弈的开头合作,然后,采取你的对手前一回合的策略.更好些的策略是“宽恕地以牙还牙”.当你的对手背叛,在下一回合中你无论如何要以小概率（大约是1%-5%）时而合作一下.这是考虑到偶尔要从循环背叛的受骗中复原.当错误传达被引入博弈时,“宽恕地以牙还牙”是最佳的.这意味着有时你的动作被错误地传达给你的对手：你合作但是你的对手听说你背叛了.
通过分析高分策略,阿克塞尔罗德指定了策略获得成功的几个必要条件.
友善
最重要的条件是策略必须“友善”,这就是说,不要在对手背叛之前先背叛.几乎所有的高分策略都是友善的.因此,完全自私的策略仅仅出于自私的原因,也永远不会首先打击其对手.
报复
但是,阿克斯洛德主张,成功的策略必须不是一个盲目乐观者.要始终报复.一个非报复策略的例子是始终合作.这是一个非常糟糕的选择,因为“下流”策略将残酷地剥削这样的傻瓜.
宽恕
成功策略的另一个品质是必须要宽恕.虽然它们不报复,但是如果对手不继续背叛,它们会一再退却到合作.这停止了报复和反报复的长期进行,最大化了得分点数.
不嫉妒
最后一个品质是不嫉妒,就是说不去争取得到高于对手的分数（对于“友善”的策略来说这也是不可能的,也就是说“友善”的策略永远无法得到高于对手的分数）.
因此,阿克塞尔罗德得到一种给人以乌托邦印象的结论,认为自私的个人为了其自私的利益会趋向友善、宽恕和不嫉妒.阿克塞尔罗德关于重复囚徒困境的研究的重要结论之一,是友善的家伙能先完成交易.
重新考虑经典的囚徒困境一节中给定的军备竞赛模型：结论是,只是理性策略增进了军事力量,似乎两个国家都宁可花费其GDP在枪炮而不是黄油上.有趣的是,企图说明对抗国家实际上以这种方式（在“重复囚徒困境假定”下的不同时期,军费支出在“高”和“低”之间反复）竞赛的尝试,却经常表明假定的军备竞赛并没有如预想的那样出现.（例如希腊人和土耳其人的军费支出,看来并不像遵循“以牙还牙”的重复囚徒困境式的军备竞赛,却更可能是被其国内的政策所驱使.）这可能是一次性博弈和重复性博弈中的理性行为不同的例子.
对一次性囚徒困境博弈来说,最佳（点数最大化的）策略是简单地背叛；正如前面解释的,无论对手的行动可能是什么,这都是真实的.但是,在重复的囚徒困境博弈中,最佳策略依赖于可能的对手的策略,和他们怎样对背叛和合作作出反应.例如,考虑这样一个人群,那里每个人每次都背叛,除了一个人是遵循以牙还牙策略.这个人处于一种轻微的不利地位,因为第一回合的损失.在这样的人群中,对这个人来说最佳策略就是每次都背叛.在一个有一定的百分比的总背叛者而剩下的则是以牙还牙者的人群中,对个人来说的最佳策略依赖于这个百分比和博弈的长度.
一般有两种方法得到最佳策略：
贝叶斯纳什均衡：如果对抗策略的统计分布能被确定（例如,50％以牙还牙,50％一直合作）,就能从数学上获得最佳的相对策略[4].
已经有了人群的蒙特卡罗模拟,在这里低分个人消失了,高分个人一再被生产出来（一种获得最佳策略的天才算法）.决赛人群中的算法合成通常依赖于初赛人群中的算法合成.
尽管以牙还牙始终被认为是最可靠的基本策略,但是在重复囚徒困境的20周年纪念赛中,来英国南安普敦大学的一个小组（由尼古拉斯·詹宁斯（Nicholas Jennings）[1]领导,包括了拉蒂普·达什（Rajdeep Dash）、萨瓦帕里·拉姆琼（Sarvapali Ramchurn）、亚历克斯·罗杰斯（Alex Rogers）斯和皮鲁克里士南·维特林根（Perukrishnen Vytelingum））介绍了一个新的策略,这个策略证明了它比以牙还牙更成功.这个策略依赖于程序之间的合作,为单一程序中获得了最高的点数.南安普敦大学提交了60个程序参与竞赛,这些程序的开头被设计成通过一组5到10个的动作去彼此识别.一旦这些识别被作出,一个程序将总是合作,其他程序则总是背叛,保证背叛者得到最大的点数.如果程序识别出它在操作一个非南安普敦参与者,这程序将持续地背叛,企图去最小化竞争程序的得分.结果[5],这个策略以获得前3位结束了竞赛,也得到了大量接近底部的位置.虽然这个策略显著地证明了比以牙还牙有效,但是这是因为利用了下述事实：在这个特殊的竞赛中,多重通道是被允许的.在一方只能控制单一参与者的竞赛中,以牙还牙确实是更好的策略.
如果重复囚徒困境将被精确地重复N次,已知N是一个常数,那么会产生另一个有趣的事实.纳什均衡就是每次都背叛.这很容易用归纳法证明.你也可以在最后的回合背叛,既然你的对手将没有机会惩罚你.因此,你们都将在最后的回合背叛.这时,你可以在倒数第二回合中背叛,既然最后一回无论你做什么,你的对手都将背叛.依此类推.为了合作以保持请求,这时未来必须对两个参与者来说是不确定的.一个解决方案是让博弈总次数N变成随机的.对未来的预期必须是无法确定的长度.
另一个单独的案例是“永不停止”的囚徒困境.这个博弈被重复很多次,而且你的分数是一个平均数（当然是用计算机计算的）.
囚徒困境博弈是某些人类合作和信任理论的基础.假定囚徒困境能够模拟需要信任的两人之间的交流,群体的合作行为可以用有多个参与者的、重复博弈的变体来模拟.这从而引起了许许多多学者经久不衰的兴趣.1975年,格罗夫曼（Grofman）和普尔（Pool）估计,致力于这方面研究的学术文章,数量超过2000篇.
[编辑] 学习心理学和博弈论
当博弈参与者能学会估计其他参与者背叛的可能性,他们自身的行为就为他们关于其他人的经验所影响.简单的统计显示,总体上,缺乏经验的参与者与其他参与者的互动,或者是典型的好,或者是典型的坏.如果他们在这些经验的基础上行动,（通过更多的背叛或合作,否则）他们可能在未来的交易中受损.随着经验逐渐丰富,他们获得了对背叛可能性的更真实的印象,变得更成功地参与博弈.不成熟的参与者经历的早期交易对他们未来参与的影响,可能比这些交易对成熟的参与者的影响要大得多.这个原理部分地解释了,为什么年轻人的成长经验这么具有影响力,以及为什么他们特别容易被欺负,有时他们本身最后也成为欺凌弱小者.
群体中背叛的可能性,可以被合作的经验所削弱[6],因为先前的博弈建立了信任.因此自我牺牲行为可以,例如,加强团体的道德品质.如果团体很小,积极行为更可能以互相肯定的方式——鼓励这个团体中的个人继续合作——得到反馈.这与相似的困境有关：鼓励那些你将援助的人,从可能使他们处于危险的境地的行为中得到满足.这类方法主要在互惠利他主义、群选择、血缘选择和道德哲学的研究中涉及.
[编辑] 相关的博弈
[编辑] 封闭袋子交易
霍夫施塔特2曾提出像囚徒困境的问题.他提出“密封袋子交易”,他认为以这简单博弈题,有助人们理解此论题.
“密封袋子交易”:甲、乙两人面对面交换密封的袋子,双方的共识是甲的袋放钱、乙的放商品.双方各自可以诚实地把东西放到袋子,然后交换；又或者交空袋子给对方,选择背叛.
在这场博弈中,由于背叛可获得巨大利益,必然有多人选择背叛.这意味着理性的商人不会进行这种交易,因而“封闭袋子交易”将由于逆向选择而失去市场.
[编辑] 是敌是友?
“是敌是友?”是一个竞赛表演节目,从2002年到2005年在美国竞赛表演广播网（Game Show Network）放映.这是一个用真人进行的囚徒困境博弈例子,不过情景是人造的.这个竞赛表演有三对人参与竞争.当每对人被淘汰时,他们做一个囚徒困境博弈,决定如何分他们的奖品.如果他们都合作（“朋友”）,他们的奖品就被平分.如果一个合作而另一个背叛（“敌人”）,背叛者得到所有的奖品,合作者什么都得不到.如果双方互相背叛,那么两人都一无所获.注意,这个支付矩阵与前述标准的支付矩阵不同,因为发生“互相背叛”的情形和“我合作而对手背叛”的情形,其损失是一样的.和标准囚徒困境的稳定均衡相比,“互相背叛”是不稳固的均衡（weak equilibrium）.如果你知道你的对手将成为“敌人”,这时你的选择无法影响你的奖品.在某种意义上,“是敌是友”拥有一个介于“囚徒困境”和“小鸡”之间的支付模型.
这个支付矩阵是：
如果参与者都合作,每人得到 +1.
如果都背叛,每人得到 0.
如果甲合作而乙背叛,甲得到0而乙得到 +2.
是敌是友对于想对囚徒困境作现实分析的人将是有用的.注意到,参与者只能进行一次,所以所有涉及重复进行博弈的观点都不适用,“以牙还牙”策略也无法发展出来.
在是敌是友中,每个参赛者被允许做一个声明,使另一半友在双方秘密决定合作或背叛之前,确信他的友善.可能“打破制度”的方法将是一个参与者告诉他的对手：“我会选择做敌人.如果你相信我后来会和你分奖品的话,就选择做朋友.否则,如果你选择做敌人,我们都会空手而回.”一个更贪婪的版本将是：“我将选择做敌人.我会给你百分之X,剩下的百分之（100-X）归我.所以,要或不要,要么我们都得到一些,要么我们都一无所获.”（在最后通牒博弈中时.）现在,奸计就是去尽量减少那个百分之X,并保持另一个竞争者仍然选择做朋友.基本上,这个参与者必须知道这个界限,在这里他的对手从看到他一无所获中得到的效用,要超过他从肯定能赢得的金钱中得到的效用,如果他顺利的话.
在竞赛中这个方法从未被试验过；可能是因为裁判们不会允许,而且即使允许,不平等厌恶也会由于这个规则的使用而导致较低的期望收益.（最后通牒博弈中尝试了这个方法,结果导致对高而不平等的出价的拒绝——在一些案例中,相当于两周的工资优先于两个参与者一无所获被决绝.）
http://ent.sina.com.cn/m/2002-03-21/76881.html