Al fine di migliorare la tua esperienza di navigazione, questo sito utilizza i cookie di profilazione di terze parti. Chiudendo questo banner o accedendo ad un qualunque elemento sottostante acconsenti all’uso dei cookie.

Matroids are Immune to Braess Paradox

6 ottobre 2016 ore 12:01 - 13:00

Aula 207, Sede di 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.