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