The price of stability of weighted congestion games with polynomial latencies

14^th March 2018, 13:00
Giorgos Christodoulou
University of Liverpool

Abstract

We give exponential lower bounds on the price of stability of weighted congestion games with polynomial cost functions. Our results close the previous huge gap between ?(d) and O((d/log d)^d) and asymptotically matches the price of anarchy upper bound for polynomial latencies of degree d. On the positive side, we give a general upper bound on the PoS of approximate Nash equilibria, which is sensitive to the range W of the player weights.

Joint work with: Martin Gairing (UoL), Yiannis Giannakopoulos (TU Munich), Paul Spirakis (UoL, CEID).

Additional Materials

• https://arxiv.org/pdf/1802.09952.pdf