The Complexity of Games on Highly Regular Graphs (

TheComplexityofGamesonHighlyRegularGraphs(ExtendedAbstract)ConstantinosDaskalakis¤ChristosH.PapadimitriouyJuly7,2005AbstractWepresentalgorithmsandcomplexityresultsfortheproblemoffindingequilibria(mixedNashequilibria,pureNashequilibriaandcorrelatedequilibria)ingameswithextremelysuccinctdescriptionthataredefinedonhighlyregulargraphssuchasthed-dimensionalgrid;wearguethatsuchgamesareofinterestinthemodellingoflargesystemsofinteractingagents.WeshowthatmixedNashequilibriacanbefoundintimeexponentialinthesuccinctrepresentationbyquantifierelimination,whilecorrelatedequilibriacanbefoundinpolynomialtimebytakingadvantageofthegame’ssymmetries.Finally,thecomplexityofdeterminingwhethersuchagameonthed-dimensionalgridhasapureNashequilibriumdependsondandthedichotomyisremarkablysharp:itissolvableinpolynomialtime(infactNL-complete)whend=1,butitisNEXP-completeford¸2.¤UCBerkeley,ComputerScienceDivision,SodaHall,Berkeley,CA94720.Email:[e-mail]lethefirstauthorwasaseniorundergraduatestudentattheNationalTechnicalUniversityofAthens.yUCBerkeley,ComputerScienceDivision,SodaHall,Berkeley,CA94720.SupportedbyanNSFITRgrantandaMicrosoftResearchgrant.Email:[e-mail].1IntroductionInrecentyearstherehasbeensomeconvergenceofideasandresearchgoalsbetweengametheoryandtheoreticalcomputerscience,asbothfieldshavetriedtograpplewiththerealitiesoftheInternet,alargesystemconnectingoptimizingagents.AnimportantopenproblemidentifiedinthisareaisthatofcomputingamixedNashequilibrium;thecomplexityofeventhe2-playercaseis,astonishingly,open(see,e.g.,[9,15]).SinceamixedNashequilibriumisalwaysguaranteedtoexist,ordinarycompletenesstechniquesdonotcomeintoplay.Theproblemdoesfallintotherealmof“exponentialexistenceproofs”[11],albeitofakindsufficientlyspecializedthat,heretoo,nocompletenessresultsseemtobeforthcoming.Ontheotherhand,progresstowardsalgorithmshasbeenveryslow(see,e.g.,[10,7]).Wemustmentionherethatthisfocusoncomplexityissuesisnotunderstoodandwelcomebyallontheotherside.Someeconomistsaremystifiedbytheobsessionofourfieldwiththecomplexityofaproblem(Nashequilibrium)thatarisesinacontext(rationalbehaviorofagents)thatisnotcomputationalatall.Webelievethatcomplexityissuesareofcentralimportanceingametheory,andnotjusttheresultofprofessionalbiasbyafewcomputerscientists.Thereasonissimple:Equilibriaingamesareimportantconceptsofrationalbehaviorandsocialstability,reassuringexistencetheoremsthatenhancetheexplanatorypowerofgametheoryandjustifyitsapplicability.Anintractabilityproofwouldrendertheseexistencetheoremslargelymoot,andwouldcastseriousdoubtonthemodellingpowerofgames.Howcanonehavefaithinamodelpredictingthatagroupofagentswillsolveanintractableproblem?InthewordsofKamalJain:“IfyourPCcannotfindit,thenneithercanthemarket.”However,sinceourambitionistomodelbygamestheInternetandtheelectronicmarket,wemustextendourcomplexityinvestigationswellbeyond2-persongames.Thisishappening:[2,4,5,12,10]investigatethecomplexityofmulti-playergamesofdifferentkinds.Butthereisanimmediatedifficulty:Sinceagamewithnplayersandsstrategieseachneedsnsnnumberstobespecified(seeSection2forgame-theoreticdefinitions)theinputneededtodefinesuchagameisexponentiallylong.Thispresentswithtwoissues:First,ahostoftrickyproblemsbecomeeasyjustbecausetheinputissolarge.Moreimportantly,exponentialinputmakesamockeryofclaimsofrelevance:Noimportantproblemcanneedanastronomicallylargeinputtobespecified(andweareinterestedinlargen,andofcourses¸2).Hence,allworkinthisareahasfocusedoncertainnaturalclassesofsuccinctlyrepresentablegames.OneimportantclassofsuccinctgamesisthatofthegraphicalgamesproposedandstudiedbyMichaelKearnsetal.[4,5].Inagraphicalgame,wearegivenagraphwiththeplayersasnodes.Itispostulatedthatanagent’sutilitydependsonthestrategychosenbytheplayerandbytheplayer’sneighborsinthegraph.Thus,suchgamesplayedongraphsofboundeddegreecanberepresentedbypolynomiallymany(innands)numbers.Graphicalgamesarequiteplausibleandattractiveasmodelsoftheinteractionofagentsacrossalargenetworkormarket.Therehasbeenahostofpositivecomplexityresultsforthiskindofgames.Ithasbeenshown,forexample,thatcorrelatedequilibria(asophisticatedequilibriumconceptdefinedinSection2)canbecomputedinpolynomialtimeforgraphicalgamesthataretrees[4],laterextendedtoallgraphicalgames[10].Butifwearetostudytrulylargesystemsofthousandsormillionsofinteractingagents,itisunrealistictoassumethatweknowthearbitrarilycomplexdetailsoftheunderlyinginteractiongraphandofthebehaviorofeverysingleplayer—thesizeofsuchdescriptionwouldbeforbiddinganyway.Onepossibility,exploredbrilliantlyintheworkofRoughgardenandTardos[14],istoassumeacontinuumofbehaviorallyidenticalplayers.Inthepresentpaperweexploreanalternativemodeloflargepopulationsofusers,withintherealmofgraphicalgames.Imaginethattheinteractiongraphisperhapsthen£ngrid,andthatallplayersarelocallyidentical(ourresultsapplytomanyhighlyregulartopologiesofgraphsandthecaseofseveralplayerclasses).Therepresentationofsuchagamewouldthenbeextremelysuccinct:Justthegameplayedateachlocus,andn,thesizeofthegrid.Suchgames,called