DOC PREVIEW
Berkeley ELENG 228A - OPTIMAL ROUTING CONTROL: REPEATED GAME APPROACH

This preview shows page 1 out of 3 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 3 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 3 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

Berkeley ELENG 228A - OPTIMAL ROUTING CONTROL: REPEATED GAME APPROACH

Documents in this Course
FAST TCP

FAST TCP

57 pages

Load more
Download OPTIMAL ROUTING CONTROL: REPEATED GAME APPROACH
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view OPTIMAL ROUTING CONTROL: REPEATED GAME APPROACH and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view OPTIMAL ROUTING CONTROL: REPEATED GAME APPROACH 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?