NETS 412: Algorithmic Game Theory
University of Pennsylvania
Instructor: Bo Waggoner
TAs: Zach Schutzman, Hadi Elzayn, Omar Paladines, Akilesh Tangella, and Ian Masters.
Time: Tuesday/Thursday 3:00-4:30
Room: Moore 216
April 8: hw6 posted, due in two weeks.
April 2: The final exam is May 4, noon - 2pm.
Course syllabus (pdf)
Game theory is the study of systems of agents, each of which acts toward its own goals and is impacted by the decisions of the others.
In this course, we will study game theory and related problems from an algorithmic perspective.
We will consider questions such as: how should an auction for scarce goods
be structured if the seller wishes to maximize his revenue? How badly
will traffic be snarled if drivers each selfishly try to minimize their
commute time, compared to if a benevolent dictator directed traffic?
How can couples be paired so that no two couples wish to swap partners
in hindsight? How can we find kidney-exchange cycles to incentivize people to participate in the exchange, without using money? How can you be as successful at betting on horse races as
the best horse racing expert, without knowing anything about horse
This course will be theoretical and mathematical rigorous.
Ideally (though not mandatory), students will have taken, or be taking concurrently, a course on algorithms (such as CIS 320) and will be familiar with big-O notation.
"Mathematical maturity" and experience with proofs will be very helpful.
Experience with game theory is not assumed.
Goals and Grading:
The goal of this course is to give students a rigorous introduction to game theory
from a computer science perspective, and to prepare students to think
about economic and algorithmic interactions from the perspective of
incentives. Grading will be based on participation, problem sets, a
midterm, and a final exam.
Resources and Links:
- Piazza will be used to discuss class material and ask and answer questions. Please ask all material-related questions on Piazza so everyone can benefit from and contribute to the answers and discussion.
- Gradescope will be used to submit homeworks and receive grades. Entry code: MBPRR4
- Optional, supplementary textbooks: Twenty Lectures in Algorithmic Game Theory by Tim Roughgarden; the Algorithmic Game Theory book edited by Nisan, Roughgarden, Tardos, and Vazirani, which can be found online; and much of Multiagent Systems by Shoham and Leyton-Brown, available here (pdf).
Calendar for office hours.
If you cannot make office hours, please email the instructor, or ask a question on Piazza.
Homeworks, exams, and practice:
LaTeX Submission template with some helpful basics (optional).
Lectures and notes:
- Thursday, Jan. 11 (no class): intro video (8min), readings Foreword, Ch 1.1 of the Algorithmic Game Theory book edited by Nisan, Roughgarden, Tardos, and Vazirani.
- Tuesday, Jan. 16: Lecture 01: Basic Definitions.
- Thursday, Jan. 18: Lecture 02: Congestion Games.
- Tuesday, Jan. 23: Lecture 03: Best-Response Dynamics.
- Thursday, Jan. 25: Lecture 04: Learning from Expert Advice.
- Tuesday, Jan. 30: Lecture 05: The Polynomial Weights Algorithm.
- Thursday, Feb. 1: Lecture 06: Zero-Sum Games.
- Tuesday, Feb. 6: Lecture 07: Some Zero-Sum Games on Graphs.
- Tuesday, Feb. 13: Lecture 08: Correlated Equilibria.
- Thursday, Feb. 15: Lecture 09: No Regret and Correlated Equilibria.
- Tuesday, Feb. 20: Lecture 10: Pareto-Optimal Exchange.
- Thursday, Feb. 22: Lecture 11: Stable Matchings.
- Tuesday, Mar. 13: Recap of course outline and previous two lectures.
- Thursday, Mar. 15: Lecture 12: Voting and Social Choice.
- Tuesday, Mar. 20: Finishing voting and intro to proper scoring rules.
- Thursday, Mar. 22: Lecture 13: Proper Scoring Rules and Prediction.
- Tuesday, Mar. 27: Lecture 14: Information Elicitation without verification.
- Thursday, Mar. 29: Finishing peer prediction and intro to prediction markets.
- Tuesday, Apr. 3: Lecture 15: Prediction Markets. See also evaluating ESPN's ncaa m bball prediction alg.
- Thursday, Apr. 5: Lecture 16: Price of Anarchy and Stability.
- Tuesday, Apr. 10: Lecture 17: Auction Design.
- Thursday, Apr. 12: Lecture 18: VCG.
- Tuesday, Apr. 17: Lecture 19: Lecture 19: Truthfulness, Single-Parameter Domains..
- Thursday, Apr. 19: Lecture 20: PoA of First-Price Auction.
Previous version of course