How do we allocate food to food banks, children to schools, organs to patients, residents to hospitals, security forces to patrol routes, and credit to multiple authors of an open source project—all in the face of competing incentives affecting selfish participants? Can we fairly divide a house, furniture, cars, and the family dog between a divorcing couple? Is Kanye going to be our next president, and—if so—why? Can we design mechanisms for these problems that perform well in practice, are computationally tractable, and whose workings and results are understandable by humans?
Who: John P. Dickerson and Marina Knittel
This course will consist primarily of reading and discussing recent papers from folks in computer science, economics, operations research, operations management, and medicine; as such, there is no assigned textbook. Some recommended high-level or reference readings follow.
Title | Author(s) | Why? | Link |
---|---|---|---|
Algorithmic Game Theory | Nisan, Roughgarden, Tardos, & Vazirani | Very readable introduction to, and reference book for, game theory and mechanism design. | (It's free!) |
Who Gets What — and Why: The New Economics of Matchmaking and Market Design | Al Roth | Pop-sci coverage of fielded matching markets like NRMP, school choice, and kidney exchange, from somebody who won a Nobel Prize for his part in their design. | (Amazon) |
Handbook of Computational Social Choice | Brandt, Conitzer, Enriss, Lang, & Procaccia | Good and very recent overview of recent theory and practice in social choice. | (It's free! password: cam1CSC) |
Combinatorial Auctions | Cramton, Shoham, & Steinberg | Fairly recent and very readable overview of modern approaches to auction design. | (It's free!) |
The Ethical Algorithm | Kearns & Roth | Recent and very readable overview of privacy, bias, fairness, and other societal concerns in algorithm design. | (Oxford University Press) |
Lectures on Economics, AI, and Optimization | Kroer | Optimization-focused approach to problems in game theory and mechanism design. | (Lecture notes!) |
A Modern Introduction to Online Learning | Orabona | Very recent tutorial on online learning & convex optimization. | (It's free!) |
Students enrolled in the course will complete a semester-long course project on something related to market and mechanism design. This project can be done individually or—preferably—in a small group, and can be entirely theoretical, entirely applied, or anything in between. The goal here is to create something that is either immediately publishable or will lead to a publishable piece of work in the future. Project proposals will be due in mid-March, with two classes at the end of the semester set aside for individual and group presentations. There will also be a brief (2-page) "project check-up" document due in mid-April, to ensure progress is being made. A whitepaper—formatted as a conference paper—will be due by the exam date for this course (Monday, May 16, 2022 at 1:30PM). Examples of projects from recent years that developed into full papers:
In addition to the course project, students will write two short blog posts and/or give two short, pre-recorded video presentations covering some research topic relevant to the class—a paper, papers, book chapter, recent event, topic of interest, and so on. This can be written using Google Docs/Word/Medium/etc, and/or recorded via Zoom or another, similar piece of software. Unless the student objects, we'll post this publicly on the course website. You're very welcome to instead write a publicly-available summary of a paper as a blog post—I know not everyone wants a public video record. Still, push yourself! There's value in having a public presentation online that you can send to folks.) Students are welcome to choose their own adventure here, but John is also happy to help with topic selection; also, students are welcome—even encouraged!—to present on a topic related to their course project. Here are some example blog-post-style writeups that cover academic papers in the mechanism design space: GAIW write-ups, e.g., Example 1 and Example 2.
We expect final grades to be calculated as follows, although this may change as the semester progress (any updates to grading procedure will be addressed in class and updated here appropriately):
This course is aimed at strong B.Sc. students with a reasonable degree of mathematical maturity and an interest in applied mechanism design. No background in economics is expected. If in doubt, e-mail me: johnd@umd.edu!
# | Date | Topic | Reading | Slides | Lecturer | Notes |
---|---|---|---|---|---|---|
1 | 1/24 | Introduction | Alvin E. Roth. The economist as engineer: Game theory, experimentation, and computation as tools for design economics. Econometrica, 2002. (Section 1, or more if you'd like!) | pdf, pptx | Dickerson | THIS LECTURE WILL BE VIRTUAL |
Part I: The Basics of Game Theory and Mechanism Design | ||||||
2 | 1/26 | Intro to Game Theory | Chapters 1 and 2 of Algorithmic Game Theory. | pdf, pptx | Dickerson | In-person lecture (& recorded/on ELMS) |
3 | 1/31 | Intro to Game Theory, Continued | Chapter 3 of Algorithmic Game Theory. | pdf, pptx | Dickerson | Seinfeld RPS Colab: link |
4 | 2/2 | Intro to Game Theory, Continued | — | pdf, pptx | Dickerson | Integer game from lecture: .xlsx |
5 | 2/7 | Primer in Combinatorial Optimization | Chapters 5 and 6 of Luca Trevisan's "Combinatorial Optimization: Exact and Approximate Algorithms" ; and, Cornuéjols, Trick, and Saltzman. A Tutorial on Integer Programming. 1995. | pdf, pptx | Dickerson | |
6 | 2/9 | Primer in Combinatorial Optimization, Continued | — | pdf, pptx | Dickerson | |
7 | 2/14 | Stable Matching | — | pdf, pptx | Knittel | |
8 | 2/16 | Stable Matching, Continued | — | pdf, pptx | Knittel | |
9 | 2/21 | Application: Faculty Hiring | The Affiliate Matching Problem | pdf, pptx | Knittel | |
10 | 2/23 | Intro to Mechanism Design | Chapter 9 of Algorithmic Game Theory. | pdf, pptx | Dickerson | |
11 | 2/28 | Intro to Mechanism Design, Continued | Chapter 2 of the Handbook for Computational Social Choice. (password: cam1CSC) | pdf, pptx | Dickerson | THIS LECTURE WILL BE PRE-RECORDED & VIRTUAL (NOT LIVE); Lectures posted in the Zoom directory on ELMS |
12 | 3/2 | Intro to Mechanism Design, Continued | — | pdf, pptx | Dickerson | THIS LECTURE WILL BE PRE-RECORDED & VIRTUAL (NOT LIVE); Lectures posted in the Zoom directory on ELMS |
13 | 3/7 | Intro to Mechanism Design, Continued | Roger Myerson. Optimal Auction Design. Mathematics of Operations Research, 1981. | pdf, pptx | Dickerson | |
14 | 3/9 | Intro to Mechanism Design, Continued | — | pdf, pptx | Dickerson | |
15 | 3/14 | Security Games | Kiekintveld et al. Computing optimal randomized resource allocations for massive security games. AAMAS, 2009. | pdf, pptx | Dickerson | Happy Pi Day! |
16 | 3/16 | Fair Allocations | Brams and Taylor. An Envy-Free Cake Division Protocol. The American Mathematical Monthly, 1995. | pdf, pptx | Knittel | First paper presentation due! |
3/18 | — | Project proposal due | ||||
3/21 | SPRING BREAK | — | — | — | ||
3/23 | SPRING BREAK | — | — | — | ||
17 | 3/28 | Fair Allocation, Continued | — | pdf, pptx | Knittel | |
18 | 3/30 | Fair Allocation, Continued | — | pdf, pptx | Knittel | |
19 | 4/4 | Stochastic Games & Primer on Markov Decision Processes (MDPs) | — | pdf, pptx | Dickerson | |
20 | 4/6 | Stochastic Games & Primer on Markov Decision Processes (MDPs), Continued | — | pdf, pptx | Dickerson | |
21 | 4/11 | Stochastic Games & Primer on Markov Decision Processes (MDPs), Continued | — | pdf, pptx | Dickerson | |
22 | 4/13 | Fairness in Machine Learning | Dwork et al. Fairness Through Awareness. Innovations in Theoretical Computer Science, 2012. ; Barocas, Hardt, and Narayanan. Fairness and Machine Learning. ; and, Barocas & Selbst. Big Data's Disparate Impact. | pdf, pptx | Knittel | |
23 | 4/18 | Fair Clustering | — | pdf, pptx | Knittel | Fair clustering tutorial: fairclustering.com |
24 | 4/20 | Fair Clustering, Continued | — | pdf, pptx | Knittel | |
25 | 4/25 | Single-Agent Mechanism Design | — | pdf, pptx | Guest Speaker: Michael Curry | Project checkup due |
26 | 4/27 | Single-Agent Mechanism Design, Continued | — | pdf, pptx | Guest Speaker: Michael Curry | |
27 | 5/2 | Fair Dataset Design | — | Schumann et al. A Step Toward More Inclusive People Annotations for Fairness, AIES, 2021. | Guest Speaker: Candice Schumann | Second paper presentation due |
28 | 5/4 | Project & Team Day | Please spend this time explicitly meeting with your project group, and feel free to reach out to the instructors | You, but virtually! | Marina and I will be available to discuss your projects, or we can chat asynchronously | |
29 | 5/9 | Final Project Presentations | — | You (either in person or virtual)! | Final project summary |