Networks, Potential Functions, and the Price of Anarchy Tim Roughgarden Stanford University PRICE OF ANARCHY (1G) 2 Pigou's Example Example: one unit of traffic wants to go from s to t cost depends on congestion c(x)=x s t c(x)=1 no congestion effects Question: what will selfish network users do? •  assume everyone wants smallest-possible cost •  [Pigou 1920] 3 Motivating Example Claim: all traffic will take the top link. Flow = 1- c(x)=x Є s t c(x)=1 this flow is envious! Flow = Є Reason: •  Є > 0  traffic on bottom is envious •  Є = 0  equilibrium –  all traffic incurs one unit of cost 4 Can We Do Better? Consider instead: traffic split equally ½ c(x)=x Flow = s t c(x)=1 ½ Flow = Improvement: •  half of traffic has cost 1 (same as before) •  half of traffic has cost ½ (much improved!) 5 Braess’s Paradox Initial Network: ½ ½ x 1 s t ½ ½ x 1 Cost = 1.5 6 Braess’s Paradox Initial Network: Augmented Network: ½ ½ ½ ½ x x 1 1 s t s 0 t ½ ½ ½ ½ x x 1 1 Cost = 1.5 Now what? 7 Braess’s Paradox Initial Network: Augmented Network: ½ ½ x x 1 1 s t s 0 t ½ ½ 1 x 1 x Cost = 1.5 Cost = 2 8 Braess’s Paradox Initial Network: Augmented Network: ½ ½ x x 1 1 s t s 0 t ½ ½ 1 x 1 x Cost = 1.5 Cost = 2 All traffic incurs more cost! [Braess 68] •  also has physical analogs [Cohen/Horowitz 91] 9 High-Level Overview Motivation: equilibria of noncooperative network games typically inefficient •  e.g., Pigou's example + Braess's Paradox •  don't optimize natural objective functions Price of anarchy: quantify inefficiency with respect to an objective function Our goal: when is the price of anarchy small? –  when does competition approximate cooperation? –  benefit of centralized control is small 10