This website uses third party cookies to improve your experience. If you continue browsing or close this notice, you will accept their use.

Matroids are Immune to Braess Paradox

6 October 2016 at 12:01 PM - 1:00 PM

Room 207, Campus on Viale Romania, 32

Speaker: Tobias Harks, Augsburg University

Matroids are Immune to Braess Paradox.


The famous Braess paradox describes the counter-intuitive phenomenonin which, in certain settings, the increase  of resources, like building a new road 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.