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

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 … Read more

Inefficiency of pure Nash equilibria in series-parallel network congestion games

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} − … Read more

The Price of Anarchy in Series-Parallel Network Congestion Games

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 … Read more