We study the inefficiency of pure Nash equilibria in symmetric unweighted network congestion games defined over series-parallel networks. We introduce a quantity y(D) to upper bound the Price of Anarchy (PoA) for delay functions in class D. When D is the class of polynomial functions with highest degree p, our upper bound is 2^{p+1} − 1, which is significantly smaller than the worst-case PoA for general networks. Thus, restricting to series-parallel networks can limit the inefficiency of pure Nash equilibria. We also construct a family of instances with polynomial delay functions that have a PoA in Ω(2^p/p) when the number of players goes to infinity. Compared with the subclass of extension-parallel networks, whose worst-case PoA is in Θ(p/ln p), our results show that the worst-case PoA quickly degrades from sub-linear to exponential when relaxing the network topology. We also consider an alternative measure of the social cost of a strategy profile as the maximum players’ cost. We introduce a parameter z(D) and we show that the PoA is at most y(D)z(D), which for polynomial delays of maximum degree p is at most 2^{2p}. Compared to the PoA in general networks, which is in p^Θ(p), our results shows a significant improvement in efficiency. We finally prove that our previous lower bound in Ω(2^p/p) is still valid for this measure of social cost. This is in stark contrast with the PoA in the subclass of extension-parallel networks, where each pure Nash equilibrium is a social optimum.
Citation
University of Wisconsin-Madison, July 2022
Article
View Inefficiency of pure Nash equilibria in series-parallel network congestion games