We study the inefficiency of pure Nash equilibria in symmetric network congestion games defined over series-parallel networks with affine edge delays. For arbitrary networks, Correa (2019) proved a tight upper bound of 5/2 on the PoA. On the other hand, for extension-parallel networks, a subclass of series-parallel networks, Fotakis (2010) proved that the PoA is 4/3. He also showed that this bound is not valid for series-parallel networks by providing a simple construction with PoA 15/11. Our main result is that for series-parallel networks the PoA cannot be larger than 2, which improves on the bound of 5/2 valid for arbitrary networks. We also construct a class of instances with a lower bound on the PoA that asymptotically approaches 27/19, which improves on the lower bound of 15/11.
Citation
University of Wisconsin-Madison, September 2021
Article
View The Price of Anarchy in Series-Parallel Network Congestion Games