纳什均衡

✍ dations ◷ 2025-05-16 05:23:39 #纳什均衡

在博弈论中,纳什均衡(英语:Nash equilibrium,或称纳什均衡点)是指在包含两个或以上参与者的非合作博弈(Non-cooperative game)中,假设每个参与者都知道其他参与者的均衡策略的情况下,没有参与者可以透过改变自身策略使自身受益时的一个概念解。该术语以约翰·福布斯·纳什命名。在博弈论中,如果每个参与者都选择了自己的策略,并且没有玩家可以透过改变策略而其他参与者保持不变而获益,那么当前的策略选择的集合及其相应的结果构成了纳什均衡。即若 p i ( s ) = m a x r i {\displaystyle p_{i}(s)=max_{r_{i}}} 为纳什均衡点,其中: p i {\displaystyle p_{i}} 为参与者i的收获(payoff), s i {\displaystyle s_{i}} 代表所有参与者之策略, r i {\displaystyle r_{i}} 代表参与者i的一种可能策略, ( s ; r i ) {\displaystyle (s;r_{i})} 指参与者i单方面改变策略为 r 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也指出,在参与者匿名的情况下,则仅需多项式时间即可逼近纳什均衡。

相关

  • 历史联合国是第二次世界大战结束后成立的国际组织。自那时起,联合国逐步拓展了其目标与行动范畴,在21世纪初已发展成为了典型的国际性机构。美国总统富兰克林·罗斯福是最先使用“
  • 赌博赌场,又称娱乐场,是专供赌博的地方。常指合法经营的多种赌博场所,非法的聚赌地方一般称为赌窟或赌坊。赌场多数是提供赌客与赌场庄家的对赌。常见提供的博彩方法有:角子老虎机、
  • 白垩纪-第三纪灭绝事件白垩纪-古近纪灭绝事件(简称K-Pg事件、K-Pg灭绝),旧称为白垩纪﹣第三纪灭绝事件(简称K-T事件、K-T灭绝),俗称恐龙大灭绝,是地球历史上的第五次以及最后一次大规模物种灭绝事件、也是
  • 金黄藻门金藻(学名:Chrysophyta),群体生活,约有1500种,外观呈金黄褐色,光合色素包含叶绿素A、C、胡萝卜素、叶黄素、褐藻素,以昆布多糖(Laminarin,一种β1-3葡萄糖聚合物)为主要碳水化合物贮存
  • 亲核性亲核体,又叫亲核基、亲核试剂(英语:Nucleophile,意思为原子核的喜好物)是一个基本的有机化学概念,指具有亲核性的化学试剂,可用:Nu表示。它用来衡量一个试剂给电子能力的强弱。一般
  • 鍼灸针灸是针法和灸法的合体。中医学中采用针刺或火灸人体穴位来治疗疾病,是联合国教科文组织认定的人类非物质文化遗产代表作。根据中医学理论,通过刺激穴位可以改善经络中的气的
  • 政府总理政治主题越南总理(越南语:Thủ tướng Việt Nam/ 首相越南?)在越南的历史上有着不同的名称。在越南帝国时期称为内阁总长(越南语:Nội các Tổng trưởng/ 內閣總長?),在越南民主
  • 吴县吴县市,是中华人民共和国江苏省苏州市曾经代管的县级市,由吴县于1995年撤县设市而成,于2000年拆分成吴中区和相城区。吴县市位于北纬30°56~31°33'、东经119°55'~120°54'之间。西
  • 清稗类钞《清稗类钞》,笔记小说,清代掌故遗闻的汇编,晚清遗老徐珂(1869年-1928年)编撰。徐珂,原名昌,字仲可,别署中可、仲玉,浙江杭县(今余杭)人,清光绪间举人,曾任袁世凯幕僚,未几辞退。后任上海
  • 千升千升,是容量计量单位,符号为kL。同时也是国际单位制(SI)单位。立方尧米、立方佑米(Ym3) 立方泽米、立方皆米(Zm3) 立方艾米(Em3) 立方拍米(Pm3) 立方垓米、立方太米(Tm3)立方京米、立