產(chǎn)業(yè)組織理論授課課件-IO-slides-introtogames

Non-CooperativeGameTheoryTodefineagame,youneedtoknowthreethings:ThesetofplayersThestrategysetsoftheplayers(i.e.,theactionstheycantake)ThepayofffunctionsNon-CooperativeGameTheoryTo1GameAPlayersStrategysetsforeachplayerPayoffsforeachplayer,foreachpossibleoutcomePayofftoRowPayofftoColumnGameAPlayersStrategysetsfor2GameBGameB3Whathappenedinthesetwogames?Whatwerethestrategies?Whatweretheoutcomes?Whydidwegettheseoutcomes?Shouldwehaveexpectedtheseoutcomes?Inotherwords--Howdowesolvethesegames?Whathappenedinthesetwogam4SolvingGamesWearelookingfortheequilibrium.Whatisequilibrium?Equilibriumisastrategycombinationwherenooneplayerhasanincentivetochangeherstrategygiventhestrategiesoftheotherplayers.Huh?SolvingGamesWearelookingfo5GameAGameA6NashEquilibrium(NE)Formally,asetofstrategiesformsaNEif,foreveryplayeri,i(si,s-i)

i(si*,s-i).Notethattheequilibriumisdefinedintermsofstrategies,notpayoffs.Whyisthisasolution?Becauseit’sarestpoint-noincentiveforoneplayertochangeunilaterally.NashEquilibrium(NE)Formally,7HowDoWeFindNE?EliminationofDominatedStrategies.Aplayerhasadominatedstrategyifthereisoneaction/strategywhichalwaysprovidesalowerpayoffthananotherstrategy,nomatterwhatotherplayersdo.Ifyoucrossoffalldominatedstrategies,sometimesyouareleftwithonlyNE.HowDoWeFindNE?Elimination8GameAGameA9RepeatedeliminationcanfindtheNERepeatedeliminationcanfind10EliminationofdominatedstrategiesonlyworksifthestrategiesarestrictlydominatedAlwaysworse,notjustequaltoorworseEliminationofdominatedstrat11Sometimestherearen’tdominatedstrategiessoyouhavetocheckforNEcellbycellSometimestherearen’tdominat12Sometimestherearen’tanyNESometimestherearen’tanyNE13Wecanusethe“Normal”ormatrixformif:Thereareonly2(sometimes3)playersThereareafinitenumberofstrategiesActionsapproximatelysimultaneousIfactionsaresequential,mustuseanotherform,the“Extensive”form:Stillonlyreallyfeasiblefor2or3players,althoughcanaccommodate“chance”StillmusthavefinitenumberofstrategiesWecanusethe“Normal”ormat14ExtensiveFormGamesUseagame“tree”todepicttheorderinwhichplayersmakedecisionsandthechoicesthattheyhaveateachdecisionpoint.Decisionpointsarecalled“nodes”.Players’strategiesorchoicesbranchofffromeachdecisionnode.Attheendofeachbranchonthegametreearethepayoffstheplayerswouldreceiveifthatbranchwerethepathfollowed.ExtensiveFormGamesUseagame15USvs.SaudiArabiaOil“Game”QuotaTariffNothingRRRNNN90,80100,6075,50100,6040,8050,100USSaudiArabiaUSvs.SaudiArabiaOil“Game”16SolvingExtensiveFormGamesNashEquilibriumhasthesamemeaninginextensiveformgamesasinnormalformgames.Thereisalsoanothersolutionconceptinextensiveformgames,theSubgamePerfectEquilibrium(SPE)strategywhichhassomeadvantagesoverNashEquilibrium.SolvingExtensiveFormGamesNa17USvs.SaudiArabiaOil“Game”QuotaTariffNothingRRRNNN90,80100,6075,50100,6040,8050,100USSaudiArabiaSubgame=partoflargergamethatcanstandaloneasagameitself.USvs.SaudiArabiaOil“Game”18Sub-GamePerfectEquilibriumAsubgamecanbedefinedforanynodeotherthanaterminal(payoff)node,andincludesallofthesubsequent“branches”ofthetreethatemanatefromthatnode.ForastrategytobeaSubgamePerfectEquilibrium(SPE)strategy,itcanonlycontainactionsthatareoptimalfortheirrespectivesubgames.Sub-GamePerfectEquilibriumA19QuotaTariffNothingRRRNNN90,80100,6075,50100,6040,8050,100USSaudiArabiaXQuotaTariffNothingRRRNNN90,20QuotaTariffNothingRRRNNN90,80100,6075,50100,6040,8050,100USSaudiArabiaTofindalloftheSubgamePerfectEquilibria:Foreachsubgame,determinetheoptimalstrategy.XXXFindtheoptimalstrategyforthe“pruned”tree.QuotaTariffNothingRRRNNN90,21QuotaTariffNothingRRRNNN90,80100,6075,50100,6040,8050,100USSaudiArabiaCompareSubgamePerfectEquilibria(SPE)toNE:NEcanincludeincrediblethreats,alongasunilateralchangesarenotoptimal.Example:Quota;RifQuotaorTariff,NifNothingQuotaTariffNothingRRRNNN90,22AnotherExampleEnterStayOutHighPLowPHighPLowP2,2-1,00,50,0EntrantIncumbentFindoptimalstrategyforeachsubgame(prunethetree).FindEntrant’soptimalaction.XXAnotherExampleEnterStayOutHi23RepeatedGamesInrepeatedgames,strategiesaremuchricher.Inaone-shotPrisoner’sDilemmagame,playerscaneithercooperateordefect.Inarepeatedgame,playerschoosewhethertocooperateordefecteachperiod.Playerscanhavestrategiesthatarecontingentontheotherplayer'sactions.Cooperateiftheotherplayercooperatedlastperiod.Defectiftheotherplayerhaseverdefected.Note:Inrepeatedgames,mustdiscountfuturepayoffs.(1/(1+r))t=t

