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, TBD.
Important Links:
- Course Policies: Syllabus
- For communication: Piazza
- For submitting homework: Gradescope
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.
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 | R1.1-2 |
| Sep 8 | Projects, Incentive Compatibility, & The Revelation Principle | R1.3-4, H2.10, Project Description, Project Rubric |
| Sep 10 | Bayesian Settings and Revenue Equivalence | H2.3,2.5,2.7 |
| Sep 15 | Myersonian Virtual Welfare and Quantile Space | R1.5, H3.3-4 |
| Sep 17 | Ironing Virtual Values | H3.3.3-4 |
| Sep 22 | Multidimensional Settings and VCG and Discussion: Project Ideas | R1.7 |
| Sep 24 | Ascending Auctions I | R2.1-2 |
| Sep 29 | Ascending Auctions II & Walrasian Equilibria | R2.2-3,5 |
| Oct 1 | Prophet Inequalities and Balanced Prices | R1.6, KW '12, FGL '15, DFKL '17 |
| Oct 6 | KVV, Prior Independence: Bulow-Klemperer & Single Sample | R1.6, H5.2-3 |
| Oct 8 | Gains from Trade in Two-Sided Markets | BGG '20 |
| Oct 13 | NO CLASS (Monday schedule) | |
| Oct 15 | Discussion: Starting research and making progress | |
| Oct 20 | MD4SG I: Health Insurance Markets | EGW '24, EAAMO |
| Oct 22 | MD4SG II: Kidney Exchange | |
| Oct 27 | MD4SG III: Democracy, Summary of MD4SG Directions | |
| Oct 29 | Interdependent Valuations I | EFFGK '19 |
| Nov 3 | Interdependent Valuations II | EFFGK '19 |
| Nov 5 | Behavioral Economics and Mechanism Design I | Shengwu's Tutorial | Nov 10 | Behavioral Economics II | Shengwu's Talk |
| Nov 10 | Discussion: How to speak and write | |
| Nov 17 | Fair Division | |
| Nov 19 | Machine Learning and Incentives | Chara's Tutorial, Survey on Algorithmic Contract Theory |
| Nov 24 | NO CLASS (Thanksgiving) | |
| Nov 26 | NO CLASS (Thanksgiving) | |
| Dec 1 | Collage of Topics | |
| Dec 3 | Project Presentations | Project Rubric |
| Dec 8 | Project Presentations | |
| Dec 10 | Project Presentations | |
| Final Matrix Exam Date | Project Reports Due Final Matrix Exam Time |
Huge gratitude to Jason Hartline and Tim Roughgarden for their publicly available materials which have made the development of this course possible.