A Tutorial on Game Theory for Wireless Networks

©2007LeventeButtyánandJean-PierreHubauxSecurityandCooperationinWirelessNetworks:Atutorialongametheoryforwirelessnetworksstaticgames;dynamicgames;repeatedgames;strictandweakdominance;Nashequilibrium;Paretooptimality;Subgameperfection;…SecurityandCooperationinWirelessNetworksAppendixB:Atutorialongametheoryforwirelessnetworks2/37ChapteroutlineB.1IntroductionB.2StaticgamesB.3DynamicgamesB.4RepeatedgamesSecurityandCooperationinWirelessNetworksAppendixB:Atutorialongametheoryforwirelessnetworks3/37BriefintroductiontoGameTheoryDisciplineaimingatmodelingsituationsinwhichactorshavetomakedecisionswhichhavemutual,possiblyconflicting,consequencesClassicalapplications:economics,butalsopoliticsandbiologyExample:shouldacompanyinvestinanewplant,orenteranewmarket,consideringthatthecompetitionmaymakesimilarmoves?Mostwidespreadkindofgame:non-cooperative(meaningthattheplayersdonotattempttofindanagreementabouttheirpossiblemoves)B.1IntroductionSecurityandCooperationinWirelessNetworksAppendixB:Atutorialongametheoryforwirelessnetworks4/37ClassificationofgamesNon-cooperativeCooperativeStaticDynamic(repeated)Strategic-formExtensive-formPerfectinformationImperfectinformationCompleteinformationIncompleteinformationCooperativeImperfectinformationIncompleteinformationPerfectinfo:eachplayerknowstheidentityofotherplayersand,foreachofthem,thepayoffresultingofeachstrategy.Completeinfo:eachplayercanobservetheactionofeachotherplayer.B.1IntroductionSecurityandCooperationinWirelessNetworksAppendixB:Atutorialongametheoryforwirelessnetworks5/37Cooperationinself-organizedwirelessnetworksS1S2D1D2Usually,thedevicesareassumedtobecooperative.Butwhatiftheyarenot?B.1IntroductionSecurityandCooperationinWirelessNetworksAppendixB:Atutorialongametheoryforwirelessnetworks6/37ChapteroutlineB.1IntroductionB.2StaticgamesB.3DynamicgamesB.4RepeatedgamesSecurityandCooperationinWirelessNetworksAppendixB:Atutorialongametheoryforwirelessnetworks7/37Example1:TheForwarder’sDilemma??BlueGreenB.2StaticgamesSecurityandCooperationinWirelessNetworksAppendixB:Atutorialongametheoryforwirelessnetworks8/37Fromaproblemtoagameuserscontrollingthedevicesarerational=trytomaximizetheirbenefitgameformulation:G=(P,S,U)–P:setofplayers–S:setofstrategyfunctions–U:setofpayofffunctionsstrategic-formrepresentation•Rewardforpacketreachingthedestination:1•Costofpacketforwarding:c(0c1)(1-c,1-c)(-c,1)(1,-c)(0,0)BlueGreenForwardDropForwardDropB.2StaticgamesSecurityandCooperationinWirelessNetworksAppendixB:Atutorialongametheoryforwirelessnetworks9/37SolvingtheForwarder’sDilemma(1/2)''(,)(,),,iiiiiiiiiiussusssSsSiuUiisSStrictdominance:strictlybeststrategy,foranystrategyoftheotherplayer(s)where:payofffunctionofplayeristrategiesofallplayersexceptplayeriInExample1,strategyDropstrictlydominatesstrategyForward(1-c,1-c)(-c,1)(1,-c)(0,0)BlueGreenForwardDropForwardDropStrategystrictlydominatesifisB.2StaticgamesSecurityandCooperationinWirelessNetworksAppendixB:Atutorialongametheoryforwirelessnetworks10/37SolvingtheForwarder’sDilemma(2/2)Solutionbyiterativestrictdominance:(1-c,1-c)(-c,1)(1,-c)(0,0)BlueGreenForwardDropForwardDropResult:Tragedyofthecommons!(Hardin,1968)DropstrictlydominatesForwardDilemmaForwardwouldresultinabetteroutcomeBUT}B.2StaticgamesSecurityandCooperationinWirelessNetworksAppendixB:Atutorialongametheoryforwirelessnetworks11/37Example2:TheJointPacketForwardingGame?BlueGreenSourceDest?Nostrictlydominatedstrategies!•Rewardforpacketreachingthedestination:1•Costofpacketforwarding:c(0c1)(1-c,1-c)(-c,0)(0,0)(0,0)BlueGreenForwardDropForwardDropB.2StaticgamesSecurityandCooperationinWirelessNetworksAppendixB:Atutorialongametheoryforwirelessnetworks12/37Weakdominance?BlueGreenSourceDest?'(,)(,),iiiiiiiiussusssSWeakdominance:strictlybetterstrategyforatleastoneopponentstrategywithstrictinequalityforatleastones-iIterativeweakdominance(1-c,1-c)(-c,0)(0,0)(0,0)BlueGreenForwardDropForwardDropBUTTheresultoftheiterativeweakdominanceisnotuniqueingeneral!Strategys’iisweaklydominatedbystrategysiifB.2StaticgamesSecurityandCooperationinWirelessNetworksAppendixB:Atutorialongametheoryforwirelessnetworks13/37Nashequilibrium(1/2)NashEquilibrium:noplayercanincreaseitspayoffbydeviatingunilaterally(1-c,1-c)(-c,1)(1,-c)(0,0)BlueGreenForwardDropForwardDropE1:TheForwarder’sDilemmaE2:TheJointPacketForwardinggame(1-c,1-c)(-c,0)(0,0)(0,0)BlueGreenForwardDropForwardDropB.2StaticgamesSecurityandCooperationinWirelessNetworksAppendixB:Atutorialongametheoryforwirelessnetworks14/37Nashequilibrium(2/2)***(,)(,),iiiiiiiiussusssSiuUiisSwhere:payofffunctionofplayeristrategyofplayeri()argmax(,)iiiiiiisSbsussThebestresponseofplayeritotheprofileofstrategiess-iisastrategysisuchthat:NashEquilibrium=MutualbestresponsesCaution!ManygameshavemorethanoneNashequilibriumStrategyprofiles*constitutesaNashequilibriumif,foreachplayeri,B.2StaticgamesSecurityandCooperationinWirelessNetworksAppendixB:Atutorialongametheoryforwirelessnetworks15/37Example3:TheMultipleAccessgameRew