isthediscountfactorforperiodt.RepeatedGamesInrepeatedgame24SolvingRepeatedGamesIfthegamehasafinitehorizon(thatis,itendsafteraspecifiednumberofrounds),youusebackwardsinduction.StartbyfindingtheoptimalstrategyinthelastperiodMovetothenexttothelastperiod,andfindtheoptimalstrategy,recognizingtheeffectsonthefinalround.Ifthegamehasaninfinitehorizon,youcan'tusebackwardsinductionbecausethereisnolastperiod.Tosolveinfinitehorizongames,youcheckdifferentstrategiestoseeiftheymeettherequirementsofequilibrium.Foreachplayer,changingstrategiesunilaterallywillnotmaketheplayerbetteroff.SolvingRepeatedGamesIftheg25SolvingRepeatedPrisoner’sDilemmaGamesForfinitehorizonrepeatedPD,usebackwardsinduction.Inthelastperiod,alwaysoptimaltodefectIfyouractioninthenext-to-the-lastperioddoesnotaffecttheoptimalstrategyinthelastperiod,youdobetterbydefectinginthenexttothelastperiodAndsoon….ForfinitehorizonrepeatedPD,collusionisneveroptimal.SolvingRepeatedPrisoner’sDi26SolvingRepeatedPrisoner’sDilemmaGamesForinfinitehorizonrepeatedPD,considerdifferentstrategies.“GrimTrigger”strategy:Cooperateaslongasotherplayercooperates,butoncehedefects,defectforever.Hisdefection“triggers”thepunishment.“Grim”becausepunishmentlastsforever.Tocheckifthereisasymmetricequilibriumwithtriggerstrategies:Makesurethatcooperatingisbetterthandefectingifotherplayerhascooperated.Makesurethat“punishment”isacrediblethreat,thatyouwillactuallygothroughwithit.SolvingRepeatedPrisoner’sDi27Prisoner’sDilemmaPrisoner’sDilemma28WhenAreTriggerStrategiesareNE?Assumeotherplayeralsousingatriggerstrategy.Ifneitherhasdefected,bothcooperatethisperiod.Ifyoufollowthetriggerstrategy,erate,yougetCthisperiod(thepayofffromcooperation)andyougetCeachperiodinthefuture.AninfinitestreamofpaymentsofCcanbewrittenas1/(1-)*C.Ifyoudefect,yougetDthisperiod(theincreasedpayofffromunilateraldefection)butinallfutureperiodsyougetP(thepunishmentpayofflevel)TotalearningsthusareD+/(1-)*P.

Thusfollowingthestrategyisoptimalif: 1/(1-)*C>D+/(1-)*P.

WhenAreTriggerStrategiesar29WhenAreTriggerStrategiesareNE,con’t?Thecondition1/(1-)*C>D+/(1-)*Pcanberewrittenas:

