Network congestion games are commonly used to model problems in large-scale networks and represent a simple, yet powerful paradigm for selfish resource sharing. These games belong to the larger class of totally unimodular congestion games and, if all the players share the same origin and destination, they admit a strongly polynomial-time algorithm to compute a pure Nash Equilibrium (PNE). Even if a PNE exists and can be efficiently computed, pure Nash equilibria could still be far from minimizing some prescribed measure of social cost. A worst-case measure of such inefficiency is the pure Price of Anarchy (PoA) and our goal is to study how symmetry and graph structure impact the PoA of network congestion games.

First, we consider affine edge delays. For arbitrary networks, Correa et al. (2019) proved a tight upper bound of 5/2 on the PoA. On the other hand, Fotakis (2010) showed that restricting to the class of extension-parallel networks makes the worst-case PoA decrease to 4/3. We prove that, for the larger class of series-parallel networks, the PoA is at most 2, and that it is at least 27/19 in the worst case, improving both the best-known upper bound and the best-known lower bound.

Next, we consider edge delays that are polynomial 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 given by Aland et al. (2006). We then establish that in games defined over series-parallel networks the PoA cannot exceed 2^{p+1} - 1, which is considerably smaller than the worst-case PoA in arbitrary networks. We also prove that the worst-case PoA, which is sub-linear in extension-parallel networks (Fotakis, 2010), dramatically degrades to exponential in series-parallel networks.

Finally, we extend the above results to the case where the social cost of a strategy profile is computed as the maximum players’ cost. In this case, the worst-case PoA is in O(4^p), which is considerably smaller than the worst-case PoA in arbitrary networks given by Christodoulou and Koutsoupias (2005). Moreover, while in extension-parallel networks each PNE is also a social optimum (Epstein et al., 2009), we construct instances of series-parallel network congestion games with exponential PoA.

This is a joint work with Bainian Hao.

BIO: Carla Michini is an assistant professor in the Industrial and Systems Engineering Department at UW-Madison since Fall 2018. Prior to that, she held postdoctoral positions at UW-Madison and ETH Zürich and she was a visiting researcher at CMU. She obtained her PhD in Operations Research at Sapienza University of Rome. Carla's research is motivated by the practical relevance of combinatorial optimization and integer programming in real-world problems. The core of her research approach consists in identifying and exploiting the polyhedral structure of various combinatorial problems to design efficient algorithms for their solution. Currently, her main goal is to leverage this approach beyond optimization, particularly in game theory and machine learning.