搜索
IntroductiontoGameTheoryLecture4•Review•MixedstrategyNashequilibrium•reviewexample•bestresponsefunctions–graphs•Game•Eliminationofstrategiesthatarestrictlydominatedbymixedstrategies•illustration•example2/32ReviewMSNEEliminationByMixingSummaryStrictvs.weakdominanceEliminationofweaklydominatedstrategiesleadsto:•strictNashequilibria•butcaneliminatenonstrictNashequilibriaThatiswhyweonlyeliminatestrictlydominatedstrategies3ReviewMSNEEliminationByMixingSummary/32MixedstrategyNE•needformakingoneselfunpredictableleadstomixingstrategies•Mixedstrategy:playerchoosesaprobabilitydistribution(p1,p2,..,pN)overhersetofactionsratherthanasingleaction•IfthereisnoNEwithoutmixing,wewillfindatleastoneMSNE(Nash-proof)•IfNEwithoutmixingexists,wemayfindadditionalMSNE4ReviewMSNEEliminationByMixingSummary/32•Review•MixedstrategyNashequilibrium•reviewexample•bestresponsefunctions–graphs•Game•Eliminationofstrategiesthatarestrictlydominatedbymixedstrategies•illustration•example5ReviewMSNEEliminationByMixingSummary/32twoNE:(B,B)and(S,S)anyMSNE?•P1mustbeindifferentbetweenBandS(otherwisenotmixing,playingpurestrategy):q*2+(1-q)*0=q*0+(1-q)*1=q=1/3BS•P2mustbeindifferentbetweenBandS:p*1+(1-p)*0=p*0+(1-p)*2=p=2/3621B(q)S(1-q)B(p)2,10,0S(1-p)0,01,2ReviewMSNEEliminationByMixingSummary/32Ifq1/3:SisbetterthanBIfq1/3:BisbetterthanSIfq=1/3:BisasgoodasS{0}ifq1/3B1(q)={p:0≤p≤1}ifq=1/3{1}ifq1/3{0}ifp2/3B2(p)={q:0≤q≤1}ifp=2/3MSNE:{1}ifp2/3{(2/3,1/3);(1/3,2/3)}721B(q)S(1-q)B(p)2,10,0S(1-p)0,01,2ReviewMSNEEliminationByMixingSummary/32•player1(2)choosesBwithprobabilityp(q)andSwithprobability1-p(1-q)8ReviewMSNEEliminationByMixingSummary/32twoNE:(T,R)and(B,L)anyMSNE?•P1mustbeindifferentbetweenTandB(otherwisenotmixing,playingpurestrategy):q*0+(1-q)*0=q*2+(1-q)*0=q=0TB•P2mustbeindifferentbetweenLandR:p*1+(1-p)*2=p*2+(1-p)*1=p=1/2921L(q)R(1-q)T(p)0,10,2B(1-p)2,20,1ReviewMSNEEliminationByMixingSummary/32Ifq0:BisbetterthanTIfq=0:BisasgoodasS{0}ifq0B1(q)={p:0≤p≤1}ifq=0{1}ifp1/2MSNE:B2(p)={q:0≤q≤1}ifp=1/2{(p,1-p);(0,1)}{0}ifp1/2p≥1/21021L(q)R(1-q)T(p)0,10,2B(1-p)2,20,1ReviewMSNEEliminationByMixingSummary/32•player1choosesTwithprobabilitypandBwithprobability1-p•player2choosesLwithprobabilityqandRwithprobability1-q11ReviewMSNEEliminationByMixingSummary/32•notjustmathematicalexercise•examples:•matchingpennies•rockpaperscissors•penaltykicks•baseballpitches•tennisservice•travelagenciespricingpolicies•makingyourselfunpredictable12ReviewMSNEEliminationByMixingSummary/32Holmesvs.Moriarty•Holmes(agenius)getsonthetrainLondon-Canterbury-DovertogettoDover•Moriarty(equallysmartguy)rentsaspecialandfollowsHolmes•Holmespreferstogetoffondifferentstation•Moriartyprefersthesamestation13MHD(q)C(1-q)D(p)0,88,-4C(1-p)4,-4-4,2ReviewMSNEEliminationByMixingSummary/32Holmesvs.Moriarty•Holmes:MoriartyknowsthatIwanttogotoD,soI’dbettergetoffinC•Holmes:MoriartyisalmostassmartasIamheknowsthisandgoestoC,soI’dbettergotoD•Holmes:ButMoriartyknowsthatIknow…14ReviewMSNEEliminationByMixingSummary/32…sowhatevermyreasoningis,Moriartywillfigureitoutandgetme15ReviewMSNEEliminationByMixingSummary/32•SolutiontoHolmes’dilemma:IfHolmeshimselfdoesnotknowwhichactionhewillchoose,MoriartycannottakeadvantageofknowingHolmes’saction=Ignoranceisabliss16ReviewMSNEEliminationByMixingSummary/32•nopurestrategyNEplayershavetomix:•forexample:{(½,½),(½,½)}–couldthiswork?•stillnoNE,weneeddifferentprobabilitiesformixing17MHD(q)C(1-q)1/2D+1/2CD(p)0,88,-44,2C(1-p)4,-4-4,20,-11/2D+1/2C2,22,-12,0.5MHD(q)C(1-q)D(p)0,88,-4C(1-p)4,-4-4,2ReviewMSNEEliminationByMixingSummary/32•howabout:{(1/3,2/3),(3/4,1/4)}–couldthiswork?•Yes,thisleadstooneMixedstrategyNE18MHD(q)C(1-q)3/4D+1/4CD(p)0,88,-42,5C(1-p)4,-4-4,22,-2.51/3D+2/3C8/3,00,02,0ReviewMSNEEliminationByMixingSummary/32•HolmesmustbeindifferentbetweenDandC(otherwisenotmixing,playingpurestrategy):q*0+(1-q)*8=q*4+(1-q)*(-4)=q=3/4DC•MoriartymustbeindifferentbetweenDandC:p*8+(1-p)*(-4)=p*(-4)+(1-p)*2=p=1/319MHD(q)C(1-q)D(p)0,88,-4C(1-p)4,-4-4,2ReviewMSNEEliminationByMixingSummary/32{1}ifq3/4B1(q)={p:0≤p≤1}ifq=3/4{0}ifq3/4{0}ifp1/3B2(p)={q:0≤q≤1}ifp=1/3{1}ifp1/3MSNE:{(1/3,2/3);(3/4,1/4)}20ReviewMSNEEliminationByMixingSummary/32•Review•MixedstrategyNashequilibrium•reviewexample•bestresponsefunctions–graphs•Game•Eliminationofstrategiesthatarestrictlydominatedbymixedstrategies•illustration•example21ReviewMSNEEliminationByMixingSummary/32•nopurestrategyisdominatedbyanotherpurestrategy•however,½D+½EstrictlydominatesF(3.5,5.5,2.5)(3,4,2)2221ABCD5,43,52,7E2,78,23,5F3,44,52,421ABCD5,43,52,7E2,78,23,5F3,44,52,4½D+½E3.5,5.55.5,3.52.5,6ReviewMSNEEliminationByMixingSummary/32•Example:•onlystrategythatisneverbestresponsetoopponent’sactionsisT•thereexistspand(1-p)suchthat:pM+(1-p)BT2321LCRT3,44,51,7M1,78,23,5B4,43,52,4ReviewMSNEEliminationByMixingSummary/32•pM+(1-p)BT•p*1+(1-p)*43=p1/3•p*8+(1-p)*34=p1/5•p*3+(1-p)*21=alwaystrue•wecanchooseforexamplep=1/42421LCRT3,44,51,7M1,78,23,5B4,43,52,4ReviewMSNEEliminationByMixingSummary/32•pM+(1-p)BT•1/4M+3/4B=(13/4,17/4,9/4)(3,4,1)=