Algorithmic Game Theory - Feige Krauthgamer Naor

Algorithmic Game Theory - Winter 2008/9

Instructors: Uri Feige, Robi Krauthgamer and Moni Naor

Grader: Ronen Gradwohl and Inbal Talgam

When: Wednesday 14:00--16:00
Where: Ziskind 1
First meeting: Nov 5th 2008

Practice exam is available!
All homewrok have been graded and available in the slot of the course!

DESCRIPTION:

Recent years have witnessed a tremendous surge of activity at the interface of computer science and game theory. The purpose of this course is to to survey these developments. Topics covered will include :

Solution concepts: Nash equilibrium and general equilibrium
Refinements of equilibrium concepts
Computing equlibria - complexity and algorithms
The price of anarchy and the price of stability
Graphical Games
Social choice theory
Mechanism Design and Auctions
Cryptography and Game Theory,
Evolutionary game theory and repeated games
Fairness, Cooperative games and Multicast pricing and Cost Sharing
Game Theoretic aspects of the structure of the Internet

PREREQUISITES: Students are expected to be familiar with algorithms, complexity theory, probability theory, and linear algebra, at an undergraduate level. No prior game theory course will be assumed.

REQUIREMENTS:

Handouts and Homework

Handout 1 (Nov 5th Lecture)

Handout 2 (Nov 12th Lecture)

Handout 3 (Nov 19th Lecture) (See Advanced Algorithms 2008 for material on Linear Programming)

Handout 4 (Nov 26 Lecture)

Handout 5 (Dec 3rd Lecture)

Notes for Lectures 1-5

Handout 6 (Dec 10th Lecture)

Handout 7 (Dec 17th Lecture)

Slides for Lecture 8 Regret Minimization (Dec 24th Lecture)

Dec 31st: Fourth Israeli Seminar on Computational Game Theory . Slides for Sergiu Hart's talk

Slides for Lecture 9 Social Choice (January 7th Lecture)

Slides for Lecture 10 Mechanism Design (Jan 14 Lecture)

Slides for Lecture 11 Combinatorial Auctions (Jan 21 Lecture)

Handout 12

Handout 13

Practice exam

Final Exam

Bibliography

Noam Nisan, Tim Roughgarden, Eva Tardos and Vijay V. Vazirani (Editors), Algorithmic Game Theory, Cambridge University Press, 2007. The closest to a textbook this course has. Available for online viewing here (with username=agt1user, password=camb2agt).
Tim Roughgarden, An Algorithmic Game Theory Primer (survey), TCS 2008.
Equlibiria Notions:

John Nash, Non-Cooperative Games (JSTOR), Annals of Mathematics 1951. John Nash's Homepage
- Math reviews on Nash's papers: An anemic review of the announcement in PNAS
- An enthusiastic one on the full paper by David Gale.
R. J. Aumann, Subjectivity and correlation in randomized strategies. Journal of Mathematical Economics, 1:67-96, 1974

The Complexity of Computing Equilibria:
- X. Chen, X. Deng, Settling the Complexity of 2-Player Nash-Equilibrium , Proc. of FOCS 2006
- C. Daskalakis, P. W. Goldberg and C. H. Papadimitriou, The Complexity of Computing a Nash Equilibrium, Proc. of STOC 2006.
- I. Gilboa and E. Zemel, Nash and Correlated Equilibria: Some Complexity Considerations, Games and Economic Behavior, 1 pp. 80-93 (1989)
- P. W. Goldberg and C. H. Papadimitriou, Reducibility Among Equilibrium Problems, Proc. of STOC 2006.
- Mihalis Yannakakis: Equilibria, Fixed Points, and Complexity Classes (Survey), STACS 2008.
Graphical Games
- M. Kearns, M. Littman, and S. Singh, Graphical Models for Game Theory, Proceedings of UAI 2001.
- Michael Kearns, Graphical Games, in Algorithmic Game Theory.

The price of anarchy and stability:

Worst-case Equilibria, by Elias Koutsoupias and Christos Papadimitriou
How Bad is Selfish Routing?, by Tim Roughgarden and Eva Tardos, Journal of the ACM, 49(2):236--259, 2002.
Tim Roughgarden, Selfish Routing and the Price of Anarchy, MIT Press. First chapter available here.

The Braess paradox:

