The structure and complexity of Nash equilibria fo

ARTICLEINPRESSTheoreticalComputerScience()–fishroutinggameIDimitrisFotakisa,SpyrosKontogiannisb,c,EliasKoutsoupiasd,MariosMavronicolase,1,PaulSpirakisf,c,∗aDepartmentofInformationandCommunicationSystemsEngineering,UniversityoftheAegean,83200Samos,GreecebDepartmentofComputerScience,UniversityofIoannina,45110Ioannina,GreececResearchAcademicComputerTechnologyInstitute,N.KazantzakiStr.,UniversityCampus,26500Patras,GreecedDepartmentofInformatics,UniversityofAthens,GreeceeDepartmentofComputerScience,UniversityofCyprus,P.O.Box20537,NicosiaCY-1678,CyprusfDepartmentofComputerEngineeringandInformatics,UniversityofPatras,Rion,26500Patras,GreeceAbstractInthiswork,westudythecombinatorialstructureandthecomputationalcomplexityofNashequilibriaforacertaingamethatmodelsselfishroutingoveranetworkconsistingofmparallellinks.Weassumeacollectionofnusers,eachemployingamixedstrategy,whichisaprobabilitydistributionoverlinks,tocontroltheroutingofherowntraffic.InaNashequilibrium,eachuserselfishlyrouteshertrafficonthoselinksthatminimizeherexpectedlatencycost,giventhenetworkcongestioncausedbytheotherusers.ThesocialcostofaNashequilibriumistheexpectation,overallrandomchoicesoftheusers,ofthemaximum,overalllinks,latencythroughalink.WeembarkonasystematicstudyofseveralalgorithmicproblemsrelatedtothecomputationofNashequilibriafortheselfishroutinggameweconsider.Inanutshell,theseproblemsrelatetodecidingtheexistenceofapureNashequilibrium,constructingaNashequilibrium,constructingthepureNashequilibriaofminimumandmaximumsocialcost,andcomputingthesocialcostofagivenmixedNashequilibrium.Ourworkprovidesacomprehensivecollectionofefficientalgorithms,hardnessresults,andstructuralresultsforthesealgorithmicproblems.OurresultsspanandcontrastawiderangeofassumptionsonthesyntaxoftheNashequilibriaandontheparametersofthesystem.c2008ElsevierB.V.Allrightsreserved.Keywords:Algorithmicgametheory;Selfishrouting;NashequilibriumIAnextendedabstractofthisworkappearedintheProceedingsofthe29thInternationalColloquiumonAutomata,LanguagesandProgramming,LectureNotesinComputerScience2380,pp.123–134,2002.ThisworkhasbeenpartiallysupportedbytheISTProgramoftheEuropeanUnionundercontractnumbersIST-1999-14186(ALCOM-FT),IST-2001-33116(FLAGS),andIST-015964(AEOLUS),andbyfundsfromtheJointProgramofScientificandTechnologicalCollaborationbetweenGreeceandCyprus.MostofthisworkwasdonewhileDimitrisFotakisandSpyrosKontogianniswerepostdoctoralfellowsattheMaxPlanckInstitutf¨urInformatik,66123Saarbr¨ucken,Germany.∗Correspondingauthorat:ResearchAcademicComputerTechnologyInstitute,N.KazantzakiStr.,UniversityCampus,26500Patras,Greece.Tel.:[phone];fax:[phone].E-mailaddresses:[e-mail](D.Fotakis),[e-mail](S.Kontogiannis),[e-mail](E.Koutsoupias),[e-mail](M.Mavronicolas),[e-mail](P.Spirakis).1CurrentlyvisitingFacultyofComputerScience,ElectricalEngineeringandMathematics,UniversityofPaderborn,Germany.0304-3975/$-seefrontmatterc2008ElsevierB.V.Allrightsreserved.doi:10.1016/j.tcs.2008.01.004Pleasecitethisarticleinpressas:D.Fotakis,etal.,ThestructureandcomplexityofNashequilibriaforaselfishroutinggame,TheoreticalComputerScience(2008),doi:10.1016/j.tcs.2008.01.004ARTICLEINPRESS2D.Fotakisetal./TheoreticalComputerScience()–1.IntroductionNashequilibrium[35]isarguablythemostimportantsolutionconceptinGameTheory[36].Itmaybeviewedtorepresentasteadystateoftheplayofastrategicgameinwhicheachplayerholdsanaccurateopinionaboutthe(expected)behaviorofotherplayersandactsrationally.Inthiswork,weembarkonasystematicstudyofthecomputationalcomplexityofNashequilibriainthecontextofasimpleselfishroutinggame,originallyintroducedbyKoutsoupiasandPapadimitriou[25].Weassumeacollectionofnusers,eachemployingamixedstrategy,whichisaprobabilitydistributionovermparallellinks,tocontroltheshippingofherowntraffic.Foreachlink,acapacityspecifiestherateatwhichthelinkprocessestraffic.InaNashequilibrium,eachuserselfishlyrouteshertrafficonthoselinksthatminimizeitsexpectedlatencycost,giventhenetworkcongestioncausedbytheotherusers.Auser’ssupportisthesetofthoselinksonwhichitmayshipitstrafficwithnon-zeroprobability.ThesocialcostofaNashequilibriumistheexpectation,overallrandomchoicesoftheusers,ofthemaximum,overalllinks,latencythroughalink.WedistinguishbetweenpureNashequilibria,whereeachuserchoosesexactlyonelink(withprobabilityone),andmixedNashequilibria,wherethechoicesofeachuseraremodeledbyaprobabilitydistributionoverlinks.WeareinterestedinalgorithmicproblemsrelatedtothecomputationofNashequilibriafortheselfishroutinggameweconsider.Morespecifically,weseektodeterminethecomputationalcomplexityofthefollowingalgorithmicproblems,assumingthatalltrafficsandcapacitiesaregiven:•DecidewhetherthereisapureNashequilibrium;ifso,determinethecorrespondingusers’strategies.•Determinetheusers’strategiesinamixedNashequilibrium.•DeterminethebestandtheworstNashequilibriaandtheirsocialcost.•GivenamixedNashequilibrium,computeitssocialcost.Ourstudysometimesdistinguishesbetweenthecase