The Weizmann Institute of Science
Faculty of Mathematics and Computer Science
Walmart Lecture Series in Cryptography and Complexity
Seminar Room, Room 261, Ziskind Building
on Monday, April 11, 2011
14:30 - 15:30
Tim Roughgarden
Stanford University
will speak on
The Price of Anarchy: Out-of-Equilibrium Guarantees,
Intrinsic Robustness, and Beyond
Abstract:
The price of anarchy is a measure of the inefficiency of decentralized behavior
that has been successfully analyzed in many applications, including network
routing, resource allocation, network formation, and even models of basketball.
It is defined as the worst-case ratio between the welfare of a Nash equilibrium
and that of an optimal solution. Seemingly, a bound on the price of anarchy is
meaningful only if players successfully reach an equilibrium. We introduce
"smoothness arguments", which yield performance guarantees that apply even when
players fail to reach a Nash equilibrium. We explain a sense in which the
price of anarchy of selfish routing is "intrinsically robust". We describe
recent applications of smoothness arguments to the analysis of Bayes-Nash
equilibria of auctions, and also a "local" refinement that yields the first
tight bounds on the price of anarchy in atomic splittable routing games.