際際滷

際際滷Share a Scribd company logo

Routing games

Download as PPTX, PDF
Javad Ghareh Chamani
Javad Ghareh Chamani

This document outlines routing games and provides definitions for two models: non-atomic selfish routing and atomic selfish routing. For non-atomic routing, traffic is split among many players of infinitesimal size, allowing the use of convex optimization techniques to find a unique equilibrium. Atomic routing models single players who must fully route their traffic on a single path, potentially leading to multiple equilibria with different costs or no equilibrium. Additional restrictions may be needed for atomic games to guarantee an equilibrium.

1 of 27
Downloaded 11 times
Routing Games By Javad Ghareh Chamani 1
Outlines Introduction Some Definitions Non-atomic Selfish Routing Atomic Selfish Routing 2
Introduction 2 Routing models Nonatomic selfish routing Atomic selfish routing Reasons of explain Simple but general Understandability of POA Different techniques needed for analyze 3
Some Definitions Pigous example Selfish players Each player wants to minimize cost 4
Multicommodity Flow Network Directed graph G = (V, E), may have parallel edges Commodities: set of source/sink pairs: (s1, t1),,(sk , tk ) Assign each player to asome commodity nonnegative, continuous, non-decreasing cost function ce 5
Multicommodity Flow Network (cnt) Paths Routes Traffic described with flow f fP: amount of traffic of commodity i that chooses path to travel from si to ti Prescribed amount of traffic for commodity i : ri 6
Feasibility of Flow A flow f is feasible for a vector r if it routes all of the traffic 7
Cost Definition Cost of a path P with respect to a flow f fe amount of traffic using paths that contain the edge e. 8
Nonatomic Equilibrium A flow (f) is equilibrium if: no commodity can increase its gain by changing its traffic 9
Braesss Paradox One commodity wants to route 1 unit of traffic from s to t 10
Braesss Paradox(cont) New equilibrium Old cost: 1.5 New cost: 2 11
Existence & Uniqueness of Equilibrium There exists at least one equilibrium All equilibriums are equivalent (of equal cost) Using Potential Function 12
Potential Functions Let ce(x) be the cost of transporting x over some edge e The total amount spent on that edge is x.ce(x) 13
Marginal Cost and Optimality Follows from convex optimization problem nonnegativity constraints 14
Marginal Cost and Optimality(cnt) How to minimize the total marginal cost? Create a new network with the marginal cost as cost function, and find an equilibrium. 15
Back to Finding Equilibrium Remaining questions? Can we find equilibrium by finding optimal flows? What function should we minimize? 16
Potential Function We want to minimize the functions he(x) of all edges. The sum of those is called the potential function and should be minimized. 17
Consequences The potential function is convex: there exists a minimum, and therefore an equilibrium and all equilibriums form a set with the same cost 18
Atomic Selfish Routing Almost the same as the nonatomic instance. Differences: Each commodity represents ONE player instead of a large number of players. Player i must route traffic amount ri on a SINGLE path. Result: Each player must route a significant amount of traffic instead of a negligible amount. 19
Feasibility of a flow A flow f is feasible if: it routes all traffic it uses one path per player i to route ri units 20
Atomic equilibrium flow Also note: Different equilibrium flows can have different costs no uniqueness 21
Nonexistence of equilibria Traffic amount: r1 = 1; r2 = 2 P1 s -> t P2 s -> v -> t P3 s -> w -> t P4 s -> v -> w -> t 1- If player 2 takes P1 or P2, player 1 takes P4. 2- If player 1 takes P4, player 2 takes P3. 3- If player 2 takes P3 or P4, player 1 takes P1. 4- If player 1 takes P1, player 2 takes P2. This does never end. . . 22
Difference of Atomic and Non Different EQ of an atomic instance can have different costs Nonatomic EQ have same cost POA in atomic instance can be larger than nonatomic 23
Overcome nonexistence of equilibrium To guarantee an equilibrium, additional restrictions are placed on atomic instances. For instance: Give all players an equal amount of traffic which has to be routed. 24
Overcome nonexistence of equilibrium (cnt) 25
Proof In atomic instances we can discretize the potential function that was used for nonatomic instances: #Possible flows is finite. One flow f is a global minimum of 26
Proof (cnt) Claim: flow f is an equilibrium flow for instance (G,r,c). Suppose: Player i could strictly decrease cost in equilibrium flow f by deviating from path P to P , yielding the new flow f : 27