>(D-C)/(D-P)Sothediscountfactor,,mustbesufficientlylargeforcollusiontobesustainable.Howdoweinterpretthis?Ahighdiscountfactormeansthatpayoffsinthefuturearerelativelyimportant.Youarewillingtoforsakeimmediate,buttransitorygainsfromdefectionforhigherpayoffsinthefuture.WhenAreTriggerStrategiesar30WhenAreTriggerStrategiesareNE,con’t?Ispunishmentacrediblethreat?Onceagain,assumeotherplayeralsousingatriggerstrategy.Ifeitherhasdefected,bothwillpunishthisperiod.Ifyoufollowthetriggerstrategy,i.e.punish,yougetPthisperiodandyougetPeachperiodinthefuture.Ifyoudon’tpunish,youwillgetalowerpayoff,sincedefectingisabestresponsetootherplayersplayingdefecting.Thereforethepunishmentisacrediblethreat.WhenAreTriggerStrategiesar31Non-CooperativeGameTheoryTodefineagame,youneedtoknowthreethings:ThesetofplayersThestrategysetsoftheplayers(i.e.,theactionstheycantake)ThepayofffunctionsNon-CooperativeGameTheoryTo32GameAPlayersStrategysetsforeachplayerPayoffsforeachplayer,foreachpossibleoutcomePayofftoRowPayofftoColumnGameAPlayersStrategysetsfor33GameBGameB34Whathappenedinthesetwogames?Whatwerethestrategies?Whatweretheoutcomes?Whydidwegettheseoutcomes?Shouldwehaveexpectedtheseoutcomes?Inotherwords--Howdowesolvethesegames?Whathappenedinthesetwogam35SolvingGamesWearelookingfortheequilibrium.Whatisequilibrium?Equilibriumisastrategycombinationwherenooneplayerhasanincentivetochangeherstrategygiventhestrategiesoftheotherplayers.Huh?SolvingGamesWearelookingfo36GameAGameA37NashEquilibrium(NE)Formally,asetofstrategiesformsaNEif,foreveryplayeri,i(si,s-i)

