P1:SBT FM-main CUNY1061-Nisan 0521872820 August3,2007 12:6 AlgorithmicGameTheory Over the last few years, there has been explosive growth in the research done at the in- terfaceofcomputerscience,gametheory,andeconomictheory,largelymotivatedbythe emergenceoftheInternet.AlgorithmicGameTheorydevelopsthecentralideasandresults ofthisnewandexcitingarea. More than 40 of the top researchers in this field have written chapters whose topics rangefromthefoundationstothestateoftheart.Thisbookcontainsanextensivetreatment ofalgorithmsforequilibriaingamesandmarkets,computationalauctionsandmechanism design,andthe“priceofanarchy,”aswellasapplicationsinnetworks,peer-to-peersystems, security,informationmarkets,andmore. This book will be of interest to students, researchers, and practitioners in theoretical computerscience,economics,networking,artificialintelligence,operationsresearch,and discretemathematics. NoamNisanisaProfessorintheDepartmentofComputerScienceatTheHebrewUniver- sityofJerusalem.HisotherbooksincludeCommunicationComplexity. Tim Roughgarden is an Assistant Professor in the Department of Computer Science at StanfordUniversity.HisotherbooksincludeSelfishRoutingandthePriceofAnarchy. E´va Tardos is a Professor in the Department of Computer Science at Cornell University. HerotherbooksincludeAlgorithmDesign. Vijay V. Vazirani is a Professor in the College of Computing at the Georgia Institute of Technology.HisotherbooksincludeApproximationAlgorithms. i P1:SBT FM-main CUNY1061-Nisan 0521872820 August3,2007 12:6 ii P1:SBT FM-main CUNY1061-Nisan 0521872820 August3,2007 12:6 Algorithmic Game Theory Editedby Noam Nisan HebrewUniversityofJerusalem Tim Roughgarden StanfordUniversity ´ Eva Tardos CornellUniversity Vijay V. Vazirani GeorgiaInstituteofTechnology iii P1:SBT FM-main CUNY1061-Nisan 0521872820 August3,2007 12:6 cambridgeuniversitypress Cambridge,NewYork,Melbourne,Madrid,CapeTown,Singapore,Sa˜oPaulo,Delhi CambridgeUniversityPress 32AvenueoftheAmericas,NewYork,NY10013-2473,USA www.cambridge.org Informationonthistitle:www.cambridge.org/9780521872829 (cid:1)C NoamNisan,TimRoughgarden,E´vaTardos,VijayV.Vazirani2007 Thispublicationisincopyright.Subjecttostatutoryexception andtotheprovisionsofrelevantcollectivelicensingagreements, noreproductionofanypartmaytakeplacewithout thewrittenpermissionofCambridgeUniversityPress. Firstpublished2007 PrintedintheUnitedStatesofAmerica AcatalogrecordforthisbookisavailablefromtheBritishLibrary. LibraryofCongressCataloginginPublicationData Algorithmicgametheory/editedbyNoamNisan...[etal.];foreword byChristosPapadimitriou. p. cm. Includesindex. ISBN-13:978-0-521-87282-9(hardback) ISBN-10:0-521-87282-0(hardback) 1.Gametheory. 2.Algorithms. I.Nisan,Noam. II.Title. QA269.A43 2007 519.3–dc22 2007014231 ISBN 978-0-521-87282-9hardback CambridgeUniversityPresshasnoresponsibilityfor thepersistenceoraccuracyofURLSforexternalor third-partyInternetWebsitesreferredtointhispublication anddoesnotguaranteethatanycontentonsuch Websitesis,orwillremain,accurateorappropriate. i P1:SBT FM-main CUNY1061-Nisan 0521872820 August3,2007 12:6 Contents Foreword pagexiii Preface xvii Contributors xix I ComputinginGames 1 BasicSolutionConceptsandComputationalIssues 3 E´vaTardosandVijayV.Vazirani 1.1 Games,OldandNew 3 1.2 Games,Strategies,Costs,andPayoffs 9 1.3 BasicSolutionConcepts 10 1.4 FindingEquilibriaandLearninginGames 16 1.5 RefinementofNash:GameswithTurnsandSubgamePerfectEquilibrium 18 1.6 NashEquilibriumwithoutFullInformation:BayesianGames 20 1.7 CooperativeGames 20 1.8 MarketsandTheirAlgorithmicIssues 22 Acknowledgments 26 Bibliography 26 Exercises 26 2 TheComplexityofFindingNashEquilibria 29 ChristosH.Papadimitriou 2.1 Introduction 29 2.2 IstheNashEquilibriumProblemNP-Complete? 31 2.3 TheLemke–HowsonAlgorithm 33 2.4 TheClassPPAD 36 2.5 SuccinctRepresentationsofGames 39 2.6 TheReduction 41 2.7 CorrelatedEquilibria 45 2.8 ConcludingRemarks 49 Acknowledgment 50 Bibliography 50 v P1:SBT FM-main CUNY1061-Nisan 0521872820 August3,2007 12:6 vi contents 3 EquilibriumComputationforTwo-PlayerGamesinStrategic andExtensiveForm 53 BernhardvonStengel 3.1 Introduction 53 3.2 BimatrixGamesandtheBestResponseCondition 54 3.3 EquilibriaviaLabeledPolytopes 57 3.4 TheLemke–HowsonAlgorithm 61 3.5 IntegerPivoting 63 3.6 DegenerateGames 65 3.7 ExtensiveGamesandTheirStrategicForm 66 3.8 SubgamePerfectEquilibria 68 3.9 ReducedStrategicForm 69 3.10 TheSequenceForm 70 3.11 ComputingEquilibriawiththeSequenceForm 73 3.12 FurtherReading 75 3.13 DiscussionandOpenProblems 75 Bibliography 76 Exercises 77 4 Learning,RegretMinimization,andEquilibria 79 AvrimBlumandYishayMansour 4.1 Introduction 79 4.2 ModelandPreliminaries 81 4.3 ExternalRegretMinimization 82 4.4 RegretMinimizationandGameTheory 88 4.5 GenericReductionfromExternaltoSwapRegret 92 4.6 ThePartialInformationModel 94 4.7 OnConvergenceofRegret-MinimizingStrategiestoNash EquilibriuminRoutingGames 96 4.8 Notes 99 Bibliography 99 Exercises 101 5 CombinatorialAlgorithmsforMarketEquilibria 103 VijayV.Vazirani 5.1 Introduction 103 5.2 Fisher’sLinearCaseandtheEisenberg–GaleConvexProgram 105 5.3 CheckingIfGivenPricesAreEquilibriumPrices 108 5.4 TwoCrucialIngredientsoftheAlgorithm 109 5.5 ThePrimal-DualSchemaintheEnhancedSetting 109 5.6 TightSetsandtheInvariant 111 5.7 BalancedFlows 111 5.8 TheMainAlgorithm 115 5.9 FindingTightSets 117 5.10 RunningTimeoftheAlgorithm 118 5.11 TheLinearCaseoftheArrow–DebreuModel 121 5.12 AnAuction-BasedAlgorithm 122 5.13 ResourceAllocationMarkets 124 P1:SBT FM-main CUNY1061-Nisan 0521872820 August3,2007 12:6 contents vii 5.14 AlgorithmforSingle-SourceMultiple-SinkMarkets 126 5.15 DiscussionandOpenProblems 131 Bibliography 132 Exercises 133 6 ComputationofMarketEquilibriabyConvexProgramming 135 BrunoCodenottiandKasturiVaradarajan 6.1 Introduction 135 6.2 FisherModelwithHomogeneousConsumers 141 6.3 ExchangeEconomiesSatisfyingWGS 142 6.4 SpecificUtilityFunctions 148 6.5 Limitations 150 6.6 ModelswithProduction 152 6.7 BibliographicNotes 155 Bibliography 156 Exercises 158 7 GraphicalGames 159 MichaelKearns 7.1 Introduction 159 7.2 Preliminaries 161 7.3 ComputingNashEquilibriainTreeGraphicalGames 164 7.4 GraphicalGamesandCorrelatedEquilibria 169 7.5 GraphicalExchangeEconomies 176 7.6 OpenProblemsandFutureResearch 177 7.7 BibliographicNotes 177 Acknowledgments 179 Bibliography 179 8 CryptographyandGameTheory 181 YevgeniyDodisandTalRabin 8.1 CryptographicNotionsandSettings 181 8.2 GameTheoryNotionsandSettings 187 8.3 ContrastingMPCandGames 189 8.4 CryptographicInfluencesonGameTheory 191 8.5 GameTheoreticInfluencesonCryptography 197 8.6 Conclusions 202 8.7 Notes 203 Acknowledgments 204 Bibliography 204 II AlgorithmicMechanismDesign 9 IntroductiontoMechanismDesign(forComputerScientists) 209 NoamNisan 9.1 Introduction 209 9.2 SocialChoice 211 9.3 MechanismswithMoney 216 9.4 ImplementationinDominantStrategies 222 P1:SBT FM-main CUNY1061-Nisan 0521872820 August3,2007 12:6 viii contents 9.5 CharacterizationsofIncentiveCompatibleMechanisms 225 9.6 Bayesian–NashImplementation 233 9.7 FurtherModels 238 9.8 Notes 239 Acknowledgments 240 Bibliography 241 10 MechanismDesignwithoutMoney 243 JamesSchummerandRakeshV.Vohra 10.1 Introduction 243 10.2 Single-PeakedPreferencesoverPolicies 244 10.3 HouseAllocationProblem 253 10.4 StableMatchings 255 10.5 FutureDirections 262 10.6 NotesandReferences 263 Bibliography 264 Exercises 264 11 CombinatorialAuctions 267 LiadBlumrosenandNoamNisan 11.1 Introduction 267 11.2 TheSingle-MindedCase 270 11.3 WalrasianEquilibriumandtheLPRelaxation 275 11.4 BiddingLanguages 279 11.5 IterativeAuctions:TheQueryModel 283 11.6 CommunicationComplexity 287 11.7 AscendingAuctions 289 11.8 BibliographicNotes 295 Acknowledgments 296 Bibliography 296 Exercises 298 12 ComputationallyEfficientApproximationMechanisms 301 RonLavi 12.1 Introduction 301 12.2 Single-DimensionalDomains:JobScheduling 303 12.3 MultidimensionalDomains:CombinatorialAuctions 310 12.4 ImpossibilitiesofDominantStrategyImplementability 317 12.5 AlternativeSolutionConcepts 321 12.6 BibliographicNotes 327 Bibliography 327 Exercises 328 13 ProfitMaximizationinMechanismDesign 331 JasonD.HartlineandAnnaR.Karlin 13.1 Introduction 331 13.2 BayesianOptimalMechanismDesign 335 13.3 Prior-FreeApproximationstotheOptimalMechanism 339 13.4 Prior-FreeOptimalMechanismDesign 344 P1:SBT FM-main CUNY1061-Nisan 0521872820 August3,2007 12:6 contents ix 13.5 Frugality 350 13.6 ConclusionsandOtherResearchDirections 354 13.7 Notes 357 Bibliography 358 Exercises 360 14 DistributedAlgorithmicMechanismDesign 363 JoanFeigenbaum,MichaelSchapira,andScottShenker 14.1 Introduction 363 14.2 TwoExamplesofDAMD 366 14.3 InterdomainRouting 370 14.4 ConclusionandOpenProblems 379 14.5 Notes 380 Acknowledgments 381 Bibliography 381 Exercises 383 15 CostSharing 385 KamalJainandMohammadMahdian 15.1 CooperativeGamesandCostSharing 385 15.2 CoreofCost-SharingGames 387 15.3 Group-StrategyproofMechanismsandCross-Monotonic Cost-SharingSchemes 391 15.4 CostSharingviathePrimal-DualSchema 394 15.5 LimitationsofCross-MonotonicCost-SharingSchemes 400 15.6 TheShapleyValueandtheNashBargainingSolution 402 15.7 Conclusion 405 15.8 Notes 406 Acknowledgments 408 Bibliography 408 Exercises 410 16 OnlineMechanisms 411 DavidC.Parkes 16.1 Introduction 411 16.2 DynamicEnvironmentsandOnlineMD 413 16.3 Single-ValuedOnlineDomains 417 16.4 BayesianImplementationinOnlineDomains 431 16.5 Conclusions 435 16.6 Notes 436 Acknowledgments 437 Bibliography 437 Exercises 439 III QuantifyingtheInefficiencyofEquilibria 17 IntroductiontotheInefficiencyofEquilibria 443 TimRoughgardenandE´vaTardos 17.1 Introduction 443 P1:SBT FM-main CUNY1061-Nisan 0521872820 August3,2007 12:6 x contents 17.2 FundamentalNetworkExamples 446 17.3 InefficiencyofEquilibriaasaDesignMetric 454 17.4 Notes 456 Bibliography 457 Exercises 459 18 RoutingGames 461 TimRoughgarden 18.1 Introduction 461 18.2 ModelsandExamples 462 18.3 Existence,Uniqueness,andPotentialFunctions 468 18.4 ThePriceofAnarchyofSelfishRouting 472 18.5 ReducingthePriceofAnarchy 478 18.6 Notes 480 Bibliography 483 Exercises 484 19 NetworkFormationGamesandthePotentialFunctionMethod 487 E´vaTardosandTomWexler 19.1 Introduction 487 19.2 TheLocalConnectionGame 489 19.3 PotentialGamesandaGlobalConnectionGame 494 19.4 FacilityLocation 502 19.5 Notes 506 Acknowledgments 511 Bibliography 511 Exercises 513 20 SelfishLoadBalancing 517 BertholdVo¨cking 20.1 Introduction 517 20.2 PureEquilibriaforIdenticalMachines 522 20.3 PureEquilibriaforUniformlyRelatedMachines 524 20.4 MixedEquilibriaonIdenticalMachines 529 20.5 MixedEquilibriaonUniformlyRelatedMachines 533 20.6 SummaryandDiscussion 537 20.7 BibliographicNotes 538 Bibliography 540 Exercises 542 21 ThePriceofAnarchyandtheDesignofScalableResource AllocationMechanisms 543 RameshJohari 21.1 Introduction 543 21.2 TheProportionalAllocationMechanism 544 21.3 ACharacterizationTheorem 551 21.4 TheVickrey–Clarke–GrovesApproach 559 21.5 ChapterSummaryandFurtherDirections 564