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.
Operations Research Seminars Amsterdam
- Speaker(s)
- Veerle Timmermans (Maastricht University)
- Date
- Thursday, 18 February 2016
- Location
- Amsterdam