Algorithmic Game Theory
Computer Science 6840
Office: 316 Gates
Hall †††††††††† 336† and 324 Gates Hall
eva at cs.cornell.edu
e-mails: email@example.com† and firstname.lastname@example.org
Office hours and
Tardos:† Wednesdays 2:30-3:30 in 316
Monday 11-12 in G11 Gates Hall
Friday 4-5 in G21 Gates Hall††††
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 course staff
will 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
Jan 23 introduction and Brasss paradox and the
tragedy of the commons.
Notes for lecture †from a previous year.
Jan 25 on discrete congestion games and the existence of equilibria.
Notes for lecture from a previous year.
Jan 27: more on potential function for congestion games, and complexity of
reference:† Alex Fabrikant, Christos
Papadimitriou, and Kunal Talwar
complexity of pure Nash equilibria
Jan 29 and Friday, Jan 31; existence of Nash equilibria and PPAD
from a previous year
try the online
Feb 3: multiplicative weight algorithm for binary prediction.
See sections 3-4 of the notes
Feb 5, Hedge algorithm for prediction
sections 5 of notes
and some of sections 4 of notes
Feb 7:† learning and regret in
section 2 of the notes
from 2007, and the first page of the notes
Feb 10, Coarse correlated equilibria of finite games, and learning
Feb 12: non-atomic congestion games and the price of anarchy
Feb 14: non-atomic congestion games and the price of anarchy (cont.)
Feb 17 break
Feb 19, atomic congestion games and the price of anarchy
Feb 21, smooth games minimizing cost and the price of anarchy
Feb 24, Utility maximization games (Guest lecture by Vasilis Syrgkanis)
Notes from Vasilis. See also the paper Intrinsic
Robustness of the Price of Anarchy by Tim Roughgarden
Feb 26: Valid utility games are (1,1) smooth
Feb 28: the facility location game
March 3: outcomes of best responses for the facility location game
March 5, Price of stability of cost sharing game.
March 7, second price auction, Guest lecture by Rad Niazadeh
March 10, Bayesian Nash equilibrium and First price auction
March 12, the VCG mechanism
March 14, Smooth auctions and the price of anarchy in auction games
Notes by Chris Liu
March 17, examples of smooth auctions: first price
Notes by Jiayang Gao
March 19, more examples of smooth auctions: all pay, and first price unit
Notes by Cathy Fan
Friday, March 21,
smooth games and the Bayesian Price of Anarchy
Notes by Xiaodong Wang
Monday, March 24,
Generalized second price action (GSP)
Notes by Daniel Freund
Wednesday, March 26, price of anarchy for GSP
Notes by Jonathan
DiLorenzo improved in April 14.
Friday, March 28, price of anarchy for
mechanisms based on greedy algorithms
Notes by Theodoros Lykouris
Monday, April 7,
smoothness, and second price item auction with unit demand bidders
Notes by Sam Park
Wednesday, April 9,
second price item auction with fractionally submodular
Notes by Bryce Evans
Friday, April 11,
classes of valuations: submodular, subadditive and fractionally subadditive
Monday, April 14, on
Bandwidth sharing in a single link, and price equilibrium of the fair sharing game.
notes from 2012.
Wednesday, April 16,
price of anarchy analysis for fair sharing on a single link.
Friday, April 18, on
Bandwidth sharing in a network.
Monday, April 21, more
on Bandwidth sharing in a network.
from 2012, and also the paper R. Johari and J.N. Tsitsiklis
loss in a network resource allocation game.
Wednesday, April 23, Walrasian pricing equilibrium.
Friday, April 25, Walrasian pricing equilibrium, and existence of optimal
Nash in the GSP game.
Monday, April 28, Vasilis
Syrgkanis on sequential auction games
See the paper Sequential Auctions and Externalities
Wednesday, April 30,
Arrow-Debreu market equilibrium
Friday, May 2,
Arrow-Debreu market equilibrium cont, and Fischer
from 2012. See also the course on Computation of
equilibria by Amin Saberi
Monday, May 5, revenue
Wednesday, May 7th,
Revenue versus an extra bidder: Bulow Klemperer
from 2012, and the paper by Bulow Klemperer Auctions
See also the
Problem set 1
was due Friday, February 14, it is now graded and solutions and comments are
available on CMS.
Problem set 2
was due Wednesday, March 5, it is now graded and solutions and comments are
available on CMS.
Problem set 3
was due Tuesday, March 24, 2014, it is now
graded and solutions and comments are available on CMS.
Proposal for the final project was
due, Friday March 28.
Problem set 4
was due Monday, April 21st, it is
now graded and solutions and comments are available on CMS.
project is due Wednesday, May 7th. See more details at Course work
home final is available starting May 12th. 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 12-20, but need to be finished by 5pm on Tuesday the 20th. Office hours
during the final week are posted on Piazza.
Other Useful resources:
tex file from Chris Liuís notes
Video of all previous
run of this class are available at www.videonote.com/Cornell
- Algorithmic Game Theory.
eds. Nisan, Roughgarden, Tardos, Vazirani
(username=agt1user, password=camb2agt), Cambridge, 2007.
- M. Osborne, A. Rubinstein, A
course in Game Theory, MIT Press, 1994.
in Economic Design by Jason Hartline
Systems, by Shoham and Leyton-Brown, Cambridge, 2008.
Learning, and Games , by Cesa-Bianchi and Lugosi
Theory of Learning in Games , by Fudenberg and Levine
- For a
nice introduction to Game Theory look at Ken Binmore:
Game Theory: a Very Short Introduction, Oxford University Press.
Rough course outline (subject to change):
to Algorithms and Games:
- Games and examples
- Solution concepts: Nash equilibria, Bayesian Nash, learning
in games and correlated Nash
the Inefficiency of Equilibria:
- Best and worst Nash,
- Quality of learning outcome.
- Strong price of anarchy.
Games we will discuss
- Routing Games and other congestion games: Nash equilibria
- Potential games: Facility Location, Network Design
- Selfish Routing and Wardrop equilibria
- Other Network design games
- Bandwidth sharing Games
- Auction Games: Simultaneous, Sequential and Greedy Auctions,
Generalized Second Prize
- Market games: market clearing prices, and related
- Matching games
- Mechanism Design
second-price auction, Vickrey-Clarke-Groves
Course work consists of 4 homework sets, a final, a final project, and
possibly scribe notes. You may discuss homework questions with other
students, but need to write down the solutions on your own. The final is a
non-cooperative version of the homework. Extra credit will be available for
solving more homework problems than 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
Course grade is determined roughly as
- project proposal 5%
- project 25%
- take home final 30%
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.
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
maturity. An A- or better in CS 4820 is great, or a course at a similar level
in a different department.
Classes on similar topics at other
Earlier version of this course
of Anarchy by Jason Hartline
Design by Jason Hatrline
Algorithmic Game Theory
by Tim Roughgarden
Decision, and Computation by Costis Daskalakis
and Silvio Micali