Matroids Are Immune to Braess’ Paradox

Satoru Fujishige (), Michel X. Goemans (), Tobias Harks (), Britta Peis () and Rico Zenklusen ()
Additional contact information
Satoru Fujishige: Research Institute for Mathematical Sciences, Kyoto University, Kyoto 606, Japan
Michel X. Goemans: Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Tobias Harks: Institute of Mathematics, University of Augsburg, 86135 Augsburg, Germany
Britta Peis: School of Business and Economics, RWTH Aachen University, 52072 Aachen, Germany
Rico Zenklusen: Department of Mathematics, ETH Zürich, 8092 Zürich, Switzerland; Department of Applied Mathematics and Statistics, Johns Hopkins University, Baltimore, Maryland 21218

Mathematics of Operations Research, 2017, vol. 42, issue 3, 745-761

Abstract: 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.

Keywords: nonatomic congestion games; Braess’ paradox; matroids; polymatroids (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://doi.org/10.1287/moor.2016.0825 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:42:y:2017:i:3:p:745-761

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().