Price of Anarchy in Paving Matroid Congestion Games

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 with delay functions in class \(\mathcal {D}\) . For both affine and polynomial delay functions, our bounds indicate that the inefficiency of pure Nash equilibria is limited by these combinatorial structures.