纳什:如何科学追求对象?

发布时间:03-2412:37

科学无国界

我们是知识的搬运工

福利时间

今天我们将送出由Nature自然科研编译,清华大学出版社出版的优质科普书籍自然的音符:118种化学元素的故事》。

你知道吗?稀土其实并不那么稀有,铊曾被英国“茶杯投毒者”作为杀人武器,火柴中的磷会导致工人发生“磷毒性颌骨坏死”,《茶花女》中有关爱情的描述“既是诅咒,也是祝福”也可以用来形容一种元素——镝。

自然科学发展的长河里一些最引人入胜的篇章无疑是由化学元素谱写的:它们的发现、特性,以及围绕它们的故事。但随着元素大发现时代的过去,这些故事也渐渐埋于故纸堆。《自然的音符:118种化学元素的故事》由100多位世界各地的科学家撰写,最初以专栏文章的形式是发表在《自然-化学》上。当这些科学家将元素的前世今生娓娓道来,你才会发现,一张元素周期表,背后有多少或激动人心、或幽默讽刺、或骇人听闻的故事。

这本书由《自然-化学》高级编辑Anne Pichon博士倾情作序,金涌院士、中国化学会、中国化工学会推荐阅读。

只要你认真阅读下面的这篇文章,思考文末提出的问题,严格按照 互动:你的答案 格式在评论区留言,就有机会获得奖品!

作者:Jrgen Veisdal翻译:Nuor审校:xux

"

如果我们都对金发女士下手,并且互相妨碍,那么结果是谁都无法得到她。接下来我们再去找她的朋友们,她们会不屑一顾,因为没有人愿意当备胎。然而假如我们都不找金发女士呢?我们不会相互影响,也不会冒犯其他几位女士。这就是我们成功的唯一方式。

"

如果看过电影的话你会发现,这就是电影《美丽心灵》(2001)中的角色约翰·纳什首次向他的朋友们解释有关他天才般的有关“博弈论”(governing dynamics)的新发现。当然,事实上,这并不是真实的约翰·福布斯·纳什想到的,他也不是这样描述“博弈论”概念的。这篇文章的目的是更加准确和全面地描述纳什均衡提出的过程和其价值。

什么是纳什均衡

纳什均衡是是非合作博弈的概念,涉及两个或两个以上的博弈者,假设其中每个博弈者都知道其他博弈者的均衡策略,单个博弈者都无法通过单方面改变自己的策略来获取利益(Osborne et al, 1994)。

定理可以被非正式地描述为:

如果没有一方博弈者能通过单方面改变自身策略来获取更大收益,那么这个策略就是纳什均衡

也就是说,在一个二人游戏中,如果已知玩家B选择的情况下,玩家 A 的策略是最优的,同时已知玩家A策略的情况下,玩家 B 策略也是最优的,那么这一对策略构成纳什均衡。没有一个玩家可以通过单方面改变自己的策略获得更优的结果。关键的是,玩家都不知道对方的策略,仅根据自身的利益选择最优策略(也知晓其他玩家的利益)。

推广到 n 个玩家的情况,可定义为:

纳什均衡的定义

用(S,f)代表 u 个玩家的游戏,Si是 i 玩家的策略,S=S1×S2×S3×…×Su是所有策略的集合,f(x)=(f1(x),…,fu(x)) 是 x∈S 情况下的收益函数。xi是玩家 i 的策略,x-i是其他所有玩家(除了 i )的策略集合。

当每个玩家 i∈{1,…,u} 选择策略 xi 后,策略配置为 x = (x,...,x),玩家i则获得收益 f(x)。收益取决于所有人的策略,包括玩家 i 和其他玩家的。

如果没有任何一个玩家可通过单方面改变策略获取更多收益,则这个策略集x*∈S 就是纳什均衡,即:

i,x ∈ S : f(x*, x*) ≥ f(x,x*)

纳什均衡的证明

纳什的论文证明(1950c)使用了布劳威尔定点定理。由于戴维·盖尔的功劳,纳什利用更简单的方式(角谷定点定理)给出了相同的证明。

利用角谷定理证明纳什均衡

为证明纳什均衡(NE)的存在,假设r(σ)是玩家i在其他玩家的策略下的最优策略。

r(σ) = arg max u(σ, σ)

在这里,σ ∈ Σ 其中Σ x Σ 是所有参与者的策略,u 是玩家 i 的收益函数。定义一个值函数 r: Σ → 2^Σ,其中 r = (r(σ), r(σ))。证明纳什均衡的存在等价于证明 r 有一个不动点。

