AG 1   Info

AG Audience

English

30 Minutes

Saarbrücken

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.

Alkmini Sgouritsa

--email hidden

passcode not visible

logged in users only