The price of anarchy in series-parallel graphs

Congestion games model self-interested agents competing for resources in communication networks. The price of anarchy quantifies the deterioration in performance in such games compared to the optimal solution. Recent research has shown that, when the social cost is defined as the maximum cost of all players, specific graph topologies impose a bound on the price of anarchy. We extend this research by providing bounds on the price of anarchy for congestion games on series-parallel networks. First we show that parallel composition does not increase the price of anarchy. This result is then used to show that the price of anarchy is bounded above by both the diameter of the graph and the number of players in the game, and that these bounds are tight. Finally we identify an important aspect of proofs for bounds on the price of anarchy: when a bound is achieved by restricting multiple parameters of the game, one should also prove that this bound cannot be realized using only a subset of these restrictions.Delft University of Technolog