Skip to main content

The price of stability of (weighted) congestion games with polynomial latencies.

Giorgos Christodoulou ( University of Liverpool )

We will discuss results on the price of stability (a notion that compares the social cost of the best Nash equilibrium with the social optimum) of congestion games. We will discuss both the unweighted and weighted version of the problem. In the latter we will discuss exponential lower bounds for the case of polynomial cost functions. Our results close the previous huge gap between Θ(d) and O((d/log d)d) and almost 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 price of stability of approximate Nash equilibria, which is sensitive to the range of the players' weights.

 

 

Share this: