Title: Smoothness arguments and the price of anarchy
Speaker: Tim Roughgarden, Stanford University
Date: Wednesday, September 26, 2012 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
The price of anarchy is a measure of the inefficiency of decentralized behavior that has been successfully analyzed in many systems. It is defined as the worst-case ratio between the welfare of an equilibrium and that of an optimal solution. Seemingly, a bound on the price of anarchy is meaningful only if players successfully reach an equilibrium. Our main result is 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: a bound on the worst-case price of anarchy for equilibria necessarily implies the exact same worst-case bound for a much larger set of outcomes, such as the possible sequences generated by no-regret learners. We also describe recent applications to the analysis of Bayes- Nash equilibria in (non-truthful) mechanisms, and a "local" refinement of the framework that yields tight bounds on the price of anarchy in atomic splittable congestion games.