版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
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
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 动物屠宰与肉类加工新技术研究考核试卷
- 文具企业市场营销与品牌建设策略实施考核试卷
- 船舶非金属材料的焊接工艺考核试卷
- 石棉制品在通讯设备的防护应用考核试卷
- 区块链保险科技行业市场突围建议及需求分析报告
- 个性化产品定制化行业的消费市场分析
- 食品配送行业发展方向及匹配能力建设研究报告
- 核心素养视域下高中英语生本课堂教学模式研究
- 基于校本教研助力教师发展的研究
- 专业书籍出版行业市场发展趋势及投资咨询报告
- 中学生讲安全演讲课件
- 封面设计课件
- 美世国际职位评估体系IPE3.0使用手册
- 2023义务教育英语课程标准
- 消防设备故障应急预案流程
- 建筑工程EPC分包合同协议书 标准版
- 1.3.2大气受热过程课件【知识精讲精研】高一地理湘教版(2019)必修第一册+
- 中医内科学-肺胀
- 法院一审公开开庭申请书
- 《气象学家竺可桢》课件
- 贫困生补助认定申请表
评论
0/150
提交评论