Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:The price of stability of (weighted) congestion games with polynomial latencies
Speaker:George Christodoulou
coming from:University of Liverpool
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1
We use this to send out email in the morning.
Level:AG Audience
Language:English
Date, Time and Location
Date:Monday, 27 May 2019
Time:13:00
Duration:30 Minutes
Location:Saarbrücken
Building:E1 4
Room:024
Abstract
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.
Contact
Name(s):Alkmini Sgouritsa
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Note:
Attachments, File(s):
  • Alkmini Sgouritsa, 05/26/2019 02:46 PM
  • Alkmini Sgouritsa, 05/24/2019 02:36 PM
  • Alkmini Sgouritsa, 05/22/2019 10:01 AM
  • Alkmini Sgouritsa, 05/22/2019 09:59 AM -- Created document.