Wolfgang Pauli Institute (WPI) Vienna

9. Pauli Kolloquium

Location: HS 2 / UZA 2 Fri, 18. Dec (Opening: 14:15) - Fri, 18. Dec 09
Topics:
Tim Roughgarden (Stanford): “Intrinsic Robustness of the Price of Anarchy”
Organisation(s)
WPI
Organiser(s)
Monika Henzinger
Norbert J. Mauser
Remark: Click HERE for the programme

Talks in the framework of this event


Tim Roughgarden (Stanford) HS 2 / UZA 2 Fri, 18. Dec 09, 14:15
“Intrinsic Robustness of the Price of Anarchy”
The price of anarchy, the most popular measure of the inefficiency of selfish behavior, assumes that players successfully reach some Nash equilibrium. We prove that for most of the classes of games in which the price of anarchy has been studied, results are "intrinsically robust" in the following sense: an upper bound on the worst-case price of anarchy for pure Nash equilibria *necessarily* implies the exact same worst-case upper bound for a much larger sets of outcomes, including mixed Nash equilibria, correlated equilibria, and sequences of outcomes generated by natural experimentation strategies (such as successive best responses or simultaneous regret-minimization). Byproducts of our work include several new results for the inefficiency of equilibria in congestion games.
Note:   Introduction by Monika Henzinger
  • Event: 9. Pauli Kolloquium (2009)

© WPI 2001-2004. www.wpi.ac.at