of 29

# Price of anarchy is independent of network topology

A presentation on Tim Roughgarden's paper on the price of anarchy.
Published on: Mar 4, 2016
Source: www.slideshare.net

#### Transcripts - Price of anarchy is independent of network topology

• 1. The Price of Anarchy is Independent of the Network Topology Tim Roughgarden (presented by Aleksandr Yampolskiy)
• 2. Outline <ul><li>Motivation </li></ul><ul><li>The Model </li></ul><ul><li>Results </li></ul><ul><li>Conclusion </li></ul>
• 3. Q: Which route would you take? suburb train station ? wide, circuitous road: 1 hour delay narrow, straight road: 20 minute delay
• 4. A: Most drivers would take the narrow road suburb train station resulting in traffic congestion
• 5. What if… <ul><li>there were a dictator who told the cars (or Internet </li></ul><ul><li>packets) which route to take? </li></ul>suburb train station red sedan must take the longer route
• 6. Outline <ul><li>Motivation </li></ul><ul><li>Model </li></ul><ul><li>Results </li></ul><ul><li>Conclusion </li></ul>
• 7. The Model <ul><li>A directed graph G = ( V , E ) </li></ul><ul><li>k source-destination pairs { s 1 , t 1 }, …, { s k , t k } </li></ul><ul><li>A rate r i ≥ 0 of traffic from s i to t i </li></ul><ul><li>Each edge e has a latency function l e ( ▪) (continuous, non-decreasing) </li></ul><ul><li>P i = a set of simple s i - t i paths and </li></ul>} ( G , r , l ) s 1 t 1 v x x 1 1 0 r 1 = 1 w s 1 ->w->t 1 s 1 -> v -> w ->t 1 s 1 ->v->t 1 Simple Paths
• 8. Flows <ul><li>Flow f: P -> R + = routes of many non-cooperative agents </li></ul><ul><li>f p = flow per path </li></ul><ul><li>f e = flow per edge = </li></ul>s 1 t 1 v x x 1 1 0 r 1 = 1 w f p 2 = ½ f p 1 = ½ edge e = ( w , t 1 ): f e = ½ + ½ = 1 l e (f e ) = 1
• 9. The Cost of a Flow <ul><li>Latency of a path P = sum of latencies of edges in P </li></ul><ul><li>Cost of a flow f = total latency incurred by f : </li></ul>s 1 t 1 v x x 1 1 0 r 1 = 1 w f p 2 = ½ f p 1 = ½ l p 1 ( f ) = ½ + 1 = 1.5 l p 2 ( f ) = ½ + 0 + 1 = 1.5 C ( f ) = ½ * 1.5 + ½ * 1.5 = 1.5
• 10. Some Assumptions <ul><li>Finding an optimal routing is difficult </li></ul><ul><li>Flows behave “selfishly” and “greedily” </li></ul><ul><li>Each network user controls a negligible fraction of the overall traffic </li></ul><ul><li>In other words: Network routing is a non- </li></ul><ul><li>cooperative game and the routes form a </li></ul><ul><li>Nash Equilibrium. </li></ul>
• 11. Nash Flows <ul><li>Def: A flow f is a Nash flow iff all traffic is routed on minimum-latency paths. Formally, </li></ul><ul><li>8 i 2 {1, ... , k } and P 1 , P 2 2 P i with f P 1 > 0, </li></ul><ul><li>l P 1 ( f ) · l P 2 ( f ) </li></ul><ul><li>Lemma: [BMW ’56] An acyclic Nash flow exists and is essentially unique. </li></ul><ul><li>Lemma: [RT ’00] In a Nash flow f , all s i - t i flow paths have equal latency L i ( f ) . </li></ul>
• 12. More on Nash Flows <ul><li>Fact: Nash flow does not optimize the total latency (cf. Prisoner’s Dilemma). </li></ul>s 1 t 1 1 x r 1 = 1 flow = ½ flow = ½ s 1 t 1 1 x r 1 = 1 flow = 0 flow = 1 C ( f* ) = ½ * 1 + ½ * ½ = ¾ C ( f ) = 0 * 1 + 1 * 1 = 1 optimal flow Nash flow [Pigou 1920]
• 13. Optimal Flows <ul><li>Def: Marginal latency </li></ul><ul><li>Lemma: [BMW ’56] An optimal flow is a Nash flow for the marginal latencies . </li></ul>s 1 t 1 1 x r 1 = 1 s 1 t 1 1 2x r 1 = 1 latency functions marginal cost functions flow = ½ flow = ½ flow = ½ flow = ½ optimal flow Nash flow
• 14. The Price of Anarchy <ul><li>Def: [KP ’99] Price of anarchy is the worst-case ratio between the cost of a Nash and of an optimal flow. </li></ul><ul><li>ρ ( G , r , l ) = </li></ul>
• 15. Outline <ul><li>Motivation </li></ul><ul><li>Model </li></ul><ul><li>Results </li></ul><ul><li>Conclusion </li></ul>
• 16. Linear Latency Functions <ul><li>Thm: [RT ’00] For linear latency functions, ρ ( G , r , l ) = C ( f ) / C ( f *) = 4/3. </li></ul>s 1 t 1 1 2x r = 1 flow = ½ flow = ½ s 1 t 1 1 x r = 1 flow = 0 flow = 1 C ( f* ) = ½ * 1 + ½ * ½ = ¾ C ( f ) = 0 * 1 + 1 * 1 = 1 latency functions marginal cost functions Nash flow: Optimal flow:
• 17. Linear Latency Functions (cont.) <ul><li>Linear latencies have the form l e (x) = a e x + b e for some a e , b e ¸ 0. </li></ul><ul><li>Marginal cost function is l e * ( x ) = 2 a e x + b e . l e * ( x/2 ) = 2 a e (x/2) + b e = l e ( x ) for each edge e. Thus, l P * ( f/2 ) = l P ( f ) for each path P . </li></ul><ul><li>Corollary: [RT ’00] The Nash flow f/2 is optimal for rate r/2 . </li></ul>
• 18. Proof Idea <ul><li>Goal: Lower bound C ( f* ) in terms of C( f ) </li></ul><ul><li>Idea: We create an optimal flow f* for ( G , r , l ) via a two-step process: </li></ul><ul><ul><li>Send a scaled down Nash flow f/2 through G . By corollary, it will be optimal for ( G , r/2 , l ). </li></ul></ul><ul><ul><li>Augment f/2 to a flow optimal for ( G , r , l ). </li></ul></ul>s 1 t 1 1 x r = 1 flow = ½ flow = 0 flow = ½ flow =0 r = ½
• 19. Proof Idea <ul><li>Goal: Lower bound C ( f* ) in terms of C( f ). </li></ul><ul><li>Idea: We create an optimal flow f* for ( G , r , l ) via a two-step process: </li></ul><ul><ul><li>Send a scaled down Nash flow f/2 through G . By corollary, it will be optimal for ( G , r/2 , l ). </li></ul></ul><ul><ul><li>Augment f/2 to a flow optimal for ( G , r , l ). </li></ul></ul>cost of f* at rate r = cost of f/2 at rate r/2 + cost of augmenting flow to rate r ≥ ¼ C ( f ) (easy) ≥ ½ C( f ) (hard) ≥ ¾ C( f )
• 20. General Latency Functions <ul><li>Can we find a similar bound on ρ ( G , r , l ) for general latency functions? </li></ul><ul><li>Unfortunately, for a general l ( · ) , the price of anarchy may be much larger than 4/3 even in a simple network: </li></ul>s 1 t 1 1 x p r = 1 s 1 t 1 1 r = 1 latency functions marginal cost functions ( p +1) x p flow = 1 flow = 0 flow = ( p + 1) -1/p flow = 1 – ( p + 1) -1/p Nash flow: Optimal flow: C ( f ) = 1 C ( f* ) = 1 – p ¢ ( p +1) -(p+1)/p =  ( )
• 21. Main Theorem <ul><li>Def: anarchy value  ( L ) 2 [1, 1 ) = how “nice” latency functions in class L are </li></ul><ul><li>Thm: Price of anarchy is independent of network topology: ρ ( G , r , l ) =  ( L ) for a standard class of functions L . </li></ul>
• 22. Upper Bound: ρ ( G , r , l ) ≤  ( L ) <ul><li>Idea: Mimic the proof for linear latencies. Scale down Nash flow f/c and then augment it to an optimal flow. </li></ul><ul><li>Problem: For non-linear latency functions, there is no constant c for which f/c is optimal for reduced rate r/c . </li></ul>
• 23. Upper Bound: ρ ( G , r , l ) ≤  ( L ) (cont.) <ul><li>Idea: Scale down Nash flow f by different factors on different edges. </li></ul><ul><li>Problem: This violates conservation constraints! </li></ul>
• 24. Upper Bound: ρ ( G , r , l ) ≤  ( L ) (cont.) <ul><li>Combining two previous ideas, we create an optimal </li></ul><ul><li>flow f* for ( G , r , l ) via a two-step process: </li></ul><ul><li>Send a pseudoflow {  e f e } e 2 E such that l e * (  e f e ) = l e ( f e ). </li></ul><ul><li>Augment the pseudoflow to an optimal flow f * </li></ul>s 1 t 1 1 x 2 r = 1 flow = 1/√3 flow = 1 - 1/√3 l(x) = x 2 , l * (x) = 3x 2 . Want 3(  x ) 2 = x 2 )  = √ 1/3
• 25. Upper Bound: ρ ( G , r , l ) ≤  ( L ) (cont.) <ul><li>Lemma: C( f* ) ¸  e l e (  e f e )  e f e +  e ( f e * -  e f e ) l e ( f e ) </li></ul>
• 26. Lower Bound: ρ ( G , r , l ) ≥  ( L )
• 27. Computing the Price of Anarchy <ul><li>So, the price of anarchy, ρ ( G , r , l ) for l 2 L is easy to compute </li></ul><ul><li>It is simply  ( L ) = the worst-possible ratio of in a two-node network: </li></ul>s 1 t 1 constant  · l r
• 28. Computing the Price of Anarchy (cont.)
• 29. Conclusion