1OPTIMAL ROUTING CONTROL:OPTIMAL ROUTING CONTROL:OPTIMAL ROUTING CONTROL:OPTIMAL ROUTING CONTROL:REPEATED GAME APPROACHREPEATED GAME APPROACHREPEATED GAME APPROACHREPEATED GAME APPROACHRichard J. La and Venkat AnantharamEE228a Presentation Slobodan MaticMotivation Bandwidth demand efficient routing schemes Network access providers compete to offer services and to minimize their costsnoncooperative game Providers interact several times before game changesand they should have an incentive to cooperate repeated game Equilibrium of the interaction: no unilateral deviationNash equilibrium point (NEP) Fixed demand: total system cost measures network efficiency Goal: move towards the system minimum and stay in NEP’s reduce the costs for some, others do not want to deviate→→→→→→→→→→→→→→→→Repeated Games Interaction occurs several times strategy: history-based plan of actions perfect information games (all actions taken known) infinite games (game end is unknown) Discounted games: NEPs not only repeating a stage game NEP problem with NEP’s: an action may be irrationalSPNEPSPNEPSPNEPSPNEP: NEP for every possible game continuation)1(),0()( <=δδrnrn))(),...,(()1(10nsnsrrIinni∑∞=−=δδCooperation in Repeated Games static gameaverage rewards per unit timeclose to one: rational (SPNEP) strategies that enforce cooperation Main idea: any gain from a deviation will be outweighedby the penalty in the stages after the deviation Prisoners’ Dilemma example: credible threat strategy: “I will choose to mum as long as you do. If you choose fink once, I will fink thereafter.” if is sufficiently large this strategy is SPNEP and enforces the decisions (mum,mum) forever:0→δ:1→δδδGames - Results Simultaneous strategyi-th player’s cost function Rosen's theorem (static game)is continuous in and convex inNEP existencesatisfies diagonally strict convexity conditionNEP uniqueness i-th player’s reservation cost folk theorem (repeated game)For each vectorv with there is s.t. for all there is a NEP with the cost vector vIFF ××∈ ...1f=−∈∈−−),(minmaxiiiFfFfifJviiiif),...,()(1 IiiffJJ =fiJfifiJ→→iivv < 1<δ)1,(δδ∈Games – Results (2) Friedman’s theorem (repeated)Let a stage game NEP has cost eFor each vector v with there is s.t. for all there is a SPNEP with the cost vector v Fudenberg-Maskin’s theorem (repeated game)Let v be the reservation costIf the set is fully dimensionalthere is a SPNEP with the cost vector viiev < 1<δ)1,(δδ∈{}Iivvii≤≤≤ 1,|v2Main Problem Existence of SPNEP’s that cost less than single stage NEP’s Two-node parallel link networks General networks single source-destination pair multiple source-destination pairs...SDSDS1D1S2D2Parallel Links – Game Model I users with demand ratesL links with capacities(stability constraint) : user i sends over link l (nonnegativity), (demand constraint) : i-th user flow configuration, : flow configuration: total flow on l-th link : performance measure – cost function is NEP if for all Iiri≤≤1,LlCl≤≤1,ilf0>ilf∑∈=Iiiilrfiflf),...,(1 Ifff =)( fJi)~,...,~(~1 Ifff =Ii ≤≤1)~,...,~,,~,...,~(min)~,...,~,~,~,...,~()~(111111IiiiiFfIiiiiifffffJfffffJfJii+−∈+−==...SD∑∑∈∈≤=LllIiiCrRParallel Links – Cost Function Type-B cost functions, where cost per unit flow is a function of the residual capacity is positive, strictly increasing in , and convexconvexconvexconvex(total flow rate capacity) the cost gets large Typical type-B cost function)()(),(llilllillililfCTffTfffJ −⋅=⋅=∑≤≤=LllililiffJfJ1),()()(llfTlfllllCffT →∞→ as,)(→⇒≥∞<−=llllllllCfCffCfT,,1)(Parallel Links – Static Game Competitive Routing in Multiuser Communication Networks[Orda,Rom,Shimkin] Rosen’s theorem unique NEP Total operation costconvex optimization unique optimal configuration with min cost NEPs are not efficient: can be far from optimum∑≤≤=IiifJfC1)()(f′C′→→Parallel Links – Repeated Game T1: If is close to one there is an NEPNEPNEPNEP in the repeated game that achieves the minimumminimumminimumminimum system cost fairness: the same cost per unit flow for every user if is a stage game NEP then possibly T2: If is close to one there is an SPNEPSPNEPSPNEPSPNEP in the repeated game that achieves the minimumminimumminimumminimum system costand the cost of each user is at most equal to its cost in the stage game NEP (for each i, ) if then decrease in the total system cost benefits all usersδC′⋅′⋅′==RrfRrfffffiLiiI,...,~),~,...,~(~11f)()~( fJfJii>f~δfˆC′)()ˆ( fJfJii≤CC′>)()ˆ( fJfJii<Single Source-Destination Pair Network model topology same: demand, capacity modelType-B cost function different: paths share links Unique flow configuration with minimum cost assumption: two paths with different cost per unit flow T3: If is close to one there is an NEPNEPNEPNEP in the repeated game that achieves the minimumminimumminimumminimum system cost users with small demands use the paths with smallest cost per unit T4: Any optimal NEP flow configuration is SPNEPSDVVLLVG ×⊆= ),,(f′C′δC′3Multiple Source-Destination Pairs Different users have different SD pairs Uniqueness of the minimal cost configuration: openopenopenopen Negative result : uniqueness holds, but no matter how close is, NEP does not exist C1=8C2=8C3=50C6=10C4=C5=2000S1S2D1,D2r1=40, r2=4.857C′δ64.0,32.421== vv94.0)(,81.3)()85.4,0,0,5.38,5.1,5.1(),...,,(21621=′=′==′fJfJffffNEPno)(22→′< fJvSummaryNANO?MultipleSD pairsNOYESYESSingleSD pairYESYESYESParallel linksSPNEP cost less than in stage gameSPNEPUnique
View Full Document