著名的布雷斯悖论(Braess paradox)是德国数学家Dietrich Braess在1968年发现的自私路由中一个反直观现象：移除网络的某些链接反而能够提高网络系统均衡的效率 —— 降低路由的延迟。布雷斯悖论表明博弈均衡缺乏效率，而且在现实生活中屡见不鲜。在交通繁忙的市区，建一条新路，分流拥挤的交通似乎是一个不错的想法，但根据布雷斯悖论，结果正好相反：对于出行的个体来说，往交通网络中增加一条新路线会增加他们所有人的出行时间（如果他们都想通过这条新路抄近道）。另外，韩国首尔的规划者拆除一条6车道高速路，修建了一个方圆8千米的公园后，很多道路专家惊讶地发现，首尔的交通非但没有恶化，反而得到了改善。其实这就是布雷斯悖论反向版。

2006年Tim Roughgarden在研究布雷斯悖论对系统效率影响的严重性时，提出一个公开问题：什么样的网络拓扑可以防止布雷斯悖论的发生？这一问题的解决对于网络设计具有重要指导意义。以色列数学家IgalMilchtaich在博弈论的顶尖期刊《Games and Economic Behavior》就无向网络单源单汇的特殊情形部分解决了该问题，并特别指出多源多汇无向网络的情形还是一个未决的问题。

信息技术部陈旭瑾等最近不仅成功的解决了Milchtaich遗留的问题，而且对于所有（无向或有向）网络任意多对源汇的情形得到了不发生布雷斯悖论的网络拓扑的统一刻画，从而完整的回答了Tim Roughgarden的公开问题。所得的成果是Milchtaich结果的意义深远的推广，是在刻画“无悖论”性质方面一个很好的（填补空缺的）结果，对促进人们理解网络结构与均衡流性质之间的联系有很大贡献。

相关论文：

Network Characterizations for Excluding Braess’sParadox

Xujin Chen, ZhuoDiao, Xiaodong Hu

Theory of Computing Systems, accepted for publication

http://link.springer.com/article/10.1007/s00224-016-9710-4