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

The Impact of Collusion on the Price of Anarchy in Nonatomic and Discrete Network Games

Hayrapetyan, Tardos and Wexler recently introduced a framework to study the impact of collusion in congestion games on the quality of Nash equilibria. We adopt their framework to network games and focus on the well established price of anarchy as a measure of this impact. We first investigate nonatomic network games with coalitions. For this … Read more