i(si*,s-i).Notethattheequilibriumisdefinedintermsofstrategies,notpayoffs.Whyisthisasolution?Becauseit’sarestpoint-noincentiveforoneplayertochangeunilaterally.NashEquilibrium(NE)Formally,38HowDoWeFindNE?EliminationofDominatedStrategies.Aplayerhasadominatedstrategyifthereisoneaction/strategywhichalwaysprovidesalowerpayoffthananotherstrategy,nomatterwhatotherplayersdo.Ifyoucrossoffalldominatedstrategies,sometimesyouareleftwithonlyNE.HowDoWeFindNE?Elimination39GameAGameA40RepeatedeliminationcanfindtheNERepeatedeliminationcanfind41EliminationofdominatedstrategiesonlyworksifthestrategiesarestrictlydominatedAlwaysworse,notjustequaltoorworseEliminationofdominatedstrat42Sometimestherearen’tdominatedstrategiessoyouhavetocheckforNEcellbycellSometimestherearen’tdominat43Sometimestherearen’tanyNESometimestherearen’tanyNE44Wecanusethe“Normal”ormatrixformif:Thereareonly2(sometimes3)playersThereareafinitenumberofstrategiesActionsapproximatelysimultaneousIfactionsaresequential,mustuseanotherform,the“Extensive”form:Stillonlyreallyfeasiblefor2or3players,althoughcanaccommodate“chance”StillmusthavefinitenumberofstrategiesWecanusethe“Normal”ormat45ExtensiveFormGamesUseagame“tree”todepicttheorderinwhichplayersmakedecisionsandthechoicesthattheyhaveateachdecisionpoint.Decisionpointsarecalled“nodes”.Players’strategiesorchoicesbranchofffromeachdecisionnode.Attheendofeachbranchonthegametreearethepayoffstheplayerswouldreceiveifthatbranchwerethepathfollowed.ExtensiveFormGamesUseagame46USvs.SaudiArabiaOil“Game”QuotaTariffNothingRRRNNN90,80100,6075,50100,6040,8050,100USSaudiArabiaUSvs.SaudiArabiaOil“Game”47SolvingExtensiveFormGamesNashEquilibriumhasthesamemeaninginextensiveformgamesasinnormalformgames.Thereisalsoanothersolutionconceptinextensiveformgames,theSubgamePerfectEquilibrium(SPE)strategywhichhassomeadvantagesoverNashEquilibrium.SolvingExtensiveFormGamesNa48USvs.SaudiArabiaOil“Game”QuotaTariffNothingRRRNNN90,80100,6075,50100,6040,8050,100USSaudiArabiaSubgame=partoflargergamethatcanstandaloneasagameitself.USvs.SaudiArabiaOil“Game”49Sub-GamePerfectEquilibriumAsubgamecanbedefinedforanynodeotherthanaterminal(payoff)node,andincludesallofthesubsequent“branches”ofthetreethatemanatefromthatnode.ForastrategytobeaSubgamePerfectEquilibrium(SPE)strategy,itcanonlycontainactionsthatareoptimalfortheirrespectivesubgames.Sub-GamePerfectEquilibriumA50QuotaTariffNothingRRRNNN90,80100,6075,50100,6040,8050,100USSaudiArabiaXQuotaTariffNothingRRRNNN90,51QuotaTariffNothingRRRNNN90,80100,6075,50100,6040,8050,100USSaudiArabiaTofindalloftheSubgamePerfectEquilibria:Foreachsubgame,determinetheoptimalstrategy.XXXFindtheoptimalstrategyforthe“pruned”tree.QuotaTariffNothingRRRNNN90,52QuotaTariffNothingRRRNNN90,80100,6075,50100,6040,8050,100USSaudiArabiaCompareSubgamePerfectEquilibria(SPE)toNE:NEcanincludeincrediblethreats,alongasunilateralchangesarenotoptimal.Example:Quota;RifQuotaorTariff,NifNothingQuotaTariffNothingRRRNNN90,53AnotherExampleEnterStayOutHighPLowPHighPLowP2,2-1,00,50,0EntrantIncumbentFindoptimalstrategyforeachsubgame(prunethetree).FindEntrant’soptimalaction.XXAnotherExampleEnterStayOutHi54RepeatedGamesInrepeatedgames,strategiesaremuchricher.Inaone-shotPrisoner’sDilemmagame,playerscaneithercooperateordefect.Inarepeatedgame,playerschoosewhethertocooperateordefecteachperiod.Playerscanhavestrategiesthatarecontingentontheotherplayer'sactions.Cooperateiftheotherplayercooperatedlastperiod.Defectiftheotherplayerhaseverdefected.Note:Inrepeatedgames,mustdiscountfuturepayoffs.(1/(1+r))t=t

isthediscountfactorforperiodt.RepeatedGamesInrepeatedgame55SolvingRepeatedGamesIfthegamehasafinitehorizon(thatis,itendsafteraspecifiednumberofrounds),youusebackwardsinduction.StartbyfindingtheoptimalstrategyinthelastperiodMovetothenexttothelastperiod,andfindtheoptimalstrategy,recognizingtheeffectsonthefinalround.Ifthegamehasaninfinitehorizon,youcan'tusebackwardsinductionbecausethereisnolastperiod.Tosolveinfinitehorizongames,youcheckdifferentstrategiestoseeiftheymeettherequirementsofequilibrium.Foreachplayer,changingstrategiesunilaterallywillnotmaketheplayerbetteroff.SolvingRepeatedGamesIftheg56SolvingRepeatedPrisoner’sDilemmaGamesForfinitehorizonrepeatedPD,usebackwardsinduction.Inthelastperiod,alwaysoptimaltodefectIfyouractioninthenext-to-the-lastperioddoesnotaffecttheoptimalstrategyinthelastperiod,youdobetterbydefectinginthenexttothelastperiodAndsoon….ForfinitehorizonrepeatedPD,collusionisneveroptimal.SolvingRepeatedPrisoner’sDi57SolvingRepeatedPrisoner’sDilemmaGamesForinfinitehorizonrepeatedPD,considerdifferentstrategies.“GrimTrigger”strategy:Cooperateaslongasotherplayercooperates,butoncehedefects,defectforever.Hisdefection“triggers”thepunishment.“Grim”becausepunishmentlastsforever.Tocheckifthereisasymmetricequilibriumwithtriggerstrategies:Makesurethatcooperatingisbetterthandefectingifotherplayerhascooperated.Makesurethat“punishment”isacrediblethreat,thatyouwillactuallygothroughwithit.SolvingRepeated