Spring 2009
Unique Number 54415
CS 395T
Algorithmic Game Theory

Instructor Greg Plaxton (office hours TBD, TAY 3.132; email: plaxton at cs)

Class Time Th 3:30-5

Class Location ENS 115

Required Textbook
The textbook for the course is Algorithmic Game Theory (Cambridge University Press, 2007, edited by Noam Nisan, Tim Roughgarden, Éva Tardos, and Vijay V. Vazirani). To give you a quick sense for the content of the text, I've reproduced the table of contents below, albeit in a somewhat compressed format.

Foreword by Christos Papadimitriou

Introduction by Noam Nisan, Tim Roughgarden, Éva Tardos and Vijay V. Vazirani

Part I: Computing in Games. 1. Basic solution concepts and computational issues, Éva Tardos and Vijay V. Vazirani; 2. Algorithms for equilibria, Christos Papadimitriou; 3. Equilibrium computation for games in strategic and extensive form, Bernhard von Stengel; 4. Learning, regret minimization and correlated equilibria, Avrim Blum and Yishay Mansour; 5. Graphical games, Michael J. Kearns; 6. Cryptography and game theory, Yevgeniy Dodis and Tal Rabin; 7. Combinatorial algorithms for market equilibria, Vijay V. Vazirani; 8. Computation of market equilibria by convex programming, Bruno Codenotti and Kasturi Varadarajan

Part II: Algorithmic Mechanism Design. 9. Introduction to mechanism design (for computer scientists), Noam Nisan; 10. Mechanism design without money, James Schummer and Rakesh V. Vohra; 11. Combinatorial auctions, Noam Nisan and Liad Blumrosen; 12. Computationally efficient approximation mechanisms, Ron Lavi; 13. Profit maximization in mechanism design, Jason Hartline and Anna Karlin; 14. Distributed algorithmic mechanism design, Joan Feigenbaum, Michael Schapira and Scott Shenker; 15. Cost sharing, Kamal Jain and Mohammad Mahdian; 16. On-line mechanisms, David C. Parkes

Part III: Quantifying the Inefficiency of Equilibria. 17. Introduction to the inefficiency of equilibria, Tim Roughgarden and Éva Tardos; 18. Routing games, Tim Roughgarden; 19. Inefficiency of equilibria in network formation games, Éva Tardos and Tom Wexler; 20. Selfish load-balancing, Berthold Vöcking; 21. Efficiency loss and the design of scalable resource allocation mechanisms, Ramesh Johari

Part IV: Additional Topics. 22. Incentives and pricing in communication networks, Asuman Ozdaglar and R. Srikant; 23. Incentives in peer-to-peer systems, John Chuang, Michal Feldman and Moshe Babaioff; 24. Cascading behavior in networks: algorithmic and economic issues, Jon Kleinberg; 25. Incentives and information security, Ross Anderson, Tyler Moore, Shishir Nagaraja and Andy Ozment; 26. Computational aspects of information markets, David M. Pennock and Rahul Sami; 27. Manipulation-resistant reputation systems, Eric Friedman, Paul Resnick and Rahul Sami; 28. Sponsored search auctions, Sebastien Lahaie, David M. Pennock, Amin Saberi and Rakesh V. Vohra; 29. Algorithmic issues in evolutionary game theory, Michael Kearns and Siddharth Suri.

Course Outline
Numerous internet-based applications involve agents who interact with one another to share or trade resources. Such agents are not controlled by a single entity, and may not be willing to cooperate with one another to maximize the global benefit of the system. Instead, such agents are likely to act out of self-interest. Game theory is a rich and longstanding field that studies the behavior of competing agents. Internet applications have led to a resurgence of interest in game theory, and the large scale of these applications has prompted investigation into many interesting new questions related to computational aspects of game theory.

This course surveys some of new results that have been obtained in algorithmic game theory over the past decade. The course is largely based on the material in the required text. Due to the technical depth of the material, it would certainly be possible to devote an entire course to discussing only a handful of of the chapters in the text. But the intent of the present course is to provide a broad overview, so we will generally not devote more than one or two lectures to a given chapter. Our main objectives will be to understand the problems addressed and the results obtained, and to gain a high-level appreciation for the techniques used to achieve these results. Apart from the textbook material, I plan to spend a couple of weeks presenting some of my ongoing research related to the design of auction mechanisms.

While most of the lecture material is drawn from the theoretical computer science community, the course is intended to be useful for students working in other areas, such as AI and networking, where many of the concepts discussed in the course find applicability. Students who have done well in a graduate or upper-division undergraduate theory course should be well-prepared to take this course.

Grading Policy There will not be any major tests or exams in this course. Grades will be based on performance on several problem sets and a number of short quizzes. I have not decided exactly how many quizzes to hold in the course. At one extreme, I might decide to hold a 5-10 minute quiz at the beginning of each lecture. A project option may also be available. I will finalize and post the grading policy before the first class day. Meanwhile, if you'd like to lobby for a particular grading policy (e.g., a project option), let me know!

