Braess的悖论
Braess的悖论指出,与直觉相反,在道路网络中增加一条道路可能会阻碍其流动(例如,每个司机的行驶时间);同样地,关闭道路可能会改善交通时间。
当然,布雷斯悖论一般适用于交通规划和网络流量,但也适用于其他领域。例如,电力遵循许多网络设计中的相同原则,因此这种悖论也在电力网络和电子系统中体现出来。令人惊讶的是,这个悖论也出现在体育运动中:明星球员的加入实际上可以减少一个团队的效率,本质上是由于对那个球员的过度依赖。
介绍/直观的解释
如果我们都去追那个金发女郎,互相阻挠,就没人能追上她了。所以我们就去找她的朋友,但他们都会冷落我们,因为没人愿意做第二选择。但如果我们都不喜欢那个金发女郎呢?我们不会互相妨碍,也不会侮辱其他女孩。这是取胜的唯一途径。-美丽心灵(2001)
在上述情况下,金发女郎无意中让每个人的情况变得更糟,因为每个人都通过自私和/或独立的行为“阻碍了彼此”。删除金发美女(或一开始就不添加她)将改善每个成员的处境,尽管只是简单地从考虑中删除一个选项,(凭直觉来说)这种行为可能只会有害。这说明了布雷斯悖论,即(非常粗略地)指出
增加选项不一定是一件好事。
从直觉上讲,当添加的选项非常令人满意,以至于每个参与者(或几乎每个参与者)都希望选择它时,就会出现这种情况,即理想的选项变得非常稀释,就像它从一开始就没有存在过一样。
例子
例如,考虑右边的道路网络。有些道路只有一条车道,因此穿越车道的时间取决于汽车的数量 在这条路。其他道路有多条车道,因此,不管有多少辆车,都需要15分钟。如果4000辆车想要绕着这个湖行驶,自然会有两个问题要问:
- 每个司机要花多长时间才能穿过这个湖?
- 是否可以通过增加道路来缩短行驶时间?
第一个问题可以通过诉诸来解决纳什均衡,因为我们可以合理地假设,每个司机都会以一种最小化他们预期驾驶时间的方式行事。假设 很多司机选择了最上面的路 他们中的大多数选择了底层的道路。那么沿顶部路径的旅行时间是 ,沿底部路径的旅行时间为 .在平衡状态下,两者应该是相等的(否则一些司机会选择改变他们的路径),所以 .这样每位司机的总驾驶时间为20分钟。
现在假设在湖上增加了一座超快的桥,就像左边的网络一样。从直觉上讲,这只会改善司机的状况,因为他们现在有了一个额外的选择,如果他们选择忽略。然而,矛盾的是,这实际上增加了预期的旅行时间。
原因是这座桥是所以每个司机都想用它。特别是需要15分钟的两条路从来没有被利用,因为他们只是被超越 -分钟路结合2分钟桥(自 ).因此,每个司机都会选择这条路 ,使 ,以及总的旅行时间 分钟。
与纳什均衡的关系
因为旅行可以被建模为所有参与者都希望最大化他们的收益(例如最小化他们的旅行时间)的游戏,这种情况可以被理解为纳什均衡.回想一下,对于任何收益选择,至少存在一个纳什均衡;然而,纳什均衡并不一定能使所有参与者都获得最大的利益。
例如,考虑囚徒困境,其中支付矩阵可以用
鸡笼。 | 缺陷 | |
鸡笼。 | 2,2 | 0,3 |
缺陷 | 3, 0 | 1,1 |
在这样的博弈中,只有当双方都选择叛变时才会出现纳什均衡,但这不是社会最优策略;双方合作将增加双方的利益,尽管这不是一个均衡状态。换句话说,两个玩家的合作是社会最优,或更正式地说帕累托有效的:
战略概要是帕累托有效的如果没有其他策略配置,则在不降低其他参与者收益的情况下提高至少一个参与者的收益。
在囚徒困境中,“双方合作”的情况是帕累托效率,因为没有其他情况会增加一方的收益而不降低另一方的收益。然而,“双方都有缺陷”的纳什均衡状态是帕累托低效的,因为“双方都合作”的情况提高了双方的收益。
从这个意义上说,布雷斯悖论可以重新表述为
博弈的纳什均衡不一定是帕累托效率。
进一步的结果
考虑到增加一条公路并不一定会提高社会成本,接下来自然会有两个问题要问:
- 布雷斯悖论何时出现,以及/或多久出现一次?
- 当布雷斯悖论真的发生时,它对社会成本的影响有多严重?
有趣的是,这些问题的答案也是违反直觉的。直觉告诉我们,布雷斯悖论是相对罕见的,因为它似乎只在非常特定的条件下成立,而且它还表明,增加一条道路可能会严重影响社会状况。
然而,可以证明
在一个随机网络,一条边的加入引起了概率的布雷斯悖论
这个数字高得惊人。也可以证明
如果每条路的旅行时间是线性在通过它们的交通流中,增加一条边不会使总旅行时间恶化超过一个因子 .
这是一个令人惊讶(也令人欣慰)的上限,因为在实践中,穿越道路的旅行时间确实倾向于大致呈线性。