CS364A: Algorithmic Game Theory (Fall 2013)
Instructor: Tim
Roughgarden (Office hours: Mondays and Wednesdays after class.)
Teaching Assistants:
-
Kostas Kollias
(Office hours: Thursdays 9 AM-Noon, in Gates B24A.
Email: kkollias "at" stanford.edu)
- Okke Schrijvers
(Office hours: Tuesdays 1-4 PM, in Gates 463A.
Email: okkes "at" stanford.edu)
Time/location:
2:15-3:30 PM on Mondays and Wednesdays in Littlefield 103.
Piazza site: here
Course description:
Broad survey of topics at the interface of theoretical computer science
and economics. Introduction to auction and mechanism design,
with an emphasis on computational efficiency and robustness.
Introduction to the "price of anarchy", with applications to networks.
Algorithms and complexity theory for learning and computing Nash and
market equilibria.
Case studies
in Web search auctions, wireless spectrum auctions, matching markets,
network routing, and security applications.
Prerequisites: basic algorithms and complexity (154N and 161, or equivalent). No prior knowledge of economics or game theory is required.
Course requirements:
All students are required to complete weekly exercise sets, which fill
in details from lecture.
Students taking the course for a letter grade are also required to
complete biweekly problem sets, which supplement the material covered
in lecture.
Students are encouraged to form groups (up to three students) to
complete the problem sets.
There will also be occasional extra credit problems and opportunities.
No late assignments accepted.
All lecture notes and exercise sets in one PDF.
Lecture videos and notes (beta versions)
Exercise and problem sets:
Primary references:
- Nisan/Roughgarden/Tardos/Vazirani (eds),
Algorithmic Game Theory,
Cambridge University, 2007.
- Also available free on the Web, see here.
- To get a sense for the course in a nutshell:
- For the first four weeks, most of what we cover is also covered in Hartline's book draft.
(Feedback is solicited here.)
- Another excellent textbook that covers several of the
course's topics is Shoham and Leyton-Brown, Multiagent
Systems, Cambridge, 2008.
Detailed schedule and references:
- Lecture 1 (Mon 9/23): Introduction.
The 2012 Olympic badminton scandal.
Selfish routing and Braess's Paradox.
Can strategic players learn a Nash equilibrium?
Readings:
- J. Hartline and R. Kleinberg,
Badminton and the Science of Rule Making, Huffington Post, 2012.
- Video of the
first controversial badminton match.
- Braess's Paradox: Chapter 1 of T. Roughgarden,
Selfish Routing and the Price of Anarchy (MIT Press, 2005),
available here
via the "Sample Chapter" link.
- Physical demonstrations of Braess's Paradox, by alumni of CS364A:
#1
#2
#3
- Basic games and equilibrium notions: AGT book, Sections 1.1.1--1.3.4.
- Lecture 2 (Wed 9/25):
Mechanism design basics.
How would you bid in a first-price auction?
The Vickrey auction and dominant-strategy implementations.
Case study: sponsored search auctions.
Readings:
- The Vickrey auction: AGT book, Section 9.3.1, 9.3.2, and 9.3.5;
and/or Section 1 or these old CS364B notes.
- Pages 1-8 of Hartline's book.
- Optional sponsored search readings: AGT book, Sections 28.1-28.3.1.
See also this CS364B course for
tons of subtopics and references on sponsored search auctions (circa
late 2007).
- Lecture 3 (Mon 9/30): Characterization of single-parameter DSIC
mechanisms (Myerson's Lemma).
Readings:
- AGT book, Sections 9.4.1--9.4.2 and 9.5.4--9.5.6. Optionally, see also Section 4
in this FOCS '01 paper by Archer and Tardos.
- Sections 2.6 and 3.1 of Hartline's book.
- Lecture 4 (Wed 10/2): DSIC sponsored search auctions.
Knapsack auctions and algorithmic mechanism design.
Revelation Principle.
Readings:
- Lecture 5 (Mon 10/7):
The challenge of revenue maximization. Bayesian optimal auctions.
Readings:
- Lecture 6 (Wed 10/9):
The Prophet Inequality. Simple near-optimal auctions.
Prior-independent auctions and the Bulow-Klemperer theorem.
Readings:
- Lecture 7 (Mon 10/14):
Case study: reserve prices in Yahoo! keyword auctions.
Multi-parameter mechanism design and the VCG mechanism.
Introduction to combinatorial auctions.
Readings:
- Lecture 8 (Wed 10/16):
Case study: wireless spectrum auctions. Readings:
- Cramton/Shoham/Steinberg (eds.), Combinatorial Auctions,
MIT Press, 2006.
- Chapter 4 (Cramton) covers simultaneous ascending auctions.
- Chapter 5 (Ausubel/Cramton/Milgrom) discusses how to add a final
"proxy" round with package bidding.
- Milgrom, Chapter 1 of Putting Auction Theory to Work, Cambridge, 2004.
- Goeree/Holt, Hierarchical Package Bidding, about bidding only on predefined packages.
- Milgrom/Segal, Deferred-Acceptance Heuristic Auctions, 2013.
Describes the proposed format for the reverse auction in the upcoming FCC double auction.
- Lecture 9 (Mon 10/21):
Beyond quasi-linearity. The clinching auction for bidders with
budgets. The top trading cycle algorithm for housing allocation.
- Lecture 10 (Wed 10/23):
Case study: kidney exchange. Stable matching.
- Lecture 11 (Mon 10/28):
Nonatomic selfish routing and the price of anarchy: examples, preliminaries,
and tight bounds for all classes of cost functions.
Readings:
- Lecture 12 (Wed 10/30):
Case study: network over-provisioning. A bicriteria bound
for nonatomic routing networks. POA bounds for atomic routing networks.
Readings:
- AGT book, Sections 18.3.2, 18.4.2, and 18.5.2.
- Lecture 13 (Mon 11/4):
Potential functions and the existence of pure Nash equilibria.
A hierarchy of equilibrium concepts: mixed-strategy Nash, correlated, and coarse correalted equilibria.
Readings:
- Lecture 14 (Wed 11/6): Vetta's location games.
Smooth games. POA bounds for coarse correlated equilibria and approximate Nash equilibria.
- Lecture 15 (Mon 11/11):
Positive externalities and network cost-sharing games.
The price of stability. Strong Nash equilibria and their inefficiency.
- Lecture 16 (Wed 11/13):
Best-response dynamics in potential games. Fast convergence to
approximate Nash equilibria in symmetric routing games.
Fast convergence to near-optimal solutions in smooth potential games.
- Lecture 17 (Mon 11/18):
Regret minimization. The multiplicative weights (or randomized weighted
majority) algorithm. Connection to learning coarse correlated equilbria.
- Lecture 18 (Wed 11/20):
Black-box reduction from swap regret minimization to external
regret minimization. Connection to learning correlated equilbria.
The minimax theorem for two-player zero sum games.
- AGT book, Sections 4.4-4.5.
- Lecture 19 (Mon 12/2):
PLS-completeness and negative convergence results for pure Nash equilibria in routing and congestion games. Primary reference:
Further good surveys:
- Lec 20 (Wed 12/4):
PPAD-completeness of computing mixed-strategy Nash equilibria of
bimatrix games. Primary references: