[数学]博弈论 Game Theory

IE675GameTheoryLectureNoteSet1WayneF.Bialas1Friday,March30,20011INTRODUCTION1.1Whatisgametheory?Gametheoryisthestudyofproblemsofconflictandcooperationamongindependentdecision­makers.Gametheorydealswithgamesofstrategyratherthangamesofchance.Theingredientsofagametheoryproblemincludeplayers(decision­makers)choices(feasibleactions)payoffs(benefits,prizes,orawards)preferencestopayoffs(objectives)Weneedtoknowwhenonechoiceisbetterthananotherforaparticularplayer.1.2ClassificationofgametheoryproblemsProblemsingametheorycanbeclassifiedinanumberofways.1.2.1Staticvs.dynamicgamesIndynamicgames,theorderofdecisionsareimportant.Question1.1.Isiteverreallypossibletoimplementstaticdecision­makinginprac­tice?1DepartmentofIndustrialEngineering,UniversityatBuffalo,342BellHall,Box602050,Buffalo,NY14260­2050USA;E­mail:[e-mail];Web:˜bialas.CopyrightcMMIWayneF.Bialas.AllRightsReserved.Duplicationofthisworkisprohibitedwithoutwrittenpermission.ThisdocumentproducedMarch30,2001at2:31pm.1­11.2.2Cooperativevs.non­cooperativeInanon­cooperativegame,eachplayerpursueshis/herowninterests.Inacooperativegames,playersareallowedtoformcoalitionsandcombinetheirdecision­makingproblems.Non­cooperativeCooperativeMathprogrammingCooperativeStaticNon­cooperativeGameGameTheoryTheoryCooperativeDynamicControlTheoryDynamicGamesNote1.1.Thisareaofstudyisdistinctfrommulti­criteriadecisionmaking.Flowofinformationisanimportantelementingametheoryproblems,butitissometimesexplicitlymissing.noisyinformationdeception1.2.3Relatedareasdifferentialgamesoptimalcontroltheorymathematicaleconomics1.2.4Applicationareascorporatedecisionmakingdefensestrategymarketmodellingpublicpolicyanalysisenvironmentalsystemsdistributedcomputingtelecommunicationsnetworks1­21.2.5Theoryvs.simulationThemathematicaltheoryofgamesprovidesthefundamentallawsandproblemstructure.Gamescanalsobesimulatedtoassesscomplexeconomicsystems.1.3SolutionconceptsThenotionofa“solution”ismoretenuousingametheorythaninotherfields.Definition1.1.Asolutionisasystematicdescriptionoftheoutcomesthatmayemergefromthedecisionproblem.optimality(forwhom??)feasibilityequilibria1.4Gamesinextensiveform1.4.1Example:MatchingPenniesPlayer1:ChooseHorTPlayer2:ChooseHorT(notknowingPlayer1’schoice)Ifthecoinsarealike,Player2wins1centfromPlayer1Ifthecoinsaredifferent,Player1wins1centfromPlayer2Writteninextensiveform,thegameappearsasfollows1­3Player1Player2InformationSet(-1,1)(1,-1)(1,-1)(-1,1)21SInordertodealwiththeissueofPlayer2’sknowledgeaboutthegame,weintroducetheconceptofaninformationset.Whenthegame’sprogressreachesPlayer2’stimetomove,Player2issupposedtoknowPlayer1’schoice.Thesetofnodes,S21,isaninformationsetforPlayer2.Aplayeronlyknowsthepossibleoptionsemanatingfromaninformation.Aplayerdoesnotknowwhichnodewithintheinformationsetistheactualnodeatwhichtheprogressofplayresides.Therearesomeobviousrulesaboutinformationsetsthatwewillformallydescribelater.1­4Forexample,thefollowingcannotoccur...Player1Player221S7KLFDQQRKDSSHQDefinition1.2.Aplayerissaidtohaveperfectinformationifallofhis/herinformationsetsaresingletons.Player1Player2JDPZLWSHUIHFLQIRUPDWLRQ1­5Definition1.3.AstrategyforPlayeriisafunctionwhichassignstoeachofPlayeri’sinformationsets,oneofthebrancheswhichfollowsarepresentativenodefromthatset.Example1.1.AstrategyΨwhichhasΨ(S21)=HwouldtellPlayer2toselectHeadswhenhe/sheisininformationsetS21.1.5Gamesinstrategicform1.5.1Example:MatchingPenniesConsiderthesamegameasaboveandthefollowingmatrixofpayoffs:Player2HTPlayer1H(­1,1)(1,­1)T(1,­1)(­1,1)TherowsrepresentthestrategiesofPlayer1.ThecolumnsrepresentthestrategiesofPlayer2.Distinguishactionsfromstrategies.Thematchingpenniesgameisanexampleofanon­cooperativegame.1.6CooperativegamesCooperativegamesallowplayerstoformcoalitionstosharedecisions,informationandpayoffs.Forexample,ifwehaveplayersetN=f1;2;3;4;5;6gApossiblecoalitionstructurewouldbeff1;2;3g;f4;6g;f5ggOftenthesegamesaredescribedincharacteristicfunctionform.Acharacteristicfunctionisamappingv:2N!Randv(S)(whereS’N)isthe“worth”ofthecoalitionS.1­61.7DynamicgamesDynamicgamescanbecooperativeornon­cooperativeinform.Oneclassofcooperativedynamicgamesarehierarchical(organizational)games.Considerahierarchyofplayers,forexample,PresidentVice­President...WorkersEachlevelhascontroloverasubsetofalldecisionvariables.Eachmayhaveanobjectivefunctionthatdependsonthedecisionvariablesofotherlevels.Supposethatthetoplevelmakeshis/herdecisionfirst,andthenpassesthatinformationtothenextlevel.Thenextlevelthenmakeshis/herdecision,andtheplayprogressesdownthroughthehierarchy.Thekeyingredientintheseproblemsispreemption,i.e.,the“frictionofspaceandtime.”Evenwheneverythingislinear,suchsystemscanproducestable,inadmissiblesolutions(Chew).stable:Noonewantstounilaterallymoveawayfromthegivensolutionpoint.inadmissible:Therearefeasiblesolutionpointsthatproducebetterpayoffsforallplayersthanthegivensolutionpoint.1­7IE675GameTheoryLectureNoteSet2WayneF.Bialas1Friday,March30,20012TWO­PERSONGAMES2.1Two­PersonZero­SumGames2.