Algorithmic Game Theory

In recent years game theory has had a substantial impact on computer science, especially on Internet- and e-commerce-related issues. Algorithmic Game Theory, first published in 2007, develops the central ideas and results of this exciting area in a clear and succinct manner. More than 40 of the top researchers in this field have written chapters that go from the foundations to the state of the art. Basic chapters on algorithmic methods for equilibria, mechanism design and combinatorial auctions are followed by chapters on important game theory applications such as incentives and pricing, cost sharing, information markets and cryptography and security. This definitive work will set the tone of research for the next few years and beyond. Students, researchers, and practitioners alike need to learn more about these fascinating theoretical developments and their widespread practical application. ToC ......Page 5 Foreword......Page 13 Preface......Page 17 Contributors......Page 19 I Computing in Games......Page 22 1.1 Games, Old and New......Page 24 1.2 Games, Strategies, Costs, and Payoffs......Page 30 1.3 Basic Solution Concepts......Page 31 1.4 Finding Equilibria and Learning in Games......Page 37 1.5 Refinement of Nash: Games with Turns and Subgame Perfect Equilibrium......Page 39 1.7 Cooperative Games......Page 41 1.8 Markets and Their Algorithmic Issues......Page 43 Exercises......Page 47 2.1 Introduction......Page 50 2.2 Is the Nash Equilibrium Problem NP-Complete......Page 52 2.3 The Lemke-Howson Algorithm......Page 54 2.4 The Class PPAD......Page 57 2.5 Succinct Representations of Games......Page 60 2.6 The Reduction......Page 62 2.7 Correlated Equilibria......Page 66 2.8 Concluding Remarks......Page 70 Bibliography......Page 71 3.1 Introduction......Page 74 3.2 Bimatrix Games and the Best Response Condition......Page 75 3.3 Equilibria via Labeled Polytopes......Page 78 3.4 The Lemke-Howson Algorithm......Page 82 3.5 Integer Pivoting......Page 84 3.6 Degenerate Games......Page 86 3.7 Extensive Games and Their Strategic Form......Page 87 3.8 Subgame Perfect Equilibria......Page 89 3.9 Reduced Strategic Form......Page 90 3.10 The Sequence Form......Page 91 3.11 Computing Equilibria with the Sequence Form......Page 94 3.13 Discussion and Open Problems......Page 96 Bibliography......Page 97 Exercises......Page 98 4.1 Introduction......Page 100 4.2 Model and Preliminaries......Page 102 4.3 External Regret Minimization......Page 103 4.4 Regret Minimization and Game Theory......Page 109 4.5 Generic Reduction from External to Swap Regret......Page 113 4.6 The Partial Information Model......Page 115 4.7 On Convergence of Regret-Minimizing Strategies to Nash Equilibrium in Routing Games......Page 117 Bibliography......Page 120 Exercises......Page 122 5.1 Introduction......Page 124 5.2 Fisher-s Linear Case and the Eisenberg-Gale Convex Program......Page 126 5.3 Checking If Given Prices Are Equilibrium Prices......Page 129 5.5 The Primal-Dual Schema in the Enhanced Setting......Page 130 5.7 Balanced Flows......Page 132 5.8 The Main Algorithm......Page 136 5.9 Finding Tight Sets......Page 138 5.10 Running Time of the Algorithm......Page 139 5.11 The Linear Case of the Arrow-Debreu Model......Page 142 5.12 An Auction-Based Algorithm......Page 143 5.13 Resource Allocation Markets......Page 145 5.14 Algorithm for Single-Source Multiple-Sink Markets......Page 147 5.15 Discussion and Open Problems......Page 152 Bibliography......Page 153 Exercises......Page 154 6.1 Introduction......Page 156 6.2 Fisher Model with Homogeneous Consumers......Page 162 6.3 Exchange Economies Satisfying WGS......Page 163 6.4 Specific Utility Functions......Page 169 6.5 Limitations......Page 171 6.6 Models with Production......Page 173 6.7 Bibliographic Notes......Page 176 Bibliography......Page 177 Exercises......Page 179 7.1 Introduction......Page 180 7.2 Preliminaries......Page 182 7.3 Computing Nash Equilibria in Tree Graphical Games......Page 185 7.4 Graphical Games and Correlated Equilibria......Page 190 7.5 Graphical Exchange Economies......Page 197 7.7 Bibliographic Notes......Page 198 Bibliography......Page 200 8.1 Cryptographic Notions and Settings......Page 202 8.2 Game Theory Notions and Settings......Page 208 8.3 Contrasting MPC and Games......Page 210 8.4 Cryptographic Influences on Game Theory......Page 212 8.5 Game Theoretic Influences on Cryptography......Page 218 8.6 Conclusions......Page 223 8.7 Notes......Page 224 Bibliography......Page 225 II Algorithmic Mechanism Design......Page 228 9.1 Introduction......Page 230 9.2 Social Choice......Page 232 9.3 Mechanisms with Money......Page 237 9.4 Implementation in Dominant Strategies......Page 243 9.5 Characterizations of Incentive Compatible Mechanisms......Page 246 9.6 Bayesian-Nash Implementation......Page 254 9.7 Further Models......Page 259 9.8 Notes......Page 260 Acknowledgments......Page 261 Bibliography......Page 262 10.1 Introduction......Page 264 10.2 Single-Peaked Preferences over Policies......Page 265 10.3 House Allocation Problem......Page 274 10.4 Stable Matchings......Page 276 10.5 Future Directions......Page 283 10.6 Notes and References......Page 284 Exercises......Page 285 11.1 Introduction......Page 288 11.2 The Single-Minded Case......Page 291 11.3 Walrasian Equilibrium and the LP Relaxation......Page 296 11.4 Bidding Languages......Page 300 11.5 Iterative Auctions: The Query Model......Page 304 11.6 Communication Complexity......Page 308 11.7 Ascending Auctions......Page 310 11.8 Bibliographic Notes......Page 316 Bibliography......Page 317 Exercises......Page 319 12.1 Introduction......Page 322 12.2 Single-Dimensional Domains: Job Scheduling......Page 324 12.3 Multidimensional Domains: Combinatorial Auctions......Page 331 12.4 Impossibilities of Dominant Strategy Implementability......Page 338 12.5 Alternative Solution Concepts......Page 342 Bibliography......Page 348 Exercises......Page 349 13.1 Introduction......Page 352 13.2 Bayesian Optimal Mechanism Design......Page 356 13.3 Prior-Free Approximations to the Optimal Mechanism......Page 360 13.4 Prior-Free Optimal Mechanism Design......Page 365 13.5 Frugality......Page 371 13.6 Conclusions and Other Research Directions......Page 375 13.7 Notes......Page 378 Bibliography......Page 379 Exercises......Page 381 14.1 Introduction......Page 384 14.2 Two Examples of DAMD......Page 387 14.3 Interdomain Routing......Page 391 14.4 Conclusion and Open Problems......Page 400 14.5 Notes......Page 401 Bibliography......Page 402 Exercises......Page 404 15.1 Cooperative Games and Cost Sharing......Page 406 15.2 Core of Cost-Sharing Games......Page 408 15.3 Group-Strategyproof Mechanisms and Cross-Monotonic Cost-Sharing Schemes......Page 412 15.4 Cost Sharing via the Primal-Dual Schema......Page 415 15.5 Limitations of Cross-Monotonic Cost-Sharing Schemes......Page 421 15.6 The Shapley Value and the Nash Bargaining Solution......Page 423 15.7 Conclusion......Page 426 15.8 Notes......Page 427 Bibliography......Page 429 Exercises......Page 431 16.1 Introduction......Page 432 16.2 Dynamic Environments and Online MD......Page 434 16.3 Single-Valued Online Domains......Page 438 16.4 Bayesian Implementation in Online Domains......Page 452 16.5 Conclusions......Page 456 16.6 Notes......Page 457 Bibliography......Page 458 Exercises......Page 460 III Quantifying the Inefficiency of Equilibria......Page 462 17.1 Introduction......Page 464 17.2 Fundamental Network Examples......Page 467 17.3 Inefficiency of Equilibria as a Design Metric......Page 475 17.4 Notes......Page 477 Bibliography......Page 478 Exercises......Page 480 18.1 Introduction......Page 482 18.2 Models and Examples......Page 483 18.3 Existence, Uniqueness, and Potential Functions......Page 489 18.4 The Price of Anarchy of Selfish Routing......Page 493 18.5 Reducing the Price of Anarchy......Page 499 18.6 Notes......Page 501 Bibliography......Page 504 Exercises......Page 505 19.1 Introduction......Page 508 19.2 The Local Connection Game......Page 510 19.3 Potential Games and a Global Connection Game......Page 515 19.4 Facility Location......Page 523 19.5 Notes......Page 527 Bibliography......Page 532 Exercises......Page 534 20.1 Introduction......Page 538 20.2 Pure Equilibria for Identical Machines......Page 543 20.3 Pure Equilibria for Uniformly Related Machines......Page 545 20.4 Mixed Equilibria on Identical Machines......Page 550 20.5 Mixed Equilibria on Uniformly Related Machines......Page 554 20.6 Summary and Discussion......Page 558 20.7 Bibliographic Notes......Page 559 Bibliography......Page 561 Exercises......Page 563 21.1 Introduction......Page 564 21.2 The Proportional Allocation Mechanism......Page 565 21.3 A Characterization Theorem......Page 572 21.4 The Vickrey-Clarke-Groves Approach......Page 580 21.5 Chapter Summary and Further Directions......Page 585 21.6 Notes......Page 586 Bibliography......Page 587 Exercises......Page 588 IV Additional Topics......Page 590 22 Incentives and Pricing in Communications Networks......Page 592 22.1 Large Networks - Competitive Models......Page 593 22.2 Pricing and Resource Allocation - Game Theoretic Models......Page 599 22.3 Alternative Pricing and Incentive Approaches......Page 608 Bibliography......Page 611 23.1 Introduction......Page 614 23.2 The p2p File-Sharing Game......Page 615 23.3 Reputation......Page 617 23.4 A Barter-Based System: BitTorrent......Page 621 23.5 Currency......Page 622 23.6 Hidden Actions in p2p Systems......Page 623 23.8 Bibliographic Notes......Page 629 Bibliography......Page 630 Exercises......Page 631 24.1 Introduction......Page 634 24.2 A First Model: Networked Coordination Games......Page 635 24.3 More General Models of Social Contagion......Page 639 24.4 Finding Influential Sets of Nodes......Page 643 24.5 Empirical Studies of Cascades in Online Data......Page 648 24.6 Notes and Further Reading......Page 651 Bibliography......Page 652 Exercises......Page 653 25.1 Introduction......Page 654 25.2 Misaligned Incentives......Page 655 25.3 Informational Asymmetries......Page 657 25.4 The Economics of Censorship Resistance......Page 661 25.5 Complex Networks and Topology......Page 664 25.6 Conclusion......Page 667 25.7 Notes......Page 668 Bibliography......Page 669 26.1 Introduction: What Is a Prediction Market......Page 672 26.2 Background......Page 673 26.3 Combinatorial Prediction Markets......Page 678 26.4 Automated Market Makers......Page 683 26.5 Distributed Computation through Markets......Page 686 26.6 Open Questions......Page 691 26.7 Bibliographic Notes......Page 692 Bibliography......Page 693 Exercises......Page 695 27.1 Introduction: Why Are Reputation Systems Important......Page 698 27.2 The Effect of Reputations......Page 701 27.3 Whitewashing......Page 703 27.4 Eliciting Effort and Honest Feedback......Page 704 27.5 Reputations Based on Transitive Trust......Page 710 27.6 Conclusion and Extensions......Page 714 27.7 Bibliographic Notes......Page 715 Bibliography......Page 716 Exercises......Page 717 28.1 Introduction......Page 720 28.2 Existing Models and Mechanisms......Page 722 28.3 A Static Model......Page 723 28.4 Dynamic Aspects......Page 728 28.5 Open Questions......Page 732 28.6 Bibliographic Notes......Page 733 Bibliography......Page 734 Exercises......Page 736 29.1 Evolutionary Game Theory......Page 738 29.2 The Computational Complexity of Evolutionarily Stable Strategies......Page 741 29.3 Evolutionary Dynamics Applied to Selfish Routing......Page 744 29.4 Evolutionary Game Theory over Graphs......Page 749 29.6 Notes......Page 754 Bibliography......Page 755 Exercises......Page 756 Index......Page 758 With Contributions From Major Researchers In The Field, 'algorithmic Game Theory' Presents A Comprehensive Treatment Of This Important Practical Application. Basic Solution Concepts And Computational Issues / Éva Tardos, Vijay V. Vazirani -- The Complexity Of Finding Nash Equilibria / Christos H. Papadimitriou -- Equilibrium Computation For Two-player Games In Strategic And Extensive Form / Bernhard Von Stengel -- Learning, Regret Minimization, Equilibria / Avrim Blum, Yishay Mansour -- Combinatorial Algorithms For Market Equilibria / Vijay V. Vazirani -- Computation Of Market Equilibria By Convex Programming / Bruno Codenotti, Kasturi Varadarajan -- Graphical Games / Michael Kearns -- Cryptography And Game Theory / Yevgeniy Dodis, Tal Rabin -- Introduction To Mechanism Design (for Computer Scientists) / Noam Nisan -- Mechanism Design Without Money / James Schummer, Rakesh V. Vohra -- Combinatorial Auctions / Liad Blumrosen, Noam Nisan -- Computationally Efficient Approximation Mechanisms / Ron Lavi -- Profit Maximization In Mechanism Design / Jason D. Hartline, Anna R. Karlin --^ Distributed Algorithmic Mechanism Design / Joan Feigenbaum, Michael Schapira, Scott Shenker -- Cost Sharing / Kamal Jain, Mohammad Mahdian -- Online Mechanisms / David C. Parkes -- Introduction To The Inefficiency Of Equilibria / Tim Roughgarden, Éva Tardos -- Routing Games / Tim Roughgarden -- Network Formation Games And The Potential Function Method / Éva Tardos, Tom Wexler -- Selfish Load Balancing / Berthold Vöcking -- The Price Of Anarchy And The Design Of The Scalable Resource Allocation Mechanisms / Ramesh Johari -- Incentives And Pricing In Communications Networks / Asuman Ozdaglar, R. Srikant -- Incentives In Peer-to-peer Systems / Moshe Babaioff, John Chuang, Michal Feldman -- Cascading Behavior In Networks: Algorithmic And Economic Issues / Jon Kleinberg -- Incentives And Information Security / Ross Anderson [and Others] -- Computational Aspects Of Prediction Markets / David M. Pennock, Rahul Sami --^ Manipulation-resistant Reputation Systems / Eric Friedman, Paul Resnick, Rahul Sami -- Sponsored Search Auctions / Sébastien Lahaie [and Others] -- Computational Evolutionary Game Theory / Siddharth Suri. Edited By Noam Nisan ... [et Al.]. Includes Bibliographical References And Index. In the last few years game theory has had a substantial impact on computer science, especially on Internet- and e-commerce-related issues. More than 40 of the top researchers in this field have written chapters that go from the foundations to the state of the art. Basic chapters on algorithmic methods for equilibria, mechanism design and combinatorial auctions are followed by chapters on incentives and pricing, cost sharing, information markets and cryptography and security. Students, researchers and practitioners alike need to learn more about these fascinating theoretical developments and their widespread practical application.