角谷不动点定理表明,如果满足以下四点,则有不动点的存在:

Σ 是紧凑,凸且非空;r(σ) 是非空的;r(σ) 是上半连续的;r(σ) 是凸的。

条件 1 的前提是Σ是单纯形,因此其为紧凑的。“凸”源于玩家能够混合策略。玩家必须选择策略因此Σ为非空的。

条件 2 和 3 可通过Berge 最大值定理(Berge's maximum theorem)证明。因为 u 是连续且紧凑的,所以 r(σ) 是非空的且上半连续的。

条件 4 也是由于混合策略的原因。假设 σ, σ' ∈ r(σ),然后 λσ + (1 - λ)σ' ∈ r(σ)。即如果两个策略产生最大收益,则两个策略混合也会产生同等收益。

因此,r 和纳什均衡中存在一个不动点。

举例

正式的游戏通常包含三个元素:玩家,策略和每个玩家的收益。收益函数代表每个玩家对于策略的偏好,策略集是玩家在游戏中的策略列表。可以在示意图中解释三种元素,并称其为收益矩阵,来表明两玩家的策略(两个玩家各有两种策略):

左:游戏1的收益矩阵,为一个“协调博弈”。右:游戏2的收益矩阵,“钱币配对”游戏(猜拳)

在每个游戏中,两个玩家都可以从A和B两种策略中任选一种。

纯策略纳什均衡

纯策略的纳什均衡指的是:没有任何一个参与者可以通过单方面偏离和轮换策略来获得更高的预期收益。

在游戏1中,如果他们选择不同的策略(A,B)或(B,A),则两者的收益均为0。如果他们都选择策略A,则两者都会得到收益2。如果他们都选择策略B,则两者都会得到收益1。策略集(A,A)和(B,B)因此产生纳什均衡,因为单个玩家策略的改变会导致该玩家的收益更低。

在游戏2中,如果他们选择不同的策略(A,B)或(B,A),则玩家1的回报为-1,玩家2的回报为1。如果他们都选择A或B,则玩家1会得到 1的收益,玩家2得到-1。该游戏中没有纯粹的纳什均衡策略,因为在每种策略集中,其中一名玩家都会从策略的偏离中获利。

混合策略纳什均衡

纳什的结果表明,在所有有限对策中至少存在一个纳什均衡点。由于游戏2不存在纯策略的纳什均衡,所以在混合策略中必然存在纳什均衡:

混合策略纳什均衡是一种策略集,其特征是至少有一个参与者在玩随机策略,并且没有一个参与者可以通过单方面改变和轮换策略来获得更高的期望收益。

在游戏2中,玩家不选择单一的策略,而是按照一定的概率分布来选择策略。在均衡中,每个参与者的概率分布选择使得所有其他参与者对他们的纯策略不感兴趣。

例如,作为玩家1,我们可以一半时使用A,一半时间选择B,根据抛硬币决定策略。玩家2唯一的理性反应就是做同样的事情。比如,在“硬币配对”博弈中,当选择A和B的策略概率相等时,就是一种混合策略的纳什均衡。

解释

纳什在他的论文中提出了两种关于均衡的想法:一种基于理性,一种基于统计人群。

在理性解释下,玩家们被认定为理性的,而且知晓游戏的全部信息,包含其他玩家的选择偏好,而且这些消息都是众所周知的。由于所有的玩家都了解彼此的选择策略和偏好,所以也能为所有的策略计算其收益,得到最佳策略。如果游戏只玩一次且所有的玩家都期望相同的纳什均衡(高收益),那么没有人会想要改变自己的策略。

基于统计人群的假设中,纳什指出:不必假设玩家完全了解游戏的信息,或者有能力和意愿进行复杂的推理过程。这是由于“假设在游戏的每个位置都有一群玩家,随着时间变化,会有随机玩家参与游戏。如果有玩家用一个稳定的平均频率来选用纯策略,那么这个稳定的平均频率就是混合策略纳什均衡。”(纳什,1950c)。

正如哈罗德·库恩后来写道:

显然诺贝尔评奖委员会认真考虑了这两种解释。古诺特可能会提出理性的解释,但是对于生物学博弈来说很重要的统计解释是完全原创的。虽然这三篇论文都对非合作博弈进行了解释,但只有这篇文章对这两种解释进行了阐述。当在诺贝尔研讨会上被问及为什么这些解释没有被收录到年报中,纳什回应道:“我不知道是不是为了《数学年鉴》而特意剪掉的。”

——摘自库恩等人的《约翰·纳什传》(The Essential John Nash,2002)

发现

不同于电影中的描述,传记作者西尔维亚·纳萨尔写道:纳什在普林斯顿大学读研究生时想到了这个想法,并研究了游戏策略和经济学谈判的数学模型。正如纳萨尔所写:

“经过与冯·诺伊曼会晤之后,纳什在与大卫·盖尔的谈话中说道:‘我想我已经找到了可以概括冯·诺伊曼的最小-最大定理的一种方法,基本思想是在两人的零和博弈中,最好的策略是…整个理论都基于此。它适用于任何数量的人,并不局限于零和博弈’。”

——引自西尔维亚·纳萨尔的《美丽的心灵》(A Beautiful Mind)(1998年)

纳什和大卫·盖尔的对话在1995年由盖尔转述给纳萨尔。纳什当时在研究所谓的“谈判问题”(bargaining problem),其中两个人都有机会互惠互利,但是任何单方面(未经同意)采取的行为都不会影响另一方的利益。想想经典的“切蛋糕和选择协议”,一方切蛋糕,另一方优先选择自己想要的部分,这种模式提供了所谓的无嫉妒的切蛋糕模式。

就像纳萨尔所写的那样,相比于纳什新结论的应用价值,盖尔对更对其数学价值着迷,他在1995年写道:“数学是如此之美。”这在数学上是正确的。

“盖尔意识到,相对于冯·诺依曼的零和博弈,纳什的想法更适用于更广泛的现实世界。”他有一个可以推广到谈判的概念。

——摘录,西尔维亚·纳萨尔的《美丽的心灵》(A Beautiful Mind,1998)

盖尔还起草给美国国家科学院,帮助纳什获得其结果的荣誉。所罗门·莱夫谢茨代表他们提交了这份报告。1950年1月,《美国国家科学院院刊》的第36卷刊登了这份不到一页的内容,题为《N人博弈中的均衡点》(Equilibrium points in N-person games)。

纳什(1950b)。N人博弈中的均衡点。美国国家科学院院刊36(1)。

结语

纳什的论文最终催生了三篇期刊论文一项诺贝尔经济学奖(1994年)。

期刊论文

这三篇文章包含了纳什均衡存在的三种不同证明。第一个题为“N人博弈中的均衡点”(1950b)的是纳什和盖尔为美国国家科学院院刊编写的笔记。第二篇叫做《非合作博弈》(1951年),发表在《数学年鉴》 54卷第2期上。在《计量经济学》第21期上发表的《两人合作游戏》(1953年)中,纳什将其关于谈判问题的工作(Nash, 1950a)扩展到了“威胁”可以发挥作用的更广泛的情况中(Kuhn et al, 2002)。

诺贝尔奖

就在1994年诺贝尔经济学奖于10月11日公布的几周前,两位数学家——哈罗德·W·库恩和小约翰·福布斯·纳什——在梅多湖附近的疗养院看望了他们的老师——将近90岁,卧病不起的阿尔伯特·W·塔克。纳什先生已经好几年没有和他的导师说过话了。从库恩离席的一个小时中,他们就数论展开了讨论。

当纳什先生走出房间后,库恩先生回来告诉塔克先生一个惊人的秘密:纳什先生不知道,瑞典皇家科学院打算对纳什在1949年于塔克先生门下做出的对经济学巨大的革命性贡献,授予他诺贝尔奖。这个奖是个奇迹。

——纳萨尔 1994

1994年10月11日,诺贝尔颁奖委员会宣布,将把1994年诺贝尔经济学奖授予约翰·福布斯·纳什博士,以表彰他在非合作博弈理论中对均衡的开创性分析:

约翰·福布斯·纳什介绍了合作博弈(可以达成有约束力的协议)和非合作博弈(不可能达成有约束力的协议)之间的区别。纳什提出了非合作博弈的均衡概念,后来被称为纳什均衡。

哈罗德·库恩(左)和纳什(右)

原文链接:

https://medium.com/cantors-paradise/the-nash-equilibrium-explained-c9ad7e97633a

【互动问题:生活中有哪些体现博弈学的知识或者游戏?

请大家严格按照 互动:问题答案的格式在评论区留言参与互动,格式不符合要求者无效。

截止到本周四中午12:00,点赞数排名前三名的朋友将获得我们送出的图书一本。

*本活动仅限于微信平台

编辑:aki

返回顶部