A polynomial-time Nash equilibrium algorithm for r

APolynomial-timeNashEquilibriumAlgorithmforRepeatedGamesMihaelL.LittmanDept.ofComputerSieneRutgersUniversityPisataway,NJ08854-8019USAPeterStoneDept.ofComputerSienesTheUniversityofTexasatAustinAustin,Texas78712-1188USAAbstratWiththeinreasingrelianeongametheoryasafoundationforautionsandeletroniommere,eÆientalgorithmsforomputingequilibriainmultiplayergeneral-sumgamesareofgreattheoretialandpratialinterest.Theomputa-tionalomplexityofndingaNashequilibriumforaone-shotbimatrixgameisawellknownopenproblem.Thispapertreatsarelatedbutdistintproblem,thatofndingaNashequilibriumforanaverage-payorepeatedbimatrixgame,andpresentsapolynomial-timealgorithm.Ourapproahdrawsonthewellknown\folktheoremfromgametheoryandshowshownite-stateequilibriumstrategiesanbefoundeÆientlyandexpressedsuintly.Keywords:Repeatedgames,omplexityanalysis,Nashequilibrium,omputationalgametheoryPACS:F.2.mEmailaddresses:mlittmans.rutgers.edu(MihaelL.Littman),pstones.utexas.edu(PeterStone).URLs:mlittman/(MihaelL.Littman),(PeterStone).PreprintsubmittedtoElsevierSiene6May20041IntrodutionTheNashequilibriumisoneofthemostimportantoneptsingametheory,formingthebasisofmuhreentworkinmultiagentdeisionmakingandeletronimarketplaes.Assuh,eÆientlyomputingNashequilibriaisoneofthemostimportantproblemsinomputationalgametheory.Theentralresultofthispaperisapolynomial-timealgorithmforomputingaNashequilibriumforrepeated2-player(bimatrix)games,undertheaverage-payoriterion.ThisresultstandsinontrasttotheproblemofomputingaNashequilibriuminaone-shotgame,theomplexityofwhihremainsanimportantandlong-standingopenproblem[12℄.Theideabehindouralgo-rithmehoesthatofthewellknown\folktheorem[11℄,whihshowshowthenotionofthreatsanstabilizeawiderangeofpayoprolesinrepeatedgames.Whilethefolktheoremprovidesaonstrutivemethodforidentify-ingNashequilibriainrepeatedgames,theontributionofthispaperistoshowhowthethreatideaanbeusedtoreateanomputationallyeÆientequilibrium-ndingalgorithm.Whiledrawingheavilyonthefolktheorem,ourresultisnotanimmediateorollary.Infat,whiletherearefolktheoremsforn-playerrepeatedgames,ourpolynomial-timealgorithmisonlyvalidforn=2.Intherestofthepaper,weformallydesribetheproblem(Setion2)andouralgorithmforsolvingit(Setion3),andonludewithasetofillustrativeexamples(Setion4).2ProblemStatementArepeatedbimatrixgameisplayedbytwoplayers,1and2,eahwithasetofationhoiesofsizen1andn2,respetively.Thegameisplayedinrounds,withthetwoplayerssimultaneouslymakingahoieofationateahround.IfPlayer1hoosesation1i1n1andPlayer2hooses1i2n2,theyreeivepayosofP1i1i2andP2i2i1,respetively1.Inarepeatedgame,playersselettheirations,possiblystohastially,viaastrategy|afuntionofthehistoryoftheirinterations.Theobjetiveofeahplayerinarepeatedgameistoadoptastrategythatmaximizesitsexpetedaveragepayo(limitofthemeansriterion).Apairof1Forleanlinessofnotation,wedeviatefromommonpratieandwritematriessothataplayeralwayshoosestherowofitsownpayomatrix,whiletheopponentalwayshoosestheolumn.2strategiesisaNashequilibriumifeahstrategyisoptimizedwithrespettotheother|neitherplayeranimproveitsaveragepayobyhangingstrategiesunilaterally[9℄.Asarunningexampleinthispaper,weusethewellknownIteratedPrisoner’sDilemmatoillustrateandmotivateouralgorithm.Inthisrepeatedbimatrixgame,oneahround,eahplayeraneitherooperate(Ation1)ordefet(Ation2).Thetwoplayersusethesamepayomatrix,P1=P2=2643051375.OnepairofequilibriumstrategiesinthePrisoner’sDilemmaisforbothplayerstodefetineveryround.Theaveragepayointhisaseis1forbothplayers.Thesestrategiesareinequilibriumbeauseaplayerfaingan\alwaysdefetopponentwillreeiveapayoofzeroforeveryroundinwhihitseletstheooperateation;thebestrespondto\alwaysdefetistoalwayshoosedefet.Thispaperonsidersthefollowingomputationalproblem.Givenagamespe-iedbypayomatriesP1andP2,returnapairofstrategiesthatonstitutesaNashequilibriumfortheaverage-payorepeatedbimatrixgame.Therun-ningtimeofthealgorithmshouldbeapolynomialfuntionofthesizeoftheinput.Tofullyspeifytheequilibrium-omputationproblem,wemustbeonreteabouttheinputandoutputrepresentations.Theinputrepresentationisrela-tivelystraightforward.For(p;q)2f(1;2);(2;1)g,thefuntionPpisannpnqmatrix.Toboundthesizeofthenumbersinthesematries,weassumetheyarerationalnumbers,speiedasintegernumeratorandnaturaldenominatorofnomorethankbits.So,therunningtimeofouralgorithmneedstobeapolynomialfuntionofn1,n2,andk.Notethattherepresentationsizeofanintegerisroughlyitslogarithminbasetwoandtherepresentationsizeofarationalnumberisthesumofthesizesofitsnumeratoranddenominator.Apolynomial-sizenumberisonewithrepresentationsizeboundedbyapolynomialfuntionoftheinputsize.Multi-plying,dividing,addingorsubtratingtwopolynomial-sizerationalnumbersproduesapolynomial-sizeresult,asdoessolvingapolynomial-sizesystemoflinearequationsorlinearprogram[14℄.Theoutputofanequilibriumomputationisapairofstrategies.ItiswellknownthateverybimatrixgamehasatleastonepairofstrategiesthatisaNashequilibrium.However,strategiesinrepeatedgamesanbeinnitelylargeobjetsmappingtheinterationh