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.