yale的知识管理讲座4(1)

IntroductiontoGameTheoryYaleBraunsteinJune2003GeneralapproachBriefHistoryofGameTheoryPayoffMatrixTypesofGamesBasicStrategiesEvolutionaryConceptsLimitationsandProblemsBriefHistoryofGameTheory1913-E.Zermeloprovidesthefirsttheoremofgametheory;assertsthatchessisstrictlydetermined1928-JohnvonNeumannprovestheminimaxtheorem1944-JohnvonNeumann&OskarMorgensternwriteTheoryofGamesandEconomicBehavior”1950-1953-JohnNashdescribesNashequilibriumRationalityAssumptions:humansarerationalbeingshumansalwaysseekthebestalternativeinasetofpossiblechoicesWhyassumerationality?narrowdowntherangeofpossibilitiespredictabilityUtilityTheoryUtilityTheorybasedon:rationalitymaximizationofutilitymaynotbealinearfunctionofincomeorwealthItisaquantificationofaperson'spreferenceswithrespecttocertainobjects.WhatisGameTheory?GametheoryisastudyofhowtomathematicallydeterminethebeststrategyforgivenconditionsinordertooptimizetheoutcomeGameTheoryFindingacceptable,ifnotoptimal,strategiesinconflictsituations.AbstractionofrealcomplexsituationGametheoryishighlymathematicalGametheoryassumesallhumaninteractionscanbeunderstoodandnavigatedbypresumptions.Whyisgametheoryimportant?Allintelligentbeingsmakedecisionsallthetime.AIneedstoperformthesetasksasaresult.Helpsustoanalyzesituationsmorerationallyandformulateanacceptablealternativewithrespecttocircumstance.Usefulinmodelingstrategicdecision-makingGamesagainstopponentsGamesagainstnatureTypesofGamesSequentialvs.SimultaneousmovesSinglePlayvs.IteratedZerovs.non-zerosumPerfectvs.ImperfectinformationCooperativevs.conflictZero-SumGamesThesumofthepayoffsremainsconstantduringthecourseofthegame.TwosidesinconflictBeingwellinformedalwayshelpsaplayerNon-zeroSumGameThesumofpayoffsisnotconstantduringthecourseofgameplay.Playersmayco-operateorcompeteBeingwellinformedmayharmaplayer.GamesofPerfectInformationTheinformationconcerninganopponent’smoveiswellknowninadvance.Allsequentialmovegamesareofthistype.ImperfectInformationPartialornoinformationconcerningtheopponentisgiveninadvancetotheplayer’sdecision.Imperfectinformationmaybediminishedovertimeifthesamegamewiththesameopponentistoberepeated.KeyAreaofInterestchancestrategyMatrixNotation(Column)PlayerIIStrategyAStrategyB(Row)PlayerIStrategyA(P1,P2)(P1,P2)StrategyB(P1,P2)(P1,P2)Notes:PlayerI'sstrategyAmaybedifferentfromPlayerII's.P2canbeomittedifzero-sumgamePrisoner’sDilemma&OtherfamousgamesAsampleofothergames:MarriageDisarmament(mygeneralsaremoreirrationalthanyours)Prisoner’sDilemmaNotes:Higherpayoffs(longersentences)arebad.Non-cooperativeequilibriumJointmaximumNCEJt.max.GamesofConflictTwosidescompetingagainsteachotherUsuallycausedbycompletelackofinformationabouttheopponentorthegameCharacteristicofzero-sumgamesGamesofCo-operationPlayersmayimprovepayoffthroughcommunicatingformingbindingcoalitions&agreementsdonotapplytozero-sumgamesPrisoner’sDilemmawithCooperationPrisoner’sDilemmawithIterationInfinitenumberofiterationsFearofretaliationFixednumberofiterationDominoeffectBasicStrategies1.Planaheadandlookback2.Useadominatingstrategyifpossible3.Eliminateanydominatedstrategies4.Lookforanyequilibrium5.MixupthestrategiesPlanaheadandlookbackIfyouhaveadominatingstrategy,useitUsestrategy1EliminateanydominatedstrategyEliminatestrategy2asit’sdominatedbystrategy1LookforanyequilibriumDominatingEquilibriumMinimaxEquilibriumNashEquilibriumMaximin&MinimaxEquilibriumMinimax-tominimizethemaximumloss(defensive)Maximin-tomaximizetheminimumgain(offensive)Minimax=MaximinMaximin&MinimaxEquilibriumStrategiesDefinition:NashEquilibrium“Ifthereisasetofstrategieswiththepropertythatnoplayercanbenefitbychangingherstrategywhiletheotherplayerskeeptheirstrategiesunchanged,thenthatsetofstrategiesandthecorrespondingpayoffsconstitutetheNashEquilibrium.“Source:,foodgiven=10unitsBoxedPigsExampleDecisions,decisions...Timeforreal-lifedecisionmakingHolmes&MoriarityinTheFinalProblemWhatwouldyoudo…IfyouwereHolmes?IfyouwereMoriarity?Possiblyinterestingdigressions?WhywasMoriaritysoevil?Whatreallyhappened?–Whatdowemeanbyreality?–Whatchangedthereality?MixedStrategyMixedStrategySolutionValueinSafeProbabilityofbeingGuardedExpectedLossSafe110,000$1/119,091$Safe2100,000$10/119,091$Both110,000$ThePayoffMatrixforHolmes&MoriarityPlayer#1Player#2Strategy#1Strategy#2Strategy#1Strategy#2Payoff(1,1)Payoff(1,2)Payoff(2,1)Payoff(2,2)Whereisgametheorycurrentlyused?–Ecology–Networks–EconomicsLimitations&ProblemsAssumesplayersalwaysmaximizetheiroutcomesSomeoutcomesaredifficulttoprovideautilityforNotallofthepayoffscanbequantifiedNotapplicabletoallproblemsSummaryWhatisgametheory?Abstractionmodelingmulti-personinteractionsHowisgametheoryapplied?Payoffmatrixcontainseachperson’sutilitiesforvariousstrategiesWhousesgametheory?Economists,Ecologists,Networkpeople,...HowisthisrelatedtoAI?Providesamethodtosimulateathinkingagent