Research Talk: Price of Anarchy for Graphic Matroid Congestion Games Marc Uetz (UTwente MOR)

Abstract

The talk is about 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. We answer 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 fulfil these combinatorial conditions, and which are based on solutions of a bilinear Diophantine equation.
Joint work with Wouter Fokkema and Ruben Hoeksma.