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 I: Cake Cutting Discussion: Project Ideas |
Worksheet, Notes, Project Description, Project Rubric |
| Sep 24 | Fair Division II: Indivisible Goods and Rent Division | Worksheet, Notes |
| Sep 29 | Ad Auctions and VCG | Worksheet, Notes, R1.4, R1.7, Edelman, Ostrovsky & Schwarz '07 |
| Oct 1 | Bayesian Settings and Revenue Equivalence | Worksheet, Notes, H2.3, H2.5, H2.7-8, Probability Basics |
| Oct 6 | Optimal Auctions and Myersonian Virtual Welfare | Worksheet, Notes, R1.5, H3.3.1-4, Ironing and Quantiles |
| Oct 8 | NO CLASS—Probability Practice or Quantile Readings | Probability Practice, Probability Solutions, Ironing Guided Reading |
| Oct 13 | NO CLASS (Monday schedule) | |
| Oct 15 | Prophet Inequalities and Posted Prices | Worksheet, Notes, R1.6, H4.2, Balanced Prices |
| Oct 20 | Quiz on HW #1 Guest Lecture by Nathan Klein on Online Algorithms |
|
| Oct 22 | Discussion: Starting research and making progress | Discussion |
| Oct 27 | Prior Independence: Bulow-Klemperer, Quantiles, and Single-Sample Auctions | Worksheet, Notes, R1.6, H3.3.4, H5.2.1, H5.3.1 |
| Oct 29 | MD4SG 1: Health Insurance | Worksheet, Notes, EGW '24, EAAMO |
| Nov 3 | MD4SG 2: Matching and School Choice | R1.10 |
| Nov 5 | MD4SG 3: Voting and Democracy | |
| Nov 10 | Quiz on HW #1 MD4SG 4: Kidney Exchange |
R1.9-10 |
| Nov 12 | Behavioral Mechanism Design | Kleinberg & Oren '14 |
| Nov 17 | Discussion: How to speak and write MD4SG Proposal Sharing |
|
| Nov 19 | Prediction Markets | |
| Nov 24 | NO CLASS (Thanksgiving) | |
| Nov 26 | NO CLASS (Thanksgiving) | |
| Dec 1 | AI Agents and Incentives Course Feedback |
|
| 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.