Algorithmic Game Theory
Computer Science 6840
4139 Upson Hall and 340 Upson hall
eva at cs.cornell.edu
e-mails: renatoppl and vasilis [at] cs [dot] cornell [dot] edu
See Piazza for office hours during the final weeks.
We also have a Piazza
page. Piazza is a web-based discussion forum for communication with
classmates and the course staff. Except for confidential matters, Piazza is
preferred over email, as anyone can answer and everyone can benefit from the
answer. The coure staff weill monitor questions and answers and endorse good
answers in a timely manner. If you know the answer to a question, feel free to
post a reply yourself, but please avoid giving away any hints on the homework
or posting any part of a solution.
Algorithmic Game Theory combines algorithmic thinking with game-theoretic,
or, more generally, economic concepts. The course will study a range of topics
at this interface. The only prerequisite to the course is mathematical
thinking at the level of doing well at CS 4820.
We will mainly use the books
- Algorithmic Game Theory.
eds. Nisan, Roughgarden, Tardos, Vazirani (username=agt1user,
password=camb2agt), Cambridge, 2007.
and supplement these with additional papers.
Another excellent textbook that covers several of the course's topics is Shoham
and Leyton-Brown, Multiagent Systems,
Cambridge, 2008. For a nice introduction to Game Theory look at Ken Binmore:
Game Theory: a Very Short Introduction, Oxford University Press.
- Problem set
1 was due Wednesday, February 15th. It is now graded. See solutions and grades at CMS.
- Problem set
2 was due Wednesday, February 29. It is now graded. See solutions and grades at CMS.
- Problem set
3 was due Friday, March 16. It is now graded. See solutions and grades at CMS.
- project proposal was due
Wednesday April 4. It is now graded. See comments and grades at CMS.
- Problem set 4 was due
Wednesday, April 18.
- Project is due Friday,
- Take-home final during the
week of finals (between May 8-18). Final is cumulative, and is a non-cooperative version of the homeworks. You can choose any 72 hour period to do the final during May 8-18. Office hours during the final week will be posted here and also on Piazza.
The tex version of
the notes for lecture 1 for suggested format.
- Notes for lecture 1:Monday, Jan 23
introduction and Breass paradox.
for lecture 2 Wednesday, Jan 25 on discrete congestion games and the
existence of equilibria
- Notes for lecture 3, Friday,
Jan 27 on non-atomic congestion games and equilibria
for lecture 4, Monday Jan 30 price of anarchy for non-atomic congestion
games coming soon
- Notes for lecture 5, Wednesday Feb 1 on
price of anarchy for smooth games
for lecture 6, Friday, Feb 3, utility games and the facility location
- Notes for lecture 7, Monday Feb 6, price
of anarchy for facility location
for lecture 8, Wednesday Feb 8 on quality solutions without reaching
for lecture 9, Friday Feb 10 (by Vasilis Syrgkanis) on Price of
Stability in cost-sharing game
for lecture 10, Monday, Feb 13 on strong Nash equilibria, and the strong price
of anarchy for the cost-sharing games,
for lecture 11, Wednesday, Feb 15 on no-regret learning and the privce of
for lecture 12, Frida, Feb 17 y on correlated equilibia and coarse correlated
equilibria in games
- Notes for lecture 13, Monday, Feb 20 on the
multiplicative weight algorithm for learning, coming soon
for lecture 14, Wednesday, Feb 22 on coarse correlated equilibria, and connection
to Nash in 2-person 0-sum games.
for lecture 15, Friday, Feb 24 on single item auction, 2nd price, and fixed
price in Bayesian setting,
for lecture 16, Monday, Feb 27 on Bayesian Nash equilibrium, and the first
price auction for a single item.
- Notes for lecture 18,
Wednesday, Feb 29 on the VCG mechanism
for lecture 19, Friday, March 2 on Bayesian Nash equilibria in single-parameter
environments and revenue equivalence
- Notes for lecture 20, Monday, March 5 revenue
equivalence continued, and the quantile space
for lecture 21,Wednesday, March 7 on Meyerson optimal auction.
for lecture 22, Friday, March 9 approximately optimal auction via monopoly
- Notes for lecture 23, Monday, March 12 non-regular distributions and the ironed virtual value
- Notes for lecture 25, Wednesday, March 14, Revenue optimal auction when values are independent, but may not be regular, coming soon.
- Notes for lecture 26, Friday, March 16, Matroid environments, and optimal auctions in such environments
- SPRING BREAK
- Notes for lecture 27, Monday, March 26 greedy auctions for single minded bidders coming soon. (Truth Revelation in Approximately Efficient Combinatorial Auctions. D. Lehmann, L. I. O'Callaghan, Y. Shoham. Journal of the ACM , 49 (5), September 2002, 577-602.
- Notes for lecture 28, Wednesday, March 28 greedy auctions and approximation algorithms. (Price of Anarchy for Greedy Auctions B. Lucier and A. Borodin.SODA 2010)
- Notes for lecture 29, Friday, March 30 on second price item auctions
- Notes for lecture 30, Monday, April 2nd on greedy auction and second price item auction as a smooth game
- Notes for lecture 31, Wednesday, April 4th on Price of anarchy for Second price item auctions and learning outcomes
- Notes for lecture 32, Friday, April 6th on Generalized second price auction.
- Notes for lecture 33, Monday, April 9th on the Prize of anarchy in Generalized second price auction
- Notes for lecture 34, Wednesday, April 11st, on Bandwidth sharing in a single link, and price equilibrium.
- Notes for lecture 35, Friday, April 13th, on game theoretical analysis of fair sharing on a single link, coming soon
- Notes for lecture 36, Monday April 16th, on fair sharing on a network. See also R. Johari and J.N. Tsitsiklis (2004). Efficiency loss in a network resource allocation game.
- Notes for lecture 37, Wednesday April 18. End of our fair sharing discussion, and starting market equilibria.
- Notes for lecture 38, Friday April 20, on Arrow-Debreu model of markets.
- Notes for lecture 39, Monday, April 23, existence of Nash equilibria in finite games
- Notes for lecture 40, Wednesday, April 25 on Sperner lemma in the plane and Brouwer fixed point theorem
- Notes for lecture 41, Friday, April 27 on high dimensional Sperner lemma and deriving Brouwer fixed point theorem
- Notes for lecture 42, Monday, April 30 on complexity of finding equilibria
- Notes for lecture 43, Wednesday May 2nd on NP completeness of deciding if a game has two Nash equilibria
Video of all previous classes are available at www.videonote.com/Cornell
A LaTex tutorial last year can be found at http://www.cs.cornell.edu/courses/cs4820/2011sp/handouts/tutorial2.html
Course outline (subject to change):
- Introduction to Algorithms
and Games: (Chapter 1) games, Nash equilibria, solution concepts, and
- Quantifying the Inefficiency
of Equilibria: (Part III: Chapters 17-21)
- Routing Games and
other congestion games: Nash equilibria
- Potential games:
Facility Location, Network Design
- Selfish Routing and Wardrop equilibria
- Network design games
- Bandwidth sharing
- Algorithmic Aspects of
Equilibria (Part I: Chapters 2-7)
- existence and
complexity of equilibria
- graphical games
- Learning in
games fictitious play, experts algorithm, no-regret algorithms;
convergence for zero-sum games
- Quantifying the Inefficiency of learning outcomes
- correlated equilibria
and connection to learning in games
- Extensive form games
- Mechanism design and pricing
games (Part II, and Hartline manuscipt)
- Social Choice Theory:
Arrow's impossibility theorem, the Gibbard-Satterthwaite theorem;
- Mechanisms with Money:
second-price auction, digital goods, Vickrey-Clarke-Groves mechanism;
Auctions:; Auction Games, Generalized Second Prize
- Bayesian Mechanism
Course work consists of 4 homework sets, a final, a project, and scribe
notes. You may work in pairs on homeworks and the project, and hand in a shared homework.
You may discuss homework questions with other students, but closely collaborate
only with your partner. The final is a non-cooperative version of the
homework. Extra credit will be available for solving more homework
problemsthan required or by improving wikipedia pages about topics discussed in
class. Grades and solutions to the homeworks will be kept in CMS.
The project should be a research-like experience (understand what is known
about about a research problem, and try to advance knowledge). You can base
projects on recent research papers: understanding what they are doing, and
attempting to improve the model or result. Or you can base projects on your own
research interests. You need to write your project result in format of a paper,
expected to be 6-10 pages long (definitely no longer than 10).
Course grade is determined roughly as
- Homeworks: 10% each
- Scribe notes 5%
- project proposal 5%
- project 25%
- take home final 25%
Extra credit can be earned by solving all problem on the problem set, or by improving pages on wikipedia related to the course. Extra credit is very useful for getting an A+, and can also be used can to partially make up missing credit on homeworks, and the final.
Classes on similar topics at other
Earlier version of this
Theory by Christos Papadimitriou
Algorithmic Game Theory
by Tim Roughgarden
Mechanism Design by Jason Hartline
Topics in Algorithmic
Game Theory by Costis Daskalakis