yale的知识管理讲座45页.PPT

IntroductiontoGameTheory,YaleBraunsteinJune2003,Generalapproach,BriefHistoryofGameTheoryPayoffMatrixTypesofGamesBasicStrategiesEvolutionaryConceptsLimitationsandProblems,BriefHistoryofGameTheory,1913-E.Zermeloprovidesthefirsttheoremofgametheory;assertsthatchessisstrictlydetermined1928-JohnvonNeumannprovestheminimaxtheorem1944-JohnvonNeumann&OskarMorgensternwriteTheoryofGamesandEconomicBehavior”1950-1953-JohnNashdescribesNashequilibrium,Rationality,Assumptions:humansarerationalbeingshumansalwaysseekthebestalternativeinasetofpossiblechoicesWhyassumerationality?narrowdowntherangeofpossibilitiespredictability,UtilityTheory,UtilityTheorybasedon:rationalitymaximizationofutilitymaynotbealinearfunctionofincomeorwealthItisaquantificationofapersonspreferenceswithrespecttocertainobjects.,WhatisGameTheory?,Gametheoryisastudyofhowtomathematicallydeterminethebeststrategyforgivenconditionsinordertooptimizetheoutcome,GameTheory,Findingacceptable,ifnotoptimal,strategiesinconflictsituations.AbstractionofrealcomplexsituationGametheoryishighlymathematicalGametheoryassumesallhumaninteractionscanbeunderstoodandnavigatedbypresumptions.,Whyisgametheoryimportant?,Allintelligentbeingsmakedecisionsallthetime.AIneedstoperformthesetasksasaresult.Helpsustoanalyzesituationsmorerationallyandformulateanacceptablealternativewithrespecttocircumstance.Usefulinmodelingstrategicdecision-makingGamesagainstopponentsGamesagainstnature,TypesofGames,Sequentialvs.SimultaneousmovesSinglePlayvs.IteratedZerovs.non-zerosumPerfectvs.ImperfectinformationCooperativevs.conflict,Zero-SumGames,Thesumofthepayoffsremainsconstantduringthecourseofthegame.TwosidesinconflictBeingwellinformedalwayshelpsaplayer,Non-zeroSumGame,Thesumofpayoffsisnotconstantduringthecourseofgameplay.Playersmayco-operateorcompeteBeingwellinformedmayharmaplayer.,GamesofPerfectInformation,Theinformationconcerninganopponentsmoveiswellknowninadvance.Allsequentialmovegamesareofthistype.,ImperfectInformation,Partialornoinformationconcerningtheopponentisgiveninadvancetotheplayersdecision.Imperfectinformationmaybediminishedovertimeifthesamegamewiththesameopponentistoberepeated.,KeyAreaofInterest,chancestrategy,Non-zeroSum,ImperfectInformation,MatrixNotation,Notes:PlayerIsstrategyAmaybedifferentfromPlayerIIs.P2canbeomittedifzero-sumgame,PrisonersDilemma&Otherfamousgames,Asampleofothergames:MarriageDisarmament(mygeneralsaremoreirrationalthanyours),PrisonersDilemma,10,10,Blame,Dont,Blame,Dont,20,0,0,20,1,1,Prisoner1,Prisoner2,Notes:Higherpayoffs(longersentences)arebad.Non-cooperativeequilibriumJointmaximum,NCE,Jt.max.,GamesofConflict,TwosidescompetingagainsteachotherUsuallycausedbycompletelackofinformationabouttheopponentorthegameCharacteristicofzero-sumgames,GamesofCo-operation,Playersmayimprovepayoffthroughcommunicatingformingbindingcoalitions&agreementsdonotapplytozero-sumgamesPrisonersDilemmawithCooperation,PrisonersDilemmawithIteration,InfinitenumberofiterationsFearofretaliationFixednumberofiterationDominoeffect,BasicStrategies,1.Planaheadandlookback2.Useadominatingstrategyifpossible3.Eliminateanydominatedstrategies4.Lookforanyequilibrium5.Mixupthestrategies,Planaheadandlookback,Strategy2,Strategy1,150,1000,25,Strategy1,Strategy2,-10,You,Opponent,Ifyouhaveadominatingstrategy,useit,Strategy2,Strategy1,150,1000,25,Strategy1,Strategy2,-10,You,Opponent,Eliminateanydominatedstrategy,Strategy2,Strategy1,150,1000,25,Strategy1,Strategy2,-10,You,Opponent,Strategy3,-15,160,Lookforanyequilibrium,DominatingEquilibriumMinimaxEquilibriumNashEquilibrium,Maximin&MinimaxEquilibrium,Minimax-tominimizethemaximumloss(defensive)Maximin-tomaximizetheminimumgain(offensive)Minimax=Maximin,Maximin&MinimaxEquilibriumStrategies,Strategy2,Strategy1,150,1000,25,Strategy1,Strategy2,-10,You,Opponent,Strategy3,-15,160,Min,1000,150,-10,-15,160,Max,Definition:NashEquilibrium,“Ifthereisasetofstrategieswiththepropertythatnoplayercanbenefitbychangingherstrategywhiletheotherplayerskeeptheirstrategiesunchanged,thenthatsetofstrategiesandthecorrespondingpayoffsconstitutetheNashEquilibrium.“Source:/economics/mccain/game/game.html,IsthisaNashEquilibrium?,Strategy2,Strategy1,150,1000,25,Strategy1,Strategy2,-10,You,Opponent,Strategy3,-15,160,Min,1000,150,-10,-15,160,Max,Costtopressbutton=2units,Whenbuttonispressed,foodgiven=10units,BoxedPigsExample,5,1,Press,Wait,Press,Wait,9,-1,4,4,0,0,LittlePig,BigPig,Decisions,decisions.,Timeforreal-lifedecisionmaking,Holmes&MoriarityinTheFinalProblemWhatwouldyoudoIfyouwereHolmes?IfyouwereMoriarity?Possiblyinterestingdigressions?WhywasMoriaritysoevil?Whatreallyhappened?Whatdowemeanbyreality?Whatchangedthereality?,MixedStrategy,Safe2,Safe1,$0,$10,000,$100,000,Safe1,Safe2,$0,MixedStrategySolution,ThePayoffMatrixforHolmes&Moriarity,EvolutionaryGameTheory,NaturalselectionreplacesrationalbehaviorSurvivalofthefittestWhyuseevolutiontodetermineastrategy?,Hawk/DoveGame,EvolutionaryStableStrategy,IntroducedbyMaynardSmithandPrice(1973)StrategybecomesstablethroughoutthepopulationMutationsbecomingineffective,Hawk,Dove,Hawk,Dove,Hawk,Dove,Hawk,Dove,Whereisgametheorycurrentlyused?,EcologyNetworksEconomics,Limitations&Problems,AssumesplayersalwaysmaximizetheiroutcomesSomeoutcomesaredifficulttoprovideautilityforNotallofthepayoffscanbequantifiedNotapplicabletoal