纳什均衡
正式的定义
让 表示集合的策略 th球员, 表示一组战略简介.这意味着 都是个人策略的可能组合。让我们 表示回报对球员 当评估战略概况时 ;请注意,单个玩家的收益也取决于其他玩家的策略。
一个人混合策略是一个概率分布一套可行的策略。例如,从“石头”、“布”或“剪刀”中选择一个均匀随机是混合策略的一个例子。还可以选择权重,以便根据不同的概率选择策略。A.纯策略它完全不涉及随机化,而是始终选择一种特定的策略。注意,重要的是:
纯策略只是混合策略的一种特殊情况,即100%选择一种策略。
这意味着,用于计算混合策略的相同方法在检测纯策略时同样有用。
A.纳什均衡这是一份战略简介 以
总的来说 ,在那里 表示一种策略而不是 可供玩家使用 .
如果这种不平等是严格的;即。
总的来说 ,概要文件 被称为严格的纳什均衡.否则, 被称为弱纳什均衡.
纳什存在定理保证只要 对所有人来说都是有限的 当参与者数量有限时,至少存在一个纳什均衡(可能涉及混合策略)。
有趣的是,约翰·冯·诺依曼(John von Neumann)对这个结果不屑一顾,他的回答是“这很微不足道,你知道,这只是一个不动点定理”,这比纳什发表这一结果早了一年,也比纳什(部分)获得诺贝尔奖早了40年。事实上,纳什的存在定理是不动点定理(或等价于Kakatuni的不动点定理)代数拓扑.
例子
纳什均衡最简单的例子是协调游戏在这种情况下,双方都能从协调中获益,但也可能有各自的偏好。例如,假设两个朋友想安排一个晚上聚会或看电影。两个朋友都喜欢参加同样的活动,但其中一个喜欢聚会而不是看电影的比例是2,而另一个喜欢看电影而不是参加聚会的比例是相同的。这可以通过以下方法建模支付矩阵:
聚会 | 电影 | |
聚会 | 2,1 | 0,0 |
电影 | 0,0 | 1,2 |
其中支付向量列在适当的策略配置文件下(第一个玩家的策略列在左侧)。在这种情况下,{Party,Party}和{Movie,Movie}是纳什均衡,因为当得知对方的选择时,双方都不会选择偏离。
然而,纳什均衡最著名的例子是囚徒困境在这个问题中,两个囚犯都可以选择通过保持沉默来与另一个囚犯“合作”,或通过坦白来“叛变”。如果两个囚犯都合作,他们将面临很少的监禁,但如果其中一人叛变,叛变者将立即获得自由,而合作者将面临大量监禁。问题在于,如果两名囚犯都选择叛逃,他们都将面临适度的监禁。这可以用收益矩阵来描述
在这种情况下,只有一个纳什均衡:两个玩家都选择叛逃——在任何其他情况下,合作的囚犯都会选择叛逃。尽管两个囚犯都会通过合作改善自己的处境,这意味着纳什均衡是正确的全球下到“双方合作”策略。
这一点的实际应用很明显:通过合理设计价值,当局可以让嫌疑人认罪,而不是与其同谋合作。
找到纳什均衡
一般来说,找到一个“纯”纳什均衡(没有随机化发生)是相当容易的,因为验证一个只需要比较少量的潜在收益。例如,考虑一款带有以下收益矩阵的游戏:
1. | 2. | 3. | |
1. | -1 | -2 | -1 |
2. | 2. | 2. | 1. |
3. | -1 | -1 | 0 |
在这个游戏中,每个玩家有三种策略可供选择,第一个玩家在相应的单元格中赚取价值。他的目标是最大化他的得分,而第二个玩家的目标是最小化他的得分。
当双方都没有改变策略的动机时,这个博弈的纳什均衡就出现了,即使他们知道自己的对手。这意味着
对于表示(纯)纳什均衡的单元格,它必须是其行的最小值和列的最大值
因为这是双方都不会选择改变策略的唯一方式。在上述博弈中,唯一的纯均衡是参与人1选择策略2,参与人2选择策略3,因为参与人都不希望偏离最终的收益1。
当然,“纯”纳什均衡是混合策略的特例(其中一种策略的选择概率为1),因此下面更一般的方法是普遍有效的。
在混合策略的情况下,情况变得稍微复杂一些,并且通常涉及优化策略,例如重排的不平等.举个例子来说吧:每个玩家都可以伸出一根或两根手指
- 如果显示奇数个手指,则第一个玩家将显示的手指数计分。
- 如果显示偶数个手指,则第二名玩家将按显示的手指数计分。
这对应于收益矩阵
1. | 2. | |
1. | 0, 2 | 3,0 |
2. | 3,0 | 0, 4 |
很明显,这场博弈没有纯均衡(因为如果输了,任何一方都会选择切换),因此必须对混合策略进行分析。令人惊讶的是,这场博弈中的纳什均衡偏向于第一方,尽管问题具有明显的对称性。
为了找到博弈的(或a)纳什均衡,假设纳什均衡由第一个玩家以概率选择1组成 (2)概率 ),第二个玩家有可能选择1 注意,纳什定理保证至少存在一个纳什均衡,所以这一步是有效的。现在,玩家1的预期收益是
因为这是纳什均衡,参与人1会不选择调整 知道 . 但回报可以写为 ,如果
- ,参与人1希望最小化 (设置 )
- ,玩家1希望最大化 (设置 )
这意味着在纳什均衡点, .
类似地,玩家2的预期回报是
这正好是预期的,考虑到预期收益的总和应该是零(这是a零和博弈).因此,通过类比推理, 在纳什均衡点。
因此,在纳什均衡点,参与人1的期望效用是正的,即 .这意味着游戏本质上是不公平的;通过概率选择1 玩家1担保预期的回报至少为 (玩家2选择相同的策略以最小化玩家1的预期收益)。
一般来说,两个玩家采用了相同的策略:计算预期收益其他玩家作为概率分布的函数,然后调整他们的概率以“抵消”对方的概率。看待纳什定理的另一种方式是注意到,由于预期收益在每个变量中都是线性的,这个过程会导致一个线性方程组,它总是至少有一个解。
现实的限制
纳什均衡需要几个条件才能适用:
- 所有玩家只对最大化自己的预期收益感兴趣,并会相应地采取行动。
- 所有玩家都完美地执行他们的策略。
- 所有玩家都有无限的智慧,或者至少有足够的智慧来决定解决方案。
- 每个玩家都知道(或可以推断)所有其他玩家的计划均衡策略,并且知道改变他们自己的策略不会导致其他玩家改变他们的策略。
- 所有这些常识,意思是每个玩家都知道其他玩家都满足上述四个条件。
在实践中,这些条件很少能得到直接满足。例如,
- 处于囚徒困境中的囚犯可能会面临其他考虑;例如,一个因叛逃而期望得到惩罚的囚犯所面临的困境要小得多。
- 玩家可能会意外地(或有意地)执行不完美的策略,这可能会导致失败,但也可能因为常识标准的无效而导致胜利。
- 玩家可能不够聪明,无法想出解决方案;例如,一个玩井字游戏的小孩不一定能推导出最佳玩法。
- 玩家们可能会认为,无论是对是错,他们的伙伴们都不会完全理性。这是一个主要问题,例如,在军备竞赛中——特别是在最近的核竞赛中。
由于这个原因,大多数实际情况都不能很好地用纳什均衡来模拟。这一概念在解释经济学和进化生物学的趋势时最有用,因为在这些趋势中,策略是有效的不在自然竞争中,效用最大化(如经济学中的金钱或生物学中的生存)是被拒绝的。事实上,这些领域的研究倾向于支持系统趋于其纳什均衡的理论。