On a Paradox of Traffic Planning, English translation of the original 1968 article on the "paradox".
What if They Closed 42d Street and Nobody Noticed?, by Gina Kolata, December 25, 1990, New York Times.
The Braess paradox in mechanical, traffic, and other networks, by C. M. Penchina and L. J. Penchina, American Journal of Physics, Volume 71(5), May 2003, pp. 479--482.
Paradoxical behaviour of mechanical and electrical networks, by J. E. Cohen and P. Horowitz, Nature, Vol 352, pp. 699-701, 1991.
Braess's paradox in Wikipedia.

Regret Minimization:

Avirm Blum and Yishai Mansour, Learning, Regret Minimization, and Equilibria, in Algorithmic Game Theory.
Dean Foster and Rakesh Vohra, Regret in the On-Line Decision Problem, Games and Economic Behavior 1999. A survey with the history of the development of the idea in different fields.

Robert Kleinberg, A Course on Learning, Games, and Electronic Markets, Cornell

Social Choice- Arrow's Impossibility Theorem:

Kenneth Arrow, A Difficulty in the Concept of Social Welfare, The Journal of Political Economy, 1950, Pages 328-346.
John Geanakoplos, Three Brief Proofs of Arrow's impossibility Theorem
Philip J. Reny, Arrow’s Theorem and the Gibbard-Satterthwaite Theorem: A Unified Approach, Economics Letters Volume 70, Issue 1, January 2001, Pages 99-105
Alan D. Taylor, The Manipulability of Voting Systems, American Mathematical Monthly, 2002.
Ehud Friedgut, Gil Kalai and Noam Nisan, Elections Can be Manipulated Often

Stable Matching:

Gale and Shapely, College admissions and the stability of marriage, American Mathematical Monthly, 1962. (JSTOR)
Alvin Roth, A history of the application to matching residents and hospitals
Alvin Roth and Marilda Sotomayor, Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis, Cambridge University Press, 1990.
Dan Gusfield and Robert Irving, The Stable Marriage Problem: Structure and Algorithms, MIT Press, 1989

Mechanism Design:

Introduction to Mechanism Design (for Computer Scientists), by Noam Nisan, in Algorithmic Game Theory.
Algorithmic Mechanism Design (or here), by Noam Nisan and Amir Ronen, in Games and Economic Behavior, Volume 35(1-2), April 2001, Pages 166--196.
Designing the Perfect Auction, by Hal Varian, Communications of the ACM, 51 (2008), pp. 9-11.
Tutorial on Optimal Mechanism Design without Prior, by Jason Hartline

Auctions:

Combinatorial Auctions by Liad Blumrosen and Noam Nisan, in Algorithmic Game Theory.
A Course on Auction Theory , taught by Ron Lavi, Technion.
William Vickrey's 1961 paper on auctions: Counterspeculation, auctions, and competitive sealed tenders .
Noam Nisan and Ilya Segal, The communication requirements of efficient allocations and supporting pricesstar , Journal of Economic Theory Volume 129(1), July 2006, Pages 192-224.
D. Lehman, L. I. Oćallaghan Y. Shoham, Truth revelation in approximately efficient combinatorial auctions, J. ACM, 49(5) Pages: 577 - 602, 2002.
Article in Haaretz about the Bezeq Auction and interview with Moti Perry (Hebrew)

Game Theory and Cryptography:

Jonathan Katz, Bridging Cryptography and Game Theory: Recent Results and Future Directions, 5th Theory of Cryptography Conference (TCC 2008).
Rational Cryptographic Protocols, Ecrypt Report, Revision 1.0, March 2007.
Yevgeniy Dodis and Tal Rabin, Cryptography and Game Theory, in Algorithmic Game Theory.
Joe Halpern and Rafael Pass, Game Theory with Costly Computation

Resources

Game Theory Net, Many Resources on Game Theory (Lecture notes, pointers to literature).

Similar Courses around the world:

Michael Kearns, Computational Game Theory, University of Pennsylvania
Adrian Vetta, Algorithmic Game Theory, McGill University
Eva Tardos, Algorithmic Game Theory, Cornell University
Tim Roughgarden, Algorithmic Game Theory, Stanford University
Christos Papadimitriou, Algorithmic Aspects of Game Theory, Berkeley
Joan Feigenbaum, Economics and Computation, Yale University
Noam Nisan, CS, Game theory, and Economics, Hebrew University
Peter Bro Miletersen, Algorithmic game theory, Fall 2008, Aarhus
Vincent Conitzer , Computational Game Theory and Mechanism Design , Duke University.

Kousha Etessami, Algorithmic Game Theory and Applications , 2003- 2008, University of Edinburgh

Adam Tauman Kalai, Game Theory and Computer Science, Spring 2008, Georgia Tech.