Course Details
Instructor: Professor Kira Goldner (goldner@).
Office Hours: Tuesday 5–6pm and by appointment.
Office Location: 111 Cummington Mall, 138P.
Teaching Fellow: Peiran Xiao (pxiao@).
Office Hours: Wednesday 2:30–3:30pm and by appointment.
OH Location: 111 Cummington Mall, 141.
Lectures:
Tuesday/Thursday 3:30—4:45pm, CAS 426.
Important Links:
- Course Policies: Syllabus
- For communication: Piazza access code AMD
- For submitting homework: Gradescope course entry code DJP34R
Course Description: This course is an introduction to the interdisciplinary area of Algorithmic Mechanism Design: 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.
The course is aimed at graduate students but will be accessible to motivated advanced undergraduate or masters students with some background in proofs (DS 122), algorithms (DS 320), and probability (MA 581).
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.
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 6 | Overview and Policies, Intro to AGT | Slides, Worksheet, Notes, R1.1-2 |
| Sep 8 | Incentive Compatibility | Worksheet, Notes, R1.3 |
| Sep 13 | The Revelation Principle | Worksheet, Notes, R1.4, H2 |
| Sep 15 | Myersonian Virtual Welfare | Worksheet, Notes, R1.5, H3.3 |
| Sep 20 | Ironing Virtual Values and Quantile Space | Worksheet, Notes, H3.3.3-4 |
| Sep 22 | Ironing Intuition, Multidimensional Settings and VCG | Worksheet, Notes, R1.7 |
| Sep 27 | Ascending Auctions I | Worksheet, Notes, R2.1-2 |
| Sep 29 | Ascending Auctions II & Walrasian Equilibria | Worksheet, Notes, R2.2-3,5 |
| Oct 4 | LP Duality I: Primals, Duals, Weak Duality | Worksheet, Notes |
| Oct 6 | Recap and Big Picture | Slides (pptx), Slides (pdf) |
| Oct 11 | NO CLASS (Monday schedule) | |
| Oct 13 | LP Duality II: Strong Duality, Complementary Slackness, Welfare | Worksheet, Notes |
| Oct 18 | LP Duality III: Lagrangian Duality | Worksheet, Notes, CDW STOC '16 |
| Oct 20 | LP Duality IV: Algorithmic Rev Max (Matt Weinberg) | CDW FOCS '12 |
| Oct 25 | LP Duality V: Approximate Revenue Maximization | Worksheet, Notes, CDW STOC '16 |
| Oct 27 | Projects & Prophet Inequalities | Worksheet, Notes, Projects, R1.6 | Nov 1 | Prior Independence: Bulow-Klemperer & Single Sample | Worksheet, Notes, R1.6, H5.2-3 |
| Nov 3 | Gains from Trade in Two-Sided Markets | Worksheet, Notes, BGG '20 |
| Nov 8 | Mechanism Design for Social Good: Health Insurance Markets | Worksheet, Notes, EGW '20 |
| Nov 10 | Mechanism Design for Social Good: Kidney Exchange (class canceled) | R1.10 Video, R1.10 Notes, Al Roth's talk |
| Nov 15 | Mechanism Design for Social Good: COVID Testing and the Research-to-Practice Pipeline (Francisco J. Marmolejo Cossío) | LMCJRGGBVTAL '21, LMCMP '22 |
| Nov 17 | Interdependent Values I | Worksheet, Notes |
| Nov 22 | Interdependent Values II | Notes |
| Nov 24 | NO CLASS (Thanksgiving) | |
| Nov 29 | Selling Separately or Bundling | Worksheet, Notes, R2.18, BILW '14, CDW '16 |
| Dec 1 | Carbon Auctions | |
| Dec 6 | Project Presentations | |
| Dec 8 | Project Presentations |
Huge gratitude to Jason Hartline and Tim Roughgarden for their publicly available materials which have made the development of this course possible.