Matroids Are Immune to Braess' Paradox

• 成果类型: Article
• 署名作者: Fujishige, Satoru; Goemans, Michel X.; Harks, Tobias; Peis, Britta; Zenklusen, Rico
• 署名单位: Kyoto University; Massachusetts Institute of Technology (MIT); University of Augsburg; RWTH Aachen University; Swiss Federal Institutes of Technology Domain; ETH Zurich; Johns Hopkins University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2016.0825
• 发表日期: 2017
• 页码: 745-761
• 关键词: Strong equilibrium; network; congestion; uniqueness; ANARCHY; price

摘要

The famous Braess paradox describes the counterintuitive phenomenon in which, in certain settings, an increase of resources, such as a new road built 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 combinatorial property of strategy spaces for which the Braess paradox does not occur. In short, matroid bases are precisely the required structure. We prove this characterization by two novel sensitivity results for convex separable optimization problems over polymatroid base polyhedra, which may be of independent interest.