约翰・纳什博士论文.(英文版) Non-cooperative Games

ANNALSOFMATHEMATICSVol.54,No.2,September,1951NON-COOPERATIVEGAMESJOHNNASH(Received·October11,1950)IntroductionVonNeumannandMorgensternhavedevelopedaveryfruitfultheoryoftwo-personzero-sumgamesintheirbookTheoryofGamesandEconomicBe­havior.Thisbookalsocontainsatheoryofn-persongamesofatypewhichwewouldcallcooperative.Thistheoryisbasedonananalysisoftheinterrela­tionships·ofthevariouscoalitionswhichcanbeformedbytheplayersofthegame.Ourtheory,incontradistinction,isbasedontheabsenceofcoalitionsinthatitisassumedthateachparticipantactsindependently,withoutcollaborationorcommunicationwithanyoftheothers.Thenotionofanequilibriumpointisthebasicingredientinourtheory.Thisnotionyieldsageneralizationoftheconceptofthesolutionofatwo-personzero­sumgame.Itturnsoutthatthesetofequilibriumpointsofatwo-personzero­sumgameissimplythesetofallpairsofopposinggoodstrategies.Intheimmediatelyfollowingsectionsweshalldefineequilibriumpointsandprovethatafinitenon-cooperativegamealwayshasatleastoneequilibriumpoint.Weshallalsointroducethenotionsofsolvabilityandstrongsolvabilityofanon-cooperativegameandproveatheoremonthegeometricalstructureofthesetofequilibriumpointsofasolvablegame.Asanexampleoftheapplicationofourtheoryweincludeasolutionofasimplifiedthreepersonpokergame.FormalDefinitionsandTerminologyInthissectionwedefinethebasicconceptsofthispaperandsetupstandardterminologyandnotation.Importantdefinitionswillbeprecededbyasubtitleindicatingtheconceptdefined.Thenon-cooperativeideawillbeimplicit,ratherthanexplicit,belo'v.FiniteGame:Forusann-persongamewillbeasetofnplayers,orpositions,each\vithanassociatedfinitesetofpurestrategies;andcorrespondingtoeachplayer,i,apayofffunction,Pi,,vhichmapsthesetofalln-tuplesofpurestrategiesintotherealnumbers.Whenweusethetermn-tupleweshallalwaysmeanasetofnitems,\vitheachitemassociated,vithadifferentplayer.l\:IixedStrategy,Si:Amixedstrategyofplayeriwillbeacollectionofnon-negativenumbers,vhichhaveunitsumandareinonetoonecorrespondencewithhispurestrategies.WewriteSi=LaCia'TriawithCia~0andLaCia=1torepresentsuchamixedstrategy,wherethe'Tria'Sarethepurestrategiesofplayeri.Weregardthes/saspointsinasimplex\vhoseverticesarethe'Tria'S.Thissimplexmaybere-286NON-COOPERATIVEGAMES287gardedasaconvexsubsetofarealvectorspace,givingusanaturalprocessoflinearcombinationforthemixedstrategies.Weshallusethesuffixesi,j,Ieforplayersanda,(3,I'toindicatevariouspurestrategiesofaplayer.ThesymbolsSi,ti,andri,etc.,villindicatemixedstrate­gies;'Triawillindicatetheithplayer'sathpurestrategy,etc.Payofffunction,Pi:Thepayofffunction,Pi,usedinthedefinitionofafinitegameabove,hasauniqueextensiontothen-tuplesofmixedstrategieswhichislinearinthemixedstrategyofeachplayer[n-linear].Thisextension,veshallalsodenotebyPi,,vritingPieSI,S2,·.·,Sn).Weshallwrite~orttodenoteann-tupleofmixedstrategiesandif~=(SI'S2,..·,Sn)thenPi(~)shallmeanPi(SI,S2,...,Sn).Suchann-tuple,~,,villalsoberegardedasapointinavectorspace,theproductspaceofthevectorspacescontainingthemixedstrategies.Andthesetofallsuchn-tuplesforms,ofcourse,aconvexpolytope,theproductofthesimplicesrepresentingthemixedstrategies.Forconvenienceweintroducethesubstitutionnotation(~;ti)tostandfor(SI,S2,...,Si-l,ti,Si+l,..·,Sn),vhere~=(SI'S2,...,Sn).Theeffectofsuccessivesubstitutions((~;t1:);rj),veindicateby(~;ti;rj),etc.EquilibriumPoint:Ann-tuple~isanequilibriumpointifandonlyifforeveryi(1)Pi(~)=max[Pi(~;ri)]·allri'8Thusanequilibriumpointisann:-tuple~suchthateachplayer'smixedstrategymaximizeshispayoffifthestrategiesoftheothersareheldfixed.Thuseachplayer'sstrategyisoptimalagainstthoseoftheothers.Weshalloccasionallyabbreviateequilibriumpointbyeq.pt.WesaythatamixedstrategySiusesapurestrategy'TriaifSi=L/3Ci{j'Tri{jandCiao.If~=(SI,S·2,..·,Sn)andSiuses'Tria,vealsosaythat~uses'Tria.FromthelinearityofPieSI,...,Sn)inSi,(2)max[Pi(~;ri)]=max[Pi(~;'Tria)].allri'8WedefinePia(~)'=:=Pi(~;'Tria).Then,veobtainthefollo,vingtrivialnecessaryandsufficientconditionfor~tobeanequilibriumpoint:(3)If~(SI,S2,..·,Sn)andSi=LaCia'TriathenPi(~)=LaCiaPia(~),con-sequentlyfor(3)tohold,vemusthaveCia=0wheneverPia(~)max{jP1'{j(~),whichistosaythat~doesnotuse'Triaunlessitisanoptimalpurestrategyforplayeri.So,ve,vrite(4)if'Tr1'aisusedin~thenPia(~)=maxP1'{j(~){jasanothernecessaryandsufficientconditionforanequilibriumpoint.288JOHNNASHSinceacriterion(3)foraneq.pt.canbeexpreEsedbytheequatingofnpairsofcontinuousfunctionsonthespaceofn-tuples~theeq.pts.obviouslyformaclosedsubsetofthisspace.Actually,thissubsetisformedfromanumberofpiecesofalgebraicvarieties,cutoutbyotheralgebraicvarieties.ExistenceofEquilibriumPointsAproofofthisexistencetheorembasedonKakutani'sgeneralizedfixedpointtheoremwaspublishedinProc.Nat.Acad.Sci.U.S.A.,36,pp.48-49.TheproofgivenhereisaconsiderableimprovementoverthatearlierversionandisbaseddirectlyontheBrou\vertheorem.WeproceedbyconstructingacontinuoustransformationTofthespaceofn-tuplessuchthatthefixedpointsofTaretheequilibriumpointsofthegame.THEOREM1.Everyfinitegamehasanequilibriumpoint.PROOF.Let~beann-tupleofmixedstrategies,Pi(~)thecorrespondingpay-o