Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Intrinsic Robustness of the Price of Anarchy


Speaker: Tim Roughgarden, Stanford University, Computer Science
Location: 1147 MSB
Start time: Mon, Mar 1 2010, 3:10PM

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.

(This is a special seminar in the VIGRE-RFG on Optimization.)