Operations Research Seminars Amsterdam

Speaker(s)
Veerle Timmermans (Maastricht University)
Date
Thursday, 18 February 2016
Location
Amsterdam

We study uniqueness of Nash equilibria in atomic splittable congestion games and derive a uniqueness result based on matroid theory: when the strategy space of every player is the set of bases of a base orderable matroid, equilibria are unique. This result can even be generalized to the setting of polymatroid congestion games, were  we introduce the class of directed flow polymatroids. On the other hand we show that matroidal set systems are in some sense necessary to guarantee uniqueness of equilibria: for every atomic splittable congestion game with at least three players and non-matroidal set systems per player, there is an isomorphic game having multiple equilibria. Our results leave a gap between base orderable matroids and general matroids for which we do not know whether equilibria are unique.