Title: Price of Anarchy in Paving Matroid Congestion Games
Abstract: Congestion games allow to model competitive resource sharing in various distributed systems. Pure Nash equilibria, that are stable outcomes of a game, could
be far from being socially optimal. Our goal is to identify combinatorial structures that limit the inefficiency of equilibria. This question has been mainly investigated for congestion games defined over networks. Instead, we focus on symmetric matroid congestion
games, where the strategies of every player are the bases of a given matroid. We derive new upper bounds on the Price of Anarchy (PoA) of congestion games defined over k-uniform matroids and paving matroids. For both affine and polynomial delay
functions, our bounds indicate that the inefficiency of pure Nash equilibria is limited by these combinatorial structures. This is a joint work with Bainian Hao.
![[Computer Systems Lab]](http://www.cs.wisc.edu/pics/csl_logo.gif){kind=logo}