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

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 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.