《美丽心灵》:纳什均衡的定义用(S)

翻译:努尔

点评:许

如果我们都打金发女郎并互相妨碍,事实证明没有人能得到她。接下来我们去找她的朋友,他们会不屑一顾,因为没有人愿意做替补。但是,如果我们都不寻找金发女郎呢?我们不会互相影响或冒犯其他几位女士。只有这样我们才能成功。

如果你看过这部电影,那将是《美丽心灵》(2001)) 中的角色约翰·纳什第一次向他的朋友们解释他关于“管理动力学”的天才) 的新发现。当然,事实上,这并不是约翰·福布斯·纳什真正想到的,他也没有这样描述“博弈论”的概念。本文的目的是更准确、更全面地描述纳什均衡提出的过程及其价值。

什么是纳什均衡

纳什均衡是非合作博弈的概念,涉及两个或多个参与者。假设每个参与者都知道其他参与者的均衡策略,那么没有一个参与者可以通过单方面改变他的策略来获得利益。(奥斯本等人,1994)。

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

如果没有一个参与者可以通过单方面改变策略来获得更大的收益,那么这个策略就是纳什均衡。

也就是说,在一个两人博弈中,如果玩家 A 的策略在玩家 B 的选择下是最优的,并且玩家 B 的策略在玩家 A 的策略下也是最优的,那么这对 A 策略就构成了纳什均衡。没有球员可以通过单方面改变自己的策略来取得更好的成绩。关键是玩家不知道对方的策略,只根据自己的利益(也知道其他玩家的利益)选择最优策略。

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

纳什均衡的定义

设(S,f)代表u个玩家的博弈,Si是第i个玩家的策略集,S=S1×S2×S3×…×Su是所有策略的集合,f(x)=(f1(x) ,… ,fu(x)) 是 x∈S 情况下的支付函数。xi 是玩家 i 的策略,xi 是所有其他玩家(除了 i)的策略元组。

图片[1]-《美丽心灵》:纳什均衡的定义用(S)-8118体育网

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

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

∀i,xᵢ ∈ Sᵢ : fᵢ(x*ᵢ, x*₋ᵢ) ≥ fᵢ(xᵢ,x*₋ᵢ)

纳什均衡证明

Nash 的论文证明 (1950c) 使用了 Brouwer 的不动点定理。感谢大卫盖尔,纳什以更简单的方式给出了相同的证明(角谷不动点定理)。

用角谷定理证明纳什均衡

为了证明纳什均衡(NE)的存在,假设rᵢ(σ₋ᵢ)是参与者i在其他参与者策略下的最优策略。

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

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

角谷不动点定理指出,如果满足以下四点,则存在不动点:

Σ 是紧的、凸的和非空的;

r(σ) 非空;

图片[2]-《美丽心灵》:纳什均衡的定义用(S)-8118体育网

r(σ) 是上半连续的;

r(σ) 是凸的。

条件 1 的前提是 Σ 是单纯形,所以它是紧致的。“凸”源于玩家混合策略的能力。玩家必须选择一个策略,所以 Σ 不为空。

条件 2 和 3 可以由 Berge 最大定理证明。由于 uᵢ 是连续且紧致的,因此 r(σ) 是非空且上半连续的。

条件 4 也是由于混合策略造成的。假设 σᵢ,σᵢ’ ∈ r(σ₋ᵢ),则 λσᵢ + (1 – λ)σᵢ’ ∈ r(σ₋ᵢ)。也就是说,如果两种策略产生最大的回报,那么两种策略的混合也将产生相等的回报。

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

例子

正式的博弈通常由三个要素组成:参与者、策略和每个参与者的收益。payoff 函数代表了每个玩家对策略的偏好,策略集是玩家在游戏中的策略列表。可以在示意图中解释三个元素,称为收益矩阵,以显示两人策略(两名玩家各有两种策略):

图片[3]-《美丽心灵》:纳什均衡的定义用(S)-8118体育网

左:游戏 1 的收益矩阵,“协调游戏”。右:游戏2的收益矩阵,“硬币匹配”游戏(猜拳)

在每场游戏中,双方玩家都可以选择两种策略 A 和 B 中的一种。

纯策略纳什均衡

图片[4]-《美丽心灵》:纳什均衡的定义用(S)-8118体育网

纯策略纳什均衡是指任何参与者都不能通过单边偏离和轮换策略来获得更高的预期收益。

在游戏 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 唯一的理性反应是做同样的事情。For example, in the “coin pairing” game, when the strategies of choosing A and B have equal probability, it is a mixed strategy Nash equilibrium.

