@inproceedings{095d831fd9b44080a6f3a8a730ae54a6,

title = "Price of Anarchy for Graphic Matroid Congestion Games",

abstract = "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.",

keywords = "2024 OA procedure, Matroid, Minimum Spanning Tree, MST, POA, Price of Anarchy, Congestion Game",

author = "Wouter Fokkema and Ruben Hoeksma and Marc Uetz",

note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.; 17th International Symposium on Algorithmic Game Theory, SAGT 2024 ; Conference date: 03-09-2024 Through 06-09-2024",

year = "2024",

month = sep,

doi = "10.1007/978-3-031-71033-9_21",

language = "English",

isbn = "9783031710322",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "371--388",

editor = "Guido Sch{\"a}fer and Carmine Ventre",

booktitle = "Algorithmic Game Theory - 17th International Symposium, SAGT 2024, Proceedings",

address = "Germany",

}