纳什均衡

纳什均衡

定理、​平衡类型

上级分类	解决方案概念
话题方面	博弈论
得名自	约翰·福布斯·纳什
公式定义	$\forall i,x_{i}\in S_{i}f_{i}(x_{i}^{*},x_{-i}^{*})\geq f_{i}(x_{i},x_{-i}^{*}).$
理论提出者	约翰·福布斯·纳什

“纳什均衡”的各地常用名称
中国大陆	纳什均衡
台湾	纳许均衡、奈许均衡
港澳	纳殊均衡、拿殊均衡

在博弈论中，纳什均衡（英语：Nash equilibrium，或称纳什均衡点）是指在包含两个或以上参与者的非合作博弈（Non-cooperative game）中，假设每个参与者都知道其他参与者的均衡策略的情况下，没有参与者可以透过改变自身策略使自身受益时的一个概念解。该术语以约翰·福布斯·纳什命名。在博弈论中，如果每个参与者都选择了自己的策略，并且没有玩家可以透过改变策略而其他参与者保持不变而获益，那么当前的策略选择的集合及其相应的结果构成了纳什均衡。即若$p_{i}(s)=max_{r_{i}}[p_{i}(s;r_{i})]$，则称s为纳许均衡点，其中：$p_{i}$为参与者i的收获（payoff），$s_{i}$代表所有参与者之策略，$r_{i}$代表参与者i的一种可能策略，$(s;r_{i})$ 指参与者i单方面改变策略为$r_{i}$。

发展历史

纳许平衡的命名来由为美国数学家约翰·福布斯·纳什。该概念的其中一个版本已知最早于1838年被安托万·奥古斯丁·库尔诺运用于他的寡占理论中。在库尔诺的理论中，商行们需选择合适的产量以获得最大利润，然而一家商行的理想产量取决于其他商行的产量。当每一家商行的理想产量都需要根据已知其他商行的产量来做出调整，以达到最大利润时，一种纯策略的纳许平衡——库尔诺平衡就形成了。在分析平衡稳定性的过程中，库尔诺还提出了最适反应动态（或最佳反应动态）的概念。然而纳许对平衡的定义比库尔诺的更为广泛，也比帕勒托效率平衡的定义更为广泛，因为纳许的定义没有针对“形成哪种平衡最为理想”作出评判。

与此相反，现代博弈论中的纳许平衡概念是用混合策略来定义的，其中的参与者倾向于符合概率分布，而非动作合理性。约翰·冯·诺伊曼和摩根斯顿在1944年出版的《博弈论与经济行为》（英语：Theory of Games and Economic Behavior）一书中提出混合策略纳许平衡的概念，然而他们的分析局限于零和博弈这一特例。书中表明对于任何零和博弈，只要动作集合有限，就存在混合策略纳许平衡。纳许在1951年发表了文章《非合作博弈》（英语：Non-Cooperative Games），意在定义上述这种混合策略纳许平衡，并证明这样一场博弈至少存在一个（混合策略）纳许平衡。之所以纳许对上述存在性的证明能够比冯·诺伊曼的更具普遍性，关键在于他对平衡所下的定义。根据纳许的说法，“平衡点是当其馀参与者的策略保持不变时，能够令参与者的混合策略最大化其收益的一个n元组”。在1950年发表的一篇论文中，仅凭著将问题置于该框架中的做法，纳许就成功运用了角谷不动点定理；在1951年发表的改版论文中，纳许运用了布劳威尔不动点定理。上述两者共同证明了，存在至少一种混合策略的策略组合（英语：strategy profile），能够针对有限参与者博弈（不一定是零和博弈）的情况自我映射，即一种不需要为提高收益而变更策略的策略组合。

自纳许平衡概念形成以来，已经有博弈理论家发现，在某些情况下该概念所做的预测颇具误导性（或缺乏唯一性）。这些理论家提出了许多相关的解概念（也称为纳许平衡的“微调”），意在弥补纳许平衡概念中已知的瑕疵。其中一个尤为重要的问题是，某些纳许平衡所依据的并非“实质性”威胁。1965年赖因哈德·泽尔腾提出子博弈完全平衡，以排除基于非实质性威胁的平衡。纳许平衡的其他延伸概念阐述了重复博弈产生的影响，或资讯不完整对博弈的影响。然而，后人的微调与延伸都用到了一个关键性理解，也是纳许概念的存在基础：一切平衡概念都是在分析在每个参与者都考虑其他参与者的决定的情况下，最终选择是什么。

例子

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

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

基于经济学中“理性经济人”的前提假设，两个囚犯符合自己利益的选择是坦白招供，原本对双方都有利的策略不招供从而均被判刑半年就不会出现。事实上，这样两人都选择坦白的策略以及因此被判两年的结局被称作是“纳什均衡”（也叫非合作均衡），换言之，在此情况下，无一参与者可以“独自行动”（即单方面改变决定）而增加收获。

学术争议和批评

第一，纳什的关于非合作博弈论的平衡不动点解（equilibrium/fixpoint）学术证明是非建设性的（non-constructive），就是说纳什用角谷不动点定理证明了平衡不动点解是存在的，但却不能指出以什么建设性的算法如何去达到这个平衡不动点解。这种非建设性的发现对现实生活里的博弈的作用是有限的，即使知道平衡不动点解存在，在很多情况下却找不到，因此仍不能解决问题。

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

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

不过在同一篇论文里，Daskalakis也指出，在参与者匿名的情况下，则仅需多项式时间即可逼近纳什均衡。

参见

• 囚徒困境
• 帕累托最优
• 博弈论
• P/NP问题
• PPAD

参考书目

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

外部链接

• 纳什博弈论的原理与应用 （页面存档备份，存于互联网档案馆） 北京晚报 (2002年3月21日)