解释

在他的论文中,纳什提出了两种关于均衡的观点:一种基于理性,一种基于统计总体。

在理性解释下,玩家被认为是理性的,并且对游戏有充分的了解,包括其他玩家的偏好,并且这些信息是众所周知的。由于所有玩家都知道彼此的选择策略和偏好,因此他们也可以计算他们对所有策略的收益并获得最佳策略。如果游戏只进行一次并且所有玩家都期望相同的纳什均衡(高收益),那么没有人会想要改变他们的策略。

在基于统计人口的假设中,纳什指出,没有必要假设玩家对游戏的信息有完整的了解,或者有能力和意愿进行复杂的推理过程。这是因为“假设游戏中每个位置都有一组玩家,随着时间的推移,随机玩家会参与到游戏中。如果纯策略有一个稳定的平均频率的玩家,那么这个稳定的平均频率是混合的. 战略纳什均衡。(纳什,1950c)。

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

显然,诺贝尔奖委员会认真对待这两种解释。Gounault 可能提出了合理的解释,但对生物博弈很重要的统计解释却是完全原创的。虽然这三篇论文都对非合作博弈提供了解释,但只有这篇论文同时解决了这两种解释。当在诺贝尔研讨会上被问到为什么这些解释没有包含在年度报告中时,纳什回答说:“我不知道它是否是故意删减到《数学年鉴》中的。”

——摘自库恩等人的《约翰纳什》。(2002)

寻找

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

“在与冯诺依曼会面后,纳什在与大卫盖尔的对话中说:‘我想我已经找到了一种方法来推广冯诺依曼的最小-最大定理,其基本思想是在两人零和游戏中,其中最好的策略是……整个理论都以此为基础。它适用于任何数量的人,不限于零和游戏。”

– 引自 Sylvia Nassar 的《美丽心灵》(1998 年)

纳什和大卫·盖尔之间的谈话是在 1995 年被盖尔转达给纳萨尔的。纳什正在研究所谓的“讨价还价问题”,在这个问题上,两个人有机会互惠互利,但任何行动都是单方面采取的(未经同意)不影响对方利益。想想经典的“切蛋糕和选择协议”,其中一方切蛋糕,另一方优先考虑他们想要的部分,这提供了所谓的无嫉妒切蛋糕模式。

正如纳萨尔所写,盖尔更着迷于纳什新结果的数学价值,而不是他的新结论的应用价值,他在 1995 年写道:“数学是如此美丽。” 这在数学上是正确的。

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

——摘录,Sylvia Nassar 的美丽心灵 (1998)

盖尔还被选入了美国国家科学院,帮助纳什获得了他的成果。Solomon Lefschetz 代表他们提交了这份报告。1950 年 1 月,《美国国家科学院院刊》第 36 卷发表了不到一页的标题,“N 人博弈中的平衡点”。

图片[5]-《美丽心灵》:纳什均衡的定义用(S)-8118体育网

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

结语

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

文件

这三篇文章包含三个不同的证明,证明纳什均衡的存在。第一篇题为“N-Man Games 中的平衡点”(1950b),是 Nash 和 Gale 在美国国家科学院院刊上的一篇笔记。第二个,称为“非合作游戏”(1951 年),发表在数学年鉴,卷。54, No. 2. 在 Econometrics No. 21, The Two-Player Game (1953) 中,纳什将他对谈判问题的研究(Nash, 1950a)扩展到“威胁”可以发挥作用的更广泛的情况(库恩等人,2002)。

诺贝尔奖

就在 10 月 11 日宣布 1994 年诺贝尔经济学奖前几周,两位数学家——哈罗德·W·库恩和小约翰·福布斯·纳什——正在梅多湖附近的一家疗养院里。拜访了他们的老师 Albert W. Tucker,他年近 90 岁,卧床不起。纳什先生已经好几年没有和他的导师说过话了。在库恩离开的那一刻,他们讨论了数论。

当纳什先生走出房间时,库恩先生回来告诉塔克先生一个惊人的秘密:在纳什先生不知道的情况下,瑞典皇家科学院打算为纳什在塔克先生领导下所做的经济学做出贡献1949年,授予他诺贝尔奖。这个奖项是一个奇迹。

– 纳萨尔 1994

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

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

图片[6]-《美丽心灵》:纳什均衡的定义用(S)-8118体育网

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

原文链接:

© 版权声明
THE END
喜欢就支持一下吧
点赞10 分享
评论 抢沙发
头像
欢迎您留下宝贵的见解!
提交
头像

昵称

取消
昵称表情代码图片