Course Details
Instructor: Professor Kira Goldner (goldner@).
Office Hours: Tuesday 3:15–4:15pm and by appointment.
Office Location: CCDS 1339.
Lectures:
Tuesday/Thursday 2:00—3:15pm, SAR 102.
Important Links:
- Course Policies: Syllabus
- For communication: Piazza Piazza access code AGT
- For submitting homework: Gradescope Gradescope course entry code 2EK2BW
Course Description: This course is an introduction to the interdisciplinary area of Algorithmic Game Theory: where computational perspectives are applied to economic problems, and economic techniques are brought to problems from computer science. We will explore a broad range of topics at the frontier of new research, starting with some of the fundamentals, such as welfare-maximizing auctions and types of Nash Equilibria. Throughout the semester, the class will also learn about prevalent topics such as (1) Data Science & Incentives, (2) Mechanism Design for Social Good, and (3) optimization and robustness in mechanism design. As part of this course, students will engage in a (guided) research project, experiencing the various parts of conducting original research.
This course is designed as an introductory graduate-level course but is open to motivated advanced undergraduates; please email me for permission. While the formal undergraduate prerequisites are DS 120, DS 121, and DS122 and DS 320 (or equivalent), the course assumes strong proficiency in these topics. Students should have:
- Mathematical maturity and comfort with formal proofs
- A solid understanding of probability (discrete and continuous random variables, moments, and conditional probability)
- Familiarity with algorithms and computational efficiency.
For more details on individual lectures, see previous iterations of the course here, such as the last iteration here.
Homework: Biweekly homeworks will be posted on Piazza when they become available. Homework must be typed up using LaTeX; here is a quick resource on LaTeX and here is a LaTeX template you may use for the homework. Here is another short guide to LaTeX. You may find it easier to use Overleaf.
Tentative Lecture Schedule
Below is a table with that will reflect what we cover in each lecture and will point to corresponding reading material. Lectures listed more than one date in advance are tentative topics. There is no required textbook for this course, as all materials are available online for free and we will switch between materials. Some shorthand for the reading material:
- R1.x = Tim Roughgarden's AGT lecture notes, lecture x. (Alternatively available in book form here.)
- R2.x = Tim Roughgarden's AMD lecture notes, lecture x.
- Hx = Jason Hartline's textbook "Mechanism Design and Approximation," chapter x.
- Kx = Anna Karlin's textbook "Game Theory, Alive," chapter x. (Also in book form.)
| Date | Topic | Resources |
|---|---|---|
| Sep 3 | Overview and Policies, Intro to AGT | Worksheet, Notes, Slides, R1.1-2 |
| Sep 8 | Nash Equilibrium and Mixed Strategies | Worksheet, Notes, Project Description, Project Rubric |
| Sep 10 | Incentive Compatibility and the Revelation Principle | Worksheet, Notes, R1.3-4, H2.6, H2.10 |
| Sep 15 | Congestion Games and the Price of Anarchy | Worksheet, Notes, R1.1, R1.11 |
| Sep 17 | Repeated Games and Cooperation | Worksheet, Notes, K6 |
| Sep 22 | Fair Division Discussion: Project Ideas |
Project Description, Project Rubric |
| Sep 24 | Algorithmic Pricing and Collusion | |
| Sep 29 | Ad Auctions: VCG and Generalized Second Price | R1.4, R1.7, Edelman, Ostrovsky & Schwarz '07 |
| Oct 1 | Bayesian Settings and Revenue Equivalence | H2.3, H2.5, H2.7-8 |
| Oct 6 | Optimal Auctions and Myersonian Virtual Welfare | R1.5, H3.3.1-4 |
| Oct 8 | Prophet Inequalities and Posted Prices | R1.6, H4.2 |
| Oct 13 | NO CLASS (Monday schedule) | |
| Oct 15 | Mechanism Design for Social Good 1: Health Insurance Discussion: Starting research and making progress |
EGW '24, EAAMO |
| Oct 20 | Prior Independence: Bulow-Klemperer and Single-Sample Auctions | H5.2-3 |
| Oct 22 | MD4SG 2: Matching and School Choice | R1.10 |
| Oct 27 | MD4SG 3: Kidney Exchange | R1.9-10 |
| Oct 29 | MD4SG 4: Voting and Democracy | |
| Nov 3 | Rent Division and Envy-Freeness | |
| Nov 5 | Behavioral Mechanism Design: Present Bias and Obvious Strategyproofness | Kleinberg & Oren '14, Li: Obviously Strategy-Proof Mechanisms |
| Nov 10 | Prediction Markets and Proper Scoring Rules | |
| Nov 12 | Information Theory and Incentives Discussion: How to speak and write |
|
| Nov 17 | Peer Prediction | |
| Nov 19 | AI Agents and Incentives | |
| Nov 24 | NO CLASS (Thanksgiving) | |
| Nov 26 | NO CLASS (Thanksgiving) | |
| Dec 1 | Tournament Design and Coalition Resistance | |
| Dec 3 | Project Presentations | Project Rubric |
| Dec 8 | Project Presentations | |
| Dec 10 | Project Presentations | |
| Dec 15 | Project Reports Due 3pm |
Huge gratitude to Jason Hartline and Tim Roughgarden for their publicly available materials which have made the development of this course possible.