Price of Anarchy for Graphic Matroid Congestion Games

This paper analyzes the quality of pure-strategy Nash equilibria for symmetric Rosenthal congestion games with linear cost functions. For this class of games, the price of anarchy is known to be \((5N-2)/(2N+1)\) , where N is the number of players. It has been open if restricting the strategy spaces of players to be bases of a matroid suffices to obtain stronger price of anarchy bounds. This paper answers this open question negatively. We consider graphic matroids, where each of the N players chooses a minimum cost spanning tree in a graph with linear cost functions on its edges. We provide constructions of graphs for \(N=2,3,4\) and for unbounded N, where the price of anarchy attains the known upper bounds \((5N-2)/(2N+1)\) and 5/2, respectively. These constructions translate the tightness of algebraic constraints into combinatorial conditions which are necessary for tight lower bound instances. The main technical contribution lies in showing the existence of recursively defined graphs which fulfill these combinatorial conditions, and which are based on solutions of a bilinear Diophantine equation.