Game Theory - Winter 2008/9
Uri Feige ,
and Robi Krauthgamer Moni Naor
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!
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
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.
Handouts and Homework
Handout 1 (Nov 5th Lecture)
Handout 2 (Nov 12th Lecture)
Handout 3 (Nov 19th Lecture) (See
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)
Lecture 8 Regret Minimization (Dec 24th Lecture) Dec 31st: Fourth Israeli Seminar on Computational Game Theory .
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)
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
(with username=agt1user, password=camb2agt).
An Algorithmic Game
Theory Primer (survey), TCS 2008.
Equlibiria Notions: 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.
Fixed Points, and Complexity Classes (Survey), STACS 2008.
The price of anarchy and stability:
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.
Robert Kleinberg, A Course on
Learning, Games, and
Electronic Markets, Cornell
Arrow's Impossibility Theorem:
A Difficulty in the Concept of Social Welfare, The Journal of Political
Economy, 1950, Pages 328-346.
Three Brief Proofs
of Arrow's impossibility Theorem
Philip J. Reny,
Arrow’s Theorem and the Gibbard-Satterthwaite Theorem: A Unified Approach,
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
Gale and Shapely,
, American Mathematical Monthly, 1962. (JSTOR) College admissions and the
stability of marriage 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,
Marriage Problem: Structure and Algorithms, MIT Press, 1989
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
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,
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,
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
Game Theory and Cryptography:
Game Theory Net, Many Resources on Game Theory (Lecture notes, pointers to literature). Similar Courses around the world:
, University of Pennsylvania Computational Game
Theory Adrian Vetta,
, McGill University
Algorithmic Game Theory
, Cornell University Algorithmic Game
, Stanford University Algorithmic Game
, Berkeley Algorithmic
Aspects of Game Theory
, Yale University
Economics and Computation
, Hebrew University CS, Game theory,
Peter Bro Miletersen,
, Fall 2008, Aarhus Algorithmic
Vincent Conitzer ,
, Duke University. Computational Game Theory and Mechanism Design
, 2003- 2008, University of Edinburgh
Algorithmic Game Theory and Applications
Adam Tauman Kalai,
, Spring 2008, Georgia Tech.
Game Theory and Computer Science