yale的知識管理講座4

Introductionto

GameTheoryYaleBraunstein

June2003GeneralapproachBriefHistoryofGameTheoryPayoffMatrixTypesofGamesBasicStrategiesEvolutionaryConceptsLimitationsandProblemsBriefHistoryofGameTheory1913-E.Zermeloprovidesthefirsttheoremofgametheory;assertsthatchessisstrictlydetermined1928-JohnvonNeumannprovestheminimaxtheorem1944-JohnvonNeumann&OskarMorgensternwrite"TheoryofGamesandEconomicBehavior〞1950-1953-JohnNashdescribesNashequilibriumRationalityAssumptions:humansarerationalbeingshumansalwaysseekthebestalternativeinasetofpossiblechoicesWhyassumerationality?narrowdowntherangeofpossibilitiespredictabilityUtilityTheoryUtilityTheorybasedon:rationalitymaximizationofutilitymaynotbealinearfunctionofincomeorwealthItisaquantificationofaperson'spreferenceswithrespecttocertainobjects.WhatisGameTheory?GametheoryisastudyofhowtomathematicallydeterminethebeststrategyforgivenconditionsinordertooptimizetheoutcomeGameTheoryFindingacceptable,ifnotoptimal,strategiesinconflictsituations.AbstractionofrealcomplexsituationGametheoryishighlymathematicalGametheoryassumesallhumaninteractionscanbeunderstoodandnavigatedbypresumptions.Whyisgametheoryimportant?Allintelligentbeingsmakedecisionsallthetime.AIneedstoperformthesetasksasaresult.Helpsustoanalyzesituationsmorerationallyandformulateanacceptablealternativewithrespecttocircumstance.Usefulinmodelingstrategicdecision-makingGamesagainstopponentsGamesagainst"nature"TypesofGamesSequentialvs.SimultaneousmovesSinglePlayvs.IteratedZerovs.non-zerosum Perfectvs.ImperfectinformationCooperativevs.conflict Zero-SumGamesThesumofthepayoffsremainsconstantduringthecourseofthegame.TwosidesinconflictBeingwellinformedalwayshelpsaplayerNon-zeroSumGameThesumofpayoffsisnotconstantduringthecourseofgameplay.Playersmayco-operateorcompeteBeingwellinformedmayharmaplayer.GamesofPerfectInformationTheinformationconcerninganopponent’smoveiswellknowninadvance.Allsequentialmovegamesareofthistype.ImperfectInformationPartialornoinformationconcerningtheopponentisgiveninadvancetotheplayer’sdecision.Imperfectinformationmaybediminishedovertimeifthesamegamewiththesameopponentistoberepeated.KeyAreaofInterestchancestrategyNon-zeroSumImperfectInformationMatrixNotationNotes: PlayerI'sstrategyAmaybedifferentfromPlayerII's. P2canbeomittedifzero-sumgamePrisoner’sDilemma&

OtherfamousgamesAsampleofothergames: Marriage Disarmament(mygeneralsare

moreirrationalthanyours)Prisoner’sDilemma10,10BlameDon'tBlameDon't20,00,201,1Prisoner1Prisoner2Notes: Higherpayoffs(longersentences)arebad. Non-cooperativeequilibriumJointmaximumNCEJt.max.GamesofConflictTwosidescompetingagainsteachotherUsuallycausedbycompletelackofinformationabouttheopponentorthegameCharacteristicofzero-sumgamesGamesofCo-operationPlayersmayimprovepayoffthroughcommunicatingformingbindingcoalitions&agreementsdonotapplytozero-sumgamesPrisoner’sDilemmawithCooperationPrisoner’sDilemmawithIterationInfinitenumberofiterationsFearofretaliationFixednumberofiterationDominoeffectBasicStrategies1.Planaheadandlookback2.Useadominatingstrategyifpossible3.Eliminateanydominatedstrategies4.Lookforanyequilibrium5.MixupthestrategiesPlanaheadandlookbackStrategy2Strategy1150100025Strategy1Strategy2-10YouOpponentIfyouhaveadominatingstrategy,

useit Strategy2Strategy1150100025Strategy1Strategy2-10YouOpponentUsestrategy1EliminateanydominatedstrategyStrategy2Strategy1150100025Strategy1Strategy2-10YouOpponentStrategy3-15160Eliminatestrategy2asit’sdominatedbystrategy1LookforanyequilibriumDominatingEquilibriumMinimaxEquilibriumNashEquilibriumMaximin&MinimaxEquilibriumMinimax-tominimizethemaximumloss(defensive)Maximin-tomaximizetheminimumgain(offensive)Minimax=MaximinMaximin&MinimaxEquilibriumStrategiesStrategy2Strategy1150100025Strategy1Strategy2-10YouOpponentStrategy3-15160Min1000150-10-15160MaxDefinition:NashEquilibrium“Ifthereisasetofstrategieswiththepropertythatnoplayercanbenefitbychangingherstrategywhiletheotherplayerskeeptheirstrategiesunchanged,thenthatsetofstrategiesandthecorrespondingpayoffsconstitutetheNashEquilibrium.“Source:/economics/mccain/game/game.htmlIsthisaNashEquilibrium?Strategy2Strategy1150100025Strategy1Strategy2-10YouOpponentStrategy3-15160Min1000150-10-15160MaxCosttopressbutton=2unitsWhenbuttonispressed,foodgiven=10unitsBoxedPigsExample5,1PressWaitPressWait9,-14,40,0LittlePigBigPigDecisions,decisions...Timefor"real-life"decisionmakingHolmes&Moriarityin"TheFinalProblem"Whatwouldyoudo…IfyouwereHolmes?IfyouwereMoriarity?Possiblyinterestingdigressions?WhywasMoriaritysoevil?Whatreallyhappened?Whatdowemeanbyreality?Whatchangedthereality?MixedStrategySafe2Safe1$0$10,000$100,000Safe1Safe2$0MixedStrategySolutionThePayoffMatrix

forHolmes&MoriarityPlayer#1Player#2Strategy#1Strategy#2Strategy#1Strategy#2Payoff(1,1)Payoff(1,2)Payoff(2,1)Payoff(2,2)CanterburyCanterburyDoverDover10050HolmesMoriartyEvolutionaryGameTheoryNaturalselectionreplacesrationalbehaviorSurvivalofthefittestWhyuseevolutiontodetermineastrategy?Hawk/DoveGameEvolutionaryStableStrategyIntroducedbyMaynardSmithandPrice(1973)Strategybecomesstablethroughoutthepopulation