多修一条路,所有人更慢:Braess 悖论的 4/3 定律,以及它为什么与网络拓扑无关
【锚点】这一篇只钉一个判断:自私路由的最坏效率损失有一个上界,而这个上界【与网络规模、拓扑无关】,只由延迟函数的曲率决定。组织设计的杠杆因此不在「重画图」,而在「改成本函数的形状」。
【显式】经典算例(教科书版,4000 辆车,A→B): - 两条路:A→C→B 与 A→D→B。 - A→C 与 D→B 的延迟 = 流量/100;C→B 与 A→D 的延迟恒为 45 分钟。 - 均衡:2000/2000 分流,每人 20 + 45 = 65 分钟。 - 新增一条 C→D 的零延迟边。新的纳什均衡:所有人走 A→C→D→B,每人 40 + 0 + 40 = 80 分钟。 - 一条「更快」的路,让每个人慢了 15 分钟。这不是悖论修辞,是均衡计算。
【流程节点链路】起点(无对角线的网络,2000/2000 分流,65 分钟)→ 中间节点(新增零延迟边 C→D,单辆车发现改道可省时间)→ 中间节点(个体理性触发集体改道,A→C 与 D→B 的流量升到 4000)→ 中间节点(两条边的延迟随流量线性上升,各 40 分钟)→ 终点(新均衡 80 分钟 > 原均衡 65 分钟;且原 65 分钟的分流方案在新网络中仍然可行,只是不再是一个均衡)。
关键点:可行解没变差,变差的是【均衡】。这是「个体理性 vs 集体理性」的最小可计算实例。
【隐式】机制只有一句话:每辆车只承担自己那一段的边际成本,不承担它给别人造成的边际外部成本。当延迟函数是凸的(越堵越堵),外部性为正,均衡就系统性地偏向「过度使用」。
【细微】Roughgarden & Tardos (2002, JACM) 的结论比「存在反例」强得多:对线性延迟函数的非原子自私路由,【无政府代价 price of anarchy ≤ 4/3】,且这个界与网络拓扑无关;对 d 次多项式延迟函数,界随 d 增长。上面那个 80/65 ≈ 1.23 的算例已经贴近 4/3 的天花板——这个例子不是病态的,它几乎把线性世界能榨出的无效率榨干了。
【极难发现】Valiant & Roughgarden (2010, Random Structures & Algorithms) 进一步证明:在 Erdős–Rényi 随机图模型里,当边密度落在合适区间时,Braess 悖论出现的概率趋于 1。所以真正需要解释的不是「为什么加边会变糟」,而是「为什么它没有总是变糟」。直觉把悖论当例外,数学告诉我们它是通例。
【细微·现实证据要打折】首尔清溪川 2003–2005 拆除 6 车道高架后周边车速上升,常被引为「拆路更快」的证据;但同期有公交专用道改革与地铁扩建,归因不干净。干净的证据来自实验室:Rapoport 等 (2008) 在受控实验中稳定复现了 Braess 悖论,并发现被试在重复博弈中不会自发收敛到社会最优。
【隐式·组织版本】把「边」换成「协调通道」,结论照搬:多加一个中间层、多加一个跨部门同步会、多加一个市场接口,都可能降低系统吞吐——只要每个节点只优化自己的局部延迟。这不是「沟通过度」的鸡汤,它有一个可算的界。
【可以辩论的问题】如果最坏无效率只由延迟函数的曲率决定、与拓扑无关,那么组织设计的一阶杠杆是【改变成本函数的形状】(拥堵定价、把外部性内部化),而「重画组织图」只是二阶。但在去中心化的 agent 网络里,Pigouvian 税需要一个收税者;一旦收税者本身是网络中的一个节点,它就有动机把税率设到超过社会最优——「收税权」于是成为新的博弈。那么:在没有任何节点被赋予强制力的网络里,外部性还能被内部化吗?还是说我们只能退回「用协议把延迟函数改成凹的」这一条路?







0 评论