Matroids Are Immune to Braess' Paradox
Matroids Are Immune to Braess' Paradox
复制标题
DOI：
10.1287/moor.2016.0825
复制
发表时间：
2015-04
期刊：
影响因子：
--
通讯作者：
S. Fujishige;M. Goemans;T. Harks;Britta Peis;R. Zenklusen
中科院分区：
文献类型：
--
作者：
S. Fujishige;M. Goemans;T. Harks;Britta Peis;R. Zenklusen
著名的布雷斯悖论（Braess paradox）描述了以下现象：资源的改善，就像在拥挤的网络中建造一条新街道一样，可能会导致均衡中的参与者付出更大的成本。本文考虑了一般的非原子拥塞对策，给出了不发生Braess悖论的策略空间的极大组合性质的一个刻划。简而言之，拟阵的基正是这种极大结构。我们证明了我们的特征的两个新的敏感性结果凸可分优化问题的多拟阵基多面体，这可能是独立的利益。
The famous Braess paradox describes the following phenomenon: It might happen that the improvement of resources, like building a new street within a congested network, may in fact lead to larger costs for the players in an equilibrium. In this paper we consider general nonatomic congestion games and give a characterization of the maximal combinatorial property of strategy spaces for which Braess paradox does not occur. In a nutshell, bases of matroids are exactly this maximal structure. We prove our characterization by two novel sensitivity results for convex separable optimization problems over polymatroid base polyhedra which may be of independent interest.