MS&E246:Lecture17NetworkroutingRamesh JohariNetworkrouting• Basic definitions• Wardrop equilibrium• Braess’ paradox• ImplicationsNetworkrouting• N users travel across a network• Transportation• Internet• s = source, d = destination• J : set of links in the network• Path : chain of links from s to d• What paths do users select?Delay• Assume users experience a cost when they cross a link• Usually interpreted as delay• but could be any congestion measure(lost packets, etc.)• lj(nj) :delay of link j when used by njusersThenetworkroutinggameAssume:Strategy space of each user:Paths from s to dCost to each user:Total delay experienced onchosen pathThenetworkroutinggameFormally:• P : set of paths from s to d(Note: p ∈ P ⇒ p ⊂ J)• pr: path chosen by user r• p = (p1, …, pN)• nj(p) : number of users r with j ∈ prThenetworkroutinggameFormally:Cost to user r = total delay =Πr(p) = ∑j ∈ prlj(nj(p))Note: in this game, players minimizepayoffs.Example1N = 6; 4 links; 2 pathss dl1(n1) = 10 n1l2(n2) = n2+ 50l3(n3) = n3+ 50 l4(n4) = 10 n4Example1Nash equilibrium:s dl1= 30 l2= 53l3= 53 l4= 30Example1:summary• This Nash equilibrium is unique. (Why?)• This Nash equilibrium isPareto efficient. (Why?)• Total delay to each user: 83 minutesExample2N = 6; 5 links; 3 pathss dl1(n1) = 10 n1l2(n2) = n2+ 50l3(n3) = n3+ 50 l4(n4) = 10 n4l5(n5) = n5+ 10Example2Nash equilibrium:s dl1= 40 l2= 52l3= 52 l4= 40l5= 12Example2:summary• The Nash equilibrium is unique. (Why?)• Total delay to each user: 92 minutes• Is the Nash equilibrium Pareto efficient?Adding a link can increase delay for everyone!This is called Braess’ paradox.Braess’ paradoxWhy does Braess’ paradox occur?A form of tragedy of the commons:Players do not care about the negative externality they impose on each other.CharacterizingpureNESuppose the current path assignment is p.Player r considers switching to pr’.What is the change in player r’s payoff?Πr(pr, p-r) = ∑j ∈ prlj(nj(p-r) + 1)Πr(pr’, p-r) = ∑j ∈ pr’lj(nj(p-r) + 1)CharacterizingpureNESuppose the current path assignment is p.Player r considers switching to pr’.What is the change in player r’s payoff?CharacterizingpureNEDefine the following function V:CharacterizingpureNEObserve that:CharacterizingpureNEObserve that:CharacterizingpureNEObserve that:So: a unilateral deviation is profitableif and only if V strictly decreases.CharacterizingpureNEDefinition:A local minimum of V is a vector p such that V(p) - V(pr’, p-r) ≤ 0 for all pr’.Conclude:Any pure strategy Nash equilibrium is alocal minimum of V.CharacterizingpureNESince V has a global minimum, at least one pure NE existsIf V has a unique local minimum, thenthe game has a unique pure NEBestresponsedynamicSuppose that at each time t = 1, 2, …,a player is randomly selected, andswitches to a better path if one exists(otherwise continues on the same path).This is called the best response dynamic.Let p(1), p(2), …be the resulting path assignments.BestresponsedynamicAt each stage:If p(t + 1) ≠ p(t), then V(p(t + 1)) < V(p(t))Since V cannot decrease forever,eventually we reach a pure NE.i.e., best response dynamic converges.BestresponsedynamicThe best response dynamic has two interpretations:1) A way to find Nash equilibria (if it converges)2) A model of bounded rationality of the playersPotentialgamesThe function V is called a potential.Games with functions V such that:V(sr, s-r) - V(sr’, s-r) = Πr(sr, s-r) - Πr(sr’, s-r) for all rare called exact potential games.PotentialgamesMore generally, games with functions Vsuch thatV(sr, s-r) - V(sr’, s-r)has the same sign (+, -, or zero) asΠr(sr, s-r) - Πr(sr’, s-r) for all rare called ordinal potential games.PotentialgamesAssume strategy spaces are finite.A potential game (ordinal or exact):• has a pure strategy NE• has convergent best response dynamicBraess’ paradoxIn our games, the potential has aunique local minimum ⇒unique pure NE.In other words, the NE achieves the minimum value of V.Braess’ paradoxFind one Pareto efficient point by minimizing total delay:This is the utilitarian solution.Braess’ paradoxFind one Pareto efficient point by minimizing total delay:Note that this is not the same as V !Braess’ paradoxIn our network routing games,minimizing total delay makeseveryone strictly better off.Just like tragedy of the commons:Individual optimization does not implyglobal