国外博弈论课件lecture(11).ppt

June18 2003 73 347GameTheory Lecture21 1 DynamicGamesofCompleteInformation DynamicGamesofCompleteandImperfectInformation June18 2003 73 347GameTheory Lecture21 2 Outlineofdynamicgamesofcompleteinformation DynamicgamesofcompleteinformationExtensive formrepresentationDynamicgamesofcompleteandperfectinformationGametreeSubgame perfectNashequilibriumBackwardinductionApplicationsDynamicgamesofcompleteandimperfectinformationMoreapplicationsRepeatedgames June18 2003 73 347GameTheory Lecture21 3 Today sAgenda ReviewofpreviousclassInfinitelyrepeatedgames June18 2003 73 347GameTheory Lecture21 4 Infinitelyrepeatedgame Ainfinitelyrepeatedgameisadynamicgameofcompleteinformationinwhicha simultaneous move gamecalledthestagegameisplayedinfinitely andtheoutcomesofallpreviousplaysareobservedbeforethenextplay Precisely thesimultaneous movegameisplayedatstage1 2 3 t 1 t t 1 Theoutcomesofallprevioust 1stagesareobservedbeforetheplayatthetthstage Eachplayerdiscountsherpayoffbyafactor where0 1 Aplayer spayoffintherepeatedgameisthepresentvalueoftheplayer spayoffsfromthestagegames June18 2003 73 347GameTheory Lecture21 5 Presentvalue June18 2003 73 347GameTheory Lecture21 6 Infinitelyrepeatedgame example Thefollowingsimultaneous movegameisrepeatedinfinitelyTheoutcomesofallpreviousplaysareobservedbeforethenextplaybeginsEachplayer spayofffortheinfinitelyrepeatedgameispresentvalueofthepayoffsreceivedatallstages Question whatisthesubgameperfectNashequilibrium June18 2003 73 347GameTheory Lecture21 7 Everysubgameofaninfinitelyrepeatedgameisidenticaltothegameasawhole 1 L1 R1 2 L2 R2 2 L2 R2 L1 R1 2 L2 R2 2 L2 R2 L1 R1 2 L2 R2 2 L2 R2 L1 R1 2 L2 R2 2 L2 R2 L1 R1 2 L2 R2 2 L2 R2 1 1 1 1 1 1 5 0 0 5 4 4 TOINFINITY June18 2003 73 347GameTheory Lecture21 8 Example strategy Astrategyforaplayerisacompleteplan Itcandependonthehistoryoftheplay Astrategyforplayeri playLiateverystage orateachofherinformationsets Anotherstrategycalledatriggerstrategyforplayeri playRiatstage1 andatthetthstage iftheoutcomeofeachofallt 1previousstagesis R1 R2 thenplayRi otherwise playLi June18 2003 73 347GameTheory Lecture21 9 Example subgameperfectNashequilibrium CheckwhetherthereisasubgameperfectNashequilibriuminwhichplayeriplaysLiateverystage ortheNashequilibriumofthestagegameisplayedateachstage Thiscanbedonebythefollowingtwosteps June18 2003 73 347GameTheory Lecture21 10 Example subgameperfectNashequilibrium Step1 checkwhetherthecombinationofstrategiesisaNashequilibriumoftheinfinitelyrepeatedgame Ifplayer1playsL1ateverystage thebestresponseforplayer2istoplayL2ateverystage Ifplayer2playsL2ateverystage thebestresponseforplayer1istoplayL1ateverystage Hence itisaNashequilibriumoftheinfinitelyrepeatedgame June18 2003 73 347GameTheory Lecture21 11 Example subgameperfectNashequilibriumcont d Step2 checkwhethertheNashequilibriumoftheinfinitelyrepeatedgameinducesaNashequilibriumineverysubgameoftheinfinitelyrepeatedgame RecallthateverysubgameoftheinfinitelyrepeatedgameisidenticaltotheinfinitelyrepeatedgameasawholeObviously itinducesaNashequilibriumineverysubgameHence itisasubgameperfectNashequilibrium June18 2003 73 347GameTheory Lecture21 12 Triggerstrategy triggerstrategyforplayeri playRiatstage1 andatthetthstage iftheoutcomesofallt 1previousstagesare R1 R2 thenplayRi otherwise playLi CheckwhetherthereisasubgameperfectNashequilibriuminwhicheachplayerplaysthetriggerstrategy Thiscanbedonebythefollowingtwosteps Step1 checkwhetherthecombinationofthetriggerstrategiesisaNashequilibriumoftheinfinitelyrepeatedgameStep2 ifyes checkwhetherthisNashequilibriuminducesaNashequilibriumineverysubgame June18 2003 73 347GameTheory Lecture21 13 Triggerstrategy step1 June18 2003 73 347GameTheory Lecture21 14 Triggerstrategy step1cont d 1 2 t 1 t t 1 t 2 Stage P2 Trigger P2 deviatetriggeratt June18 2003 73 347GameTheory Lecture21 15 Triggerstrategy step1cont d June18 2003 73 347GameTheory Lecture21 16 Triggerstrategy step2 Step2 checkwhethertheNashequilibriuminducesaNashequilibriumineverysubgameoftheinfinitelyrepeatedgame Recallthateverysubgameoftheinfinitelyrepeatedgameisidenticaltotheinfinitelyrepeatedgameasawhole June18 2003 73 347GameTheory Lecture21 17 Step2cont d subgame 1 L1 R1 2 L2 R2 2 L2 R2 L1 R1 2 L2 R2 2 L2 R2 L1 R1 2 L2 R2 2 L2 R2 L1 R1 2 L2 R2 2 L2 R2 L1 R1 2 L2 R2 2 L2 R2 1 1 1 1 1 1 5 0 0 5 4 4 TOINFINITY June18 2003 73 347GameTheory Lecture21 18 Triggerstrategy step2cont d Wehavetwoclassesofsubgames subgamefollowingahistory fromstage1 inwhichthestageoutcomesareall R1 R2 subgamefollowingahistory fromstage1 inwhichatleastonestageoutcomeisnot R1 R2 TheNashequilibriumoftheinfinitelyrepeatedgameinducesaNashequilibriuminwhicheachplayerstillplaystriggerstrategyforthefirstclassofsubgamesTheNashequilibriumoftheinfinitelyrepeatedgameinducesaNashequilibriuminwhich L1