Instructor	Greg Plaxton (office hours TBD, TAY 3.132; email: plaxton at cs)

Class Time	Th 3:30-5

Class Location	ENS 115

Required Textbook	The textbook for the course is Algorithmic Game Theory (Cambridge University Press, 2007, edited by Noam Nisan, Tim Roughgarden, Éva Tardos, and Vijay V. Vazirani). To give you a quick sense for the content of the text, I've reproduced the table of contents below, albeit in a somewhat compressed format. Foreword by Christos Papadimitriou Introduction by Noam Nisan, Tim Roughgarden, Éva Tardos and Vijay V. Vazirani Part I: Computing in Games. 1. Basic solution concepts and computational issues, Éva Tardos and Vijay V. Vazirani; 2. Algorithms for equilibria, Christos Papadimitriou; 3. Equilibrium computation for games in strategic and extensive form, Bernhard von Stengel; 4. Learning, regret minimization and correlated equilibria, Avrim Blum and Yishay Mansour; 5. Graphical games, Michael J. Kearns; 6. Cryptography and game theory, Yevgeniy Dodis and Tal Rabin; 7. Combinatorial algorithms for market equilibria, Vijay V. Vazirani; 8. Computation of market equilibria by convex programming, Bruno Codenotti and Kasturi Varadarajan Part II: Algorithmic Mechanism Design. 9. Introduction to mechanism design (for computer scientists), Noam Nisan; 10. Mechanism design without money, James Schummer and Rakesh V. Vohra; 11. Combinatorial auctions, Noam Nisan and Liad Blumrosen; 12. Computationally efficient approximation mechanisms, Ron Lavi; 13. Profit maximization in mechanism design, Jason Hartline and Anna Karlin; 14. Distributed algorithmic mechanism design, Joan Feigenbaum, Michael Schapira and Scott Shenker; 15. Cost sharing, Kamal Jain and Mohammad Mahdian; 16. On-line mechanisms, David C. Parkes Part III: Quantifying the Inefficiency of Equilibria. 17. Introduction to the inefficiency of equilibria, Tim Roughgarden and Éva Tardos; 18. Routing games, Tim Roughgarden; 19. Inefficiency of equilibria in network formation games, Éva Tardos and Tom Wexler; 20. Selfish load-balancing, Berthold Vöcking; 21. Efficiency loss and the design of scalable resource allocation mechanisms, Ramesh Johari Part IV: Additional Topics. 22. Incentives and pricing in communication networks, Asuman Ozdaglar and R. Srikant; 23. Incentives in peer-to-peer systems, John Chuang, Michal Feldman and Moshe Babaioff; 24. Cascading behavior in networks: algorithmic and economic issues, Jon Kleinberg; 25. Incentives and information security, Ross Anderson, Tyler Moore, Shishir Nagaraja and Andy Ozment; 26. Computational aspects of information markets, David M. Pennock and Rahul Sami; 27. Manipulation-resistant reputation systems, Eric Friedman, Paul Resnick and Rahul Sami; 28. Sponsored search auctions, Sebastien Lahaie, David M. Pennock, Amin Saberi and Rakesh V. Vohra; 29. Algorithmic issues in evolutionary game theory, Michael Kearns and Siddharth Suri.

Course Outline	Numerous internet-based applications involve agents who interact with one another to share or trade resources. Such agents are not controlled by a single entity, and may not be willing to cooperate with one another to maximize the global benefit of the system. Instead, such agents are likely to act out of self-interest. Game theory is a rich and longstanding field that studies the behavior of competing agents. Internet applications have led to a resurgence of interest in game theory, and the large scale of these applications has prompted investigation into many interesting new questions related to computational aspects of game theory. This course surveys some of new results that have been obtained in algorithmic game theory over the past decade. The course is largely based on the material in the required text. Due to the technical depth of the material, it would certainly be possible to devote an entire course to discussing only a handful of of the chapters in the text. But the intent of the present course is to provide a broad overview, so we will generally not devote more than one or two lectures to a given chapter. Our main objectives will be to understand the problems addressed and the results obtained, and to gain a high-level appreciation for the techniques used to achieve these results. Apart from the textbook material, I plan to spend a couple of weeks presenting some of my ongoing research related to the design of auction mechanisms. While most of the lecture material is drawn from the theoretical computer science community, the course is intended to be useful for students working in other areas, such as AI and networking, where many of the concepts discussed in the course find applicability. Students who have done well in a graduate or upper-division undergraduate theory course should be well-prepared to take this course.

Grading Policy	There will not be any major tests or exams in this course. Grades will be based on performance on several problem sets and a number of short quizzes. I have not decided exactly how many quizzes to hold in the course. At one extreme, I might decide to hold a 5-10 minute quiz at the beginning of each lecture. A project option may also be available. I will finalize and post the grading policy before the first class day. Meanwhile, if you'd like to lobby for a particular grading policy (e.g., a project option), let me know!