We study the inefficiency of pure Nash equilibria in symmetric unweighted network congestion games. We first explore the impact of symmetry on the worst-case PoA of network congestion games. For polynomial delay functions with highest degree p, we construct a family of symmetric congestion games over arbitrary networks which achieves the same worst-case PoA of asymmetric network congestion games. Next, we explore the impact of network structure within the class of symmetric network congestion games. For delay functions in class *D* we introduce a quantity y(*D*) and we show that the PoA is at most y(*D*) in games defined over series-parallel networks. Thus, for polynomial delays with highest degree p, the PoA cannot exceed 2^{p+1} - 1, which is significantly smaller than the worst-case PoA in games defined over arbitrary networks. Moreover, we prove that the worst-case PoA quickly degrades from sub-linear to exponential when relaxing the network topology form extension-parallel to series-parallel. Finally, we consider measuring the social cost as the maximum players' cost. For polynomial delays of maximum degree p we show that the worst case PoA is significantly smaller than that of general symmetric congestion games, but dramatically larger than that of games defined over extension-parallel networks.

## Article

Download

View Inefficiency of pure Nash equilibria in network congestion games: the impact of symmetry and graph structure