PLEASE NOTE THAT THE TITLE OF THIS TALK HAS BEEN CHANGED. 
 
                     The  Weizmann  Institute  of  Science
                  Faculty of Mathematics and Computer Science
 
                    Foundations of Computer Science Seminar
 
                    Seminar Room, Room 261, Ziskind Building
                           on Monday, April 11, 2011
                                 14:30 - 15:30
 
                                Tim Roughgarden
                              Stanford University
 
                                 will speak on
 
Title:  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.




 
---------------------------------------------------------
Technion Math Net-2 (TECHMATH2)
Editor: Michael Cwikel   <techm@math.technion.ac.il> 
Announcement from: Diana Mandelik   <diana.mandelik@weizmann.ac.il>