More Related Content

Routing games

  • 1. Routing Games By Javad Ghareh Chamani 1
  • 2. Outlines Introduction Some Definitions Non-atomic Selfish Routing Atomic Selfish Routing 2
  • 3. Introduction 2 Routing models Nonatomic selfish routing Atomic selfish routing Reasons of explain Simple but general Understandability of POA Different techniques needed for analyze 3
  • 4. Some Definitions Pigous example Selfish players Each player wants to minimize cost 4
  • 5. Multicommodity Flow Network Directed graph G = (V, E), may have parallel edges Commodities: set of source/sink pairs: (s1, t1),,(sk , tk ) Assign each player to asome commodity nonnegative, continuous, non-decreasing cost function ce 5
  • 6. Multicommodity Flow Network (cnt) Paths Routes Traffic described with flow f fP: amount of traffic of commodity i that chooses path to travel from si to ti Prescribed amount of traffic for commodity i : ri 6
  • 7. Feasibility of Flow A flow f is feasible for a vector r if it routes all of the traffic 7
  • 8. Cost Definition Cost of a path P with respect to a flow f fe amount of traffic using paths that contain the edge e. 8
  • 9. Nonatomic Equilibrium A flow (f) is equilibrium if: no commodity can increase its gain by changing its traffic 9
  • 10. Braesss Paradox One commodity wants to route 1 unit of traffic from s to t 10
  • 11. Braesss Paradox(cont) New equilibrium Old cost: 1.5 New cost: 2 11
  • 12. Existence & Uniqueness of Equilibrium There exists at least one equilibrium All equilibriums are equivalent (of equal cost) Using Potential Function 12
  • 13. Potential Functions Let ce(x) be the cost of transporting x over some edge e The total amount spent on that edge is x.ce(x) 13
  • 14. Marginal Cost and Optimality Follows from convex optimization problem nonnegativity constraints 14
  • 15. Marginal Cost and Optimality(cnt) How to minimize the total marginal cost? Create a new network with the marginal cost as cost function, and find an equilibrium. 15
  • 16. Back to Finding Equilibrium Remaining questions? Can we find equilibrium by finding optimal flows? What function should we minimize? 16
  • 17. Potential Function We want to minimize the functions he(x) of all edges. The sum of those is called the potential function and should be minimized. 17
  • 18. Consequences The potential function is convex: there exists a minimum, and therefore an equilibrium and all equilibriums form a set with the same cost 18
  • 19. Atomic Selfish Routing Almost the same as the nonatomic instance. Differences: Each commodity represents ONE player instead of a large number of players. Player i must route traffic amount ri on a SINGLE path. Result: Each player must route a significant amount of traffic instead of a negligible amount. 19
  • 20. Feasibility of a flow A flow f is feasible if: it routes all traffic it uses one path per player i to route ri units 20
  • 21. Atomic equilibrium flow Also note: Different equilibrium flows can have different costs no uniqueness 21
  • 22. Nonexistence of equilibria Traffic amount: r1 = 1; r2 = 2 P1 s -> t P2 s -> v -> t P3 s -> w -> t P4 s -> v -> w -> t 1- If player 2 takes P1 or P2, player 1 takes P4. 2- If player 1 takes P4, player 2 takes P3. 3- If player 2 takes P3 or P4, player 1 takes P1. 4- If player 1 takes P1, player 2 takes P2. This does never end. . . 22
  • 23. Difference of Atomic and Non Different EQ of an atomic instance can have different costs Nonatomic EQ have same cost POA in atomic instance can be larger than nonatomic 23
  • 24. Overcome nonexistence of equilibrium To guarantee an equilibrium, additional restrictions are placed on atomic instances. For instance: Give all players an equal amount of traffic which has to be routed. 24
  • 26. Proof In atomic instances we can discretize the potential function that was used for nonatomic instances: #Possible flows is finite. One flow f is a global minimum of 26
  • 27. Proof (cnt) Claim: flow f is an equilibrium flow for instance (G,r,c). Suppose: Player i could strictly decrease cost in equilibrium flow f by deviating from path P to P , yielding the new flow f : 27

Editor's Notes

  • #4: Nonatomicvery large number of player each controlling negligible fraction of traffic.Atomic each player control non-negligible amount