搜索
1EE800C:GametheoryforwirelessnetworksLecture2:January2420062Paretoefficiency:revisitedDef:Astrategyprofiles*issaidtobeParetooptimaliffthereexistsnootherstrategyprofiles’,suchthatifforsomejParetoefficiency:AstrategyprofileisParetooptimalifsomeplayersmustbehurtinordertoimprovethepayoffofotherplayers.jIisusususuiijj\*),()'(*),()'(∈∀≥3HowtogetNashequilibrium?•Introspectionanddeduction4CournotExample•Duopolyproducingaproduct•Strategies:quantitiesproduced•Priceofthegoods:•Utilities:•Cournotreactionfunctions:specifyeachfirm’soptimaloutputforeachfixedoutputlevelofitsopponent[]∞=∈,0iiQq()21;qqqqp+=()()()iiiiqcqpqqqu−=21,212121::QQrQQr→→()()()()()()0'')(12212121121=−+++qrcqrqrqpqrqpMax.utility:costofproduction5CournotExamplecont:•For•Thereactionfunctionsbecome•AndtheNashequilibriumis:()()()10,1,0max≤≤=−=ccqqcqqpiii()()()()2/12/1221112cqqrcqqr−−=−−=()()3/)1(*2*1*21*2*12*1cqqqrqqrq−==⇒⎥⎥⎦⎤==6HowtogettoNashequilibrium?•IntrospectionanddeductionÅuptonow•Learningorevolution–Cournotexample:playerstaketurnssettingtheiroutputsandeachplayer’soutputisabestresponsetotheoutputhisopponentchoseinthepreviousperiod.()()()(),...,,0121121210121201qrrqrqqrqq===Ifitreachessteadystate,then()()3/)1(*2*1*21*2*12*1cqqqrqqrq−==⇒⎥⎥⎦⎤==ÆSteadystateisaNasheq.7Asymptoticallystableequilibrium•Learning-typeadjustmentprocessneednotconvergetoasteadystate•IfaprocessconvergestoaparticularsteadystateforallinitialpointssufficientlyclosetoitÆasymptoticallystable•CournotexampleÆasymptoticallystable:()()()()⎪⎩⎪⎨⎧⎟⎠⎞⎜⎝⎛=−=⇒⎥⎥⎥⎦⎤==−=31,31eq.Nash2/1]1,0[01AqqrQqcqqpjjiiii8Cournotexample:evolution•UniqueNasheq.isattheintersectionofthereactioncurvesA1/21/211()122qrq=()211qrq=1q2qTheprocessconvergestoNashequilibriumfromanystartingpointÆeq.globallystable9Asymptoticstability:cont.111q2q1r2rBCDB,D=stableNasheq.C=Nasheq,butnotstableStabilityofNashequilibriumdependsontheslopeofthereactionfunctions10Asymptoticstabilitycondition•Slopeofthereactionfunction:•Sufficientconditionforequilibrium(inanopenneighborhoodoftheNasheq):•Note:Samestabilityconditionifthefirmsreactsimultaneouslyinsteadofalternativelytotheiropponent’scurrentactions222/iijiijiquqqudqdr∂∂∂∂∂−=222221122122211212211ququqquqqudqdrdqdr∂∂∂∂∂∂∂∂∂∂⇔11Example:Shapleycycle•BestresponseadjustmentprocessdoesnotnecessarilyconvergeLMRUMD0,04,55,45,40,04,54,55,40,012Adjustmentprocess•Aformofrepeatedgameplay•Playersignoretheeffectoftheircurrentactionsontheopponent’sfutureactions•Myopicplay=arepeatedgameinwhichthereisnocommunicationbetweenplayers,nomemoryofpastevents,orpredictionoffuturepayoffs.Theadaptationisbasedonthecurrentstateofthegame.•Twoconvergencedynamicspossibleinamyopicgame–Bestresponsedynamic–Betterresponsedynamic•Bothrequireadditionalconditionstoensureconvergence.13ExistenceofNashequilibria•Theorem:Everyfinitestrategic-formgamehasamixedstrategyequilibrium.–Beforegivingaproof,weneedsomefunctionalanalysisbasics–Convexset:AsetSinn-dimensionalspaceiscalledaconvexset,ifthelinesegmentjoininganypairofpointsofSliesentirelyinS.ABAB14Somemorefunctionalanalysisdefinitions•Compactset:AboundedsetSiscompactifthereisnopointx∉SsuchthatthelimitofasequenceformedentirelyfromelementsinSisx.–CompactsetÅÆclosedandbounded–Examples:anyclosedfiniteinterval[a,b],closeddisc,etc.–Notcompact:(a,b],[a,∞)15Somemorefunctionalanalysisdefinitions•ContinuousfunctionAfunctionf:X→Yiscontinuousifforallx0∈Xthefollowingconditionshold:f(x0)∈Y()0limxxfxY→∈()()00limxxfxfx→=16Convexfunctions•Aconvexfunctionisacontinuousfunctionwhosevalueatthemidpointofeveryintervalinitsdomaindoesnotexceedtheaverageofitsvaluesattheendsoftheinterval.•f(x)icconvexon[a,b]ifforanytwopointsx1,x2∈[a,b],andany0λ1,[])()1()()1(2121xfxfxxfλλλλ−+≤−+17Moreonconvexfunctions•Iff(x)hasasecondderivativeon[a,b],thenanecessaryandsufficientconditionforittobeconvexisthat()],[,0''baxxf∈∀≥Convexfunction18Concavefunction•f(x)isconcaveif–f(x)isconvex.Concavefunction19Quasi-concavity•Afunctionf()isquasi-concaveifforallxandyandalltbetween0and1•Iff()isafunctionofonevariableandissingle-peaked,thenf()isquasi-concave•fisquasi-concaveifPuisconvexforalla•Allconcavefunctionsarequasi-concave•Anymonotonictransformationofaconcavefunctionisquasi-concave())()1()()(yfyttxfyfxf≥−+⇒≥UpperLevelSet:(){}:uPxXfxa=∈≥20Example•Someutilityfunctionusedforpowercontrol•Allupperlevelsetsareconvexa1a2a321Fixedpointproperty•ForagivensetX,f:XÆX,afixedpointoffisanelementxofXsuchthatx=f(x)aa0xf(x)Afunctionfcanbeguaranteedtohaveafixedpointifitis:ContinuousMapssetintoitself(f:X→X)XiscompactandconvexExistenceoffixedpoint:22JustifiedbytheIntermediateValueTheoremIffiscontinuousonaclosedinterval[a,b],andcisanynumberbetweenf(a)andf(b)inclusive,thenthereisatleastonenumberx0intheclosedinterval[a,b]suchthatf(x0)=c.abf(a)f(b)cx023Kakutani’sfixedpointtheorem•Sufficientconditionsforf:XÆXtohaveafixedpoint:–(1)Xisacompact,convex,nonemptysubsetofafinite-dimensionalEuclidianspace–(2)f(x)isnonemptyforallx–(3)f(x)isconvexforallx–(4)f(.)hasaclosedgraph(equivalenttoupperhemi-continuity)UpperHemi-continuity:foranyx0,andforanyopensetV,that