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.