纳什均衡

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

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

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

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

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

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

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

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

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

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