Algorithmic Game Theory

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.

Table of Contents

I Computing in Games

1 Basic Solution Concepts and Computational Issues

2 The Complexity of Finding Nash Equilibria

3 Equilibrium Computation for Two-Player Games in Strategic

and Extensive Form

4 Learning, Regret Minimization, and Equilibria

5 Combinatorial Algorithms for Market Equilibria

6 Computation of Market Equilibria by Convex Programming

7 Graphical Games

8 Cryptography and Game Theory

II Algorithmic Mechanism Design

9 Introduction to Mechanism Design (for Computer Scientists)

10 Mechanism Design without Money

11 Combinatorial Auctions

12 Computationally Efficient Approximation Mechanisms

13 Profit Maximization in Mechanism Design

14 Distributed Algorithmic Mechanism Design

15 Cost Sharing

16 Online Mechanisms

III Quantifying the Inefficiency of Equilibria

17 Introduction to the Inefficiency of Equilibria

18 Routing Games

19 Network Formation Games and the Potential Function Method

20 Selfish Load Balancing

21 The Price of Anarchy and the Design of Scalable Resource Allocation Mechanisms

IV Additional Topics

22 Incentives and Pricing in Communications Networks

23 Incentives in Peer-to-Peer Systems

24 Cascading Behavior in Networks: Algorithmic and Economic Issues

25 Incentives and Information Security

26 Computational Aspects of Prediction Markets

27 Manipulation-Resistant Reputation Systems

28 Sponsored Search Auctions

29 Computational Evolutionary Game Theory

About the Authors

Tim Roughgarden is an Assistant Professor in the Department of Computer Science at Stanford University.

Vijay Vazirani got his Bachelor’s degree in Computer Science from MIT in 1979 and his PhD from the University of California at Berkeley in 1983. The central theme in his research career has been the design of efficient algorithms. Additionally, he has also worked on complexity theory, cryptography, coding theory and game theory. In 2001 he published what is widely regarded as the definitive book on Approximation Algorithms; this book has been translated into Japanese, Polish and French. He is a Fellow of the ACM.