Paper Info
Title
Intrinsic Robustness of the Price of Anarchy: Abstract of the Kalai Prize Talk.
Abstract
The price of anarchy is a measure of the inefficiency of selfish behavior that has been successfully analyzed in many applications, including network routing, resource allocation, auctions, 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 (first-best) solution. Seemingly, a bound on the price of anarchy is meaningful only if players successfully reach some Nash equilibrium. The main result of this paper is that for many of the classes of games in which the price of anarchy has been studied, results are \"intrinsically robust\": a bound on the worst-case price of anarchy for pure Nash equilibria *necessarily* implies the exact same worst-case bound for 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). We also discuss subsequent developments, such as generalizations to incomplete-information games with applications to mechanism design.
Year
DOI
Venue
2016
10.1145/2940716.2940797
EC
Field
DocType
Citations 
Mathematical optimization,Economics,Mathematical economics,Epsilon-equilibrium,Price of stability,Dynamic pricing,Microeconomics,Best response,Common value auction,Mechanism design,Price of anarchy,Nash equilibrium
Conference
0
PageRank 
References 
Authors
0.34
0
1
Name
Order
Citations
PageRank
Tim Roughgarden14177353.32