CMSC828M – Spring 2021
Applied Mechanism Design
Who: John P. Dickerson
When: Tuesday and Thursday, 2:00–3:15 PM
Where: Zoom (link available on ELMS) & Slack (join link on ELMS)
Office hours: Whenever; email me first at john@cs.umd.edu
Description of Course
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 Oprah 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?
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!) |
Requirements
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 early March, with two classes at the end of the semester set aside for individual and group presentations, if the class is small enough to accommodate that. There will also be a brief (2-page) "project check-up" document due in early 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 17 at 10:30AM). Examples of projects from recent years that developed into full papers:
- Faez Ahmed, John P Dickerson, and Mark Fuge. "Diverse Weighted Bipartite b-Matching." IJCAI-2017. (arXiv)
- Zhoushu Li, Neal Gupta, Sanmay Das, and John P Dickerson. "Equilibrium Behavior in Competing Dynamic Matching Markets." IJCAI-2018.
- Duncan McElfresh and John P Dickerson. "Balancing Lexicographic Fairness and a Utilitarian Objective with Application to Kidney Exchange." AAAI-2018. (arXiv)
- Elissa M Redmiles, Michelle L Mazurek, John P Dickerson. "Dancing Pigs or Externalities? Measuring the Rationality of Security Decisions." EC-2018.
- Candice Schumann, Samsara N Counts, Jeffrey Foster, and John P Dickerson. "The Diverse Cohort Selection Problem: Multi-Armed Bandits with Varied Pulls." AAMAS-19. (arXiv)
- Candice Schumann, Zhi Lang, Jeffrey Foster, and John P Dickerson. "Making the Cut: A Bandit-based Approach to Tiered Interviewing." NeurIPS-19. (arXiv)
ADDITIONAL COURSE REQS
In addition to the course project, students will give a short, pre-recorded video presentation covering some research topic relevant to the class—a paper, papers, book chapter, recent event, topic of interest, and so on. This can be recorded via Zoom or another, similar piece of software; and, unless the student objects, we'll post this publicly on the course website. (Or, if you chat with me, you're welcome to instead write a publicly-available summary of a paper. 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.
Finally, many students expressed interest in this course counting toward MS/PhD qualifiers; with that in mind, students enrolled in the course will have a 24-hour take-home midterm and a 48-hour take-home final; the former will occur sometime in early April, and the latter will be taken at the student's discretion at any time after the final lecture and before (48 hours before) the exam date for this course (Monday, May 17 at 10:30AM).
Final grades will be calculated as:
- 5% course project proposal
- 5% course project checkup
- 45% course project writeup
- 15% presenting/summarizing a paper
- 30% examinations (student-favoring split of either 10% midterm/20% final or 15% midterm/15% final).
This course is aimed at Ph.D. students, but should be accessible to M.Sc. and B.Sc. students with some degree of mathematical maturity and an interest in applied mechanism design. If in doubt, e-mail me: john@cs.umd.edu!
Schedule
| # | Date | Topic | Reading | Slides | Lecturer | Notes |
|---|---|---|---|---|---|---|
| 1 | 1/26 | Introduction | Alvin E. Roth. The economist as engineer: Game theory, experimentation, and computation as tools for design economics. Econometrica, 2002. | pdf, pptx | Dickerson | |
| Part I: The Basics of Game Theory and Mechanism Design | ||||||
| 2 | 1/28 | Intro to Game Theory | Chapters 1 and 2 of Algorithmic Game Theory. | pdf, pptx | Dickerson | |
| 3 | 2/2 | Intro to Game Theory, Continued | Chapter 3 of Algorithmic Game Theory. | pdf, pptx | Dickerson | |
| 4 | 2/4 | Intro to Game Theory, Continued | — | pdf, pptx | Dickerson | |
| 5 | 2/9 | Intro to Game Theory, Continued | — | pdf, pptx | Dickerson | Results from game played in class: ; link to corresponding NYTimes survey: |
| 6 | 2/11 | 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 | |
| 7 | 2/16 | Primer in Combinatorial Optimization, Continued | 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 | Updated results from game played in class: ; start at 2:15PM ET today due to Kira Goldner's job talk |
| 8 | 2/18 | Snow Day | ||||
| 9 | 2/23 | Intro to Mechanism Design | Chapter 9 of Algorithmic Game Theory. | pdf, pptx | Dickerson | |
| 10 | 2/25 | Intro to Mechanism Design, Continued | Chapter 10 of Algorithmic Game Theory. | pdf, pptx | Dickerson | |
| 11 | 3/2 | Intro to Mechanism Design, Continued | pdf, pptx | Dickerson | ||
| 12 | 3/4 | Security Games | Kiekintveld et al. Computing optimal randomized resource allocations for massive security games. AAMAS, 2009. | pdf, pptx | Dickerson | |
| 13 | 3/9 | Green Security Games | pdf, pptx | Dickerson | Fei Fang's website | |
| 14 | 3/11 | Dickerson | ||||
| – | 3/12 | Project proposals due! | Submit a .pdf file on Slack by making a channel with all group members and John, then @ John. | You! | ||
| – | 3/16 | Spring Break | — | — | — | |
| – | 3/18 | Spring Break | — | — | — | |
| 15 | 3/23 | Stochastic Games & Primer on Markov Decision Processes (MDPs) | — | pdf, pptx | Dickerson | |
| 16 | 3/25 | Stochastic Games & Primer on Markov Decision Processes (MDPs) | — | pdf, pptx | Dickerson | |
| 17 | 3/30 | Stable Matching I | Roth and Peranson. The Redesign of the Matching Market for American Physicians: Some Engineering Aspects of Economic Design. American Economic Review, 1999. | pdf, pptx | Dickerson | |
| 18 | 4/1 | Stable Matching II & National Residency Matching Program | Bertsimas, Farias, and Trichakis. Fairness, Efficiency, and Flexibility in Organ Allocation for Kidney Transplantation. Operations Research, 2013. | pdf, pptx | Dickerson | |
| 19 | 4/6 | Incentives & Matching I | pdf, pptx | Dickerson | ||
| 20 | 4/9 | Incentives & Matching II: Organ Exchange | pdf, pptx | Dickerson | ||
| 21 | 4/13 | Organ Exchange: Batch Optimization | pdf, pptx | Dickerson | ||
| 22 | 4/15 | Organ Exchange: Dynamic Optimization | Dickerson and Sandholm. FutureMatch: Combining Human Value Judgments and Machine Learning to Match in Dynamic Environments. AAAI, 2015. | pdf, pptx | Dickerson | Asynchronous recording |
| 23 | 4/20 | Fair Division |
|
pdf, pptx | Dickerson | Wharton's Course Match website |
| 24 | 4/22 | Fair Division & Combinatorial Assignment Problems | pdf, pptx | Dickerson | ||
| 25 | 4/27 | Fair Division & Combinatorial Assignment Problems | pdf, pptx | Dickerson | ||
| 26 | 4/29 | Incentive Auctions & Spectrum Repacking | pdf, pptx | Dickerson | Priceonomics blog post | |
| 27 | 5/4 | Differentiable Economics: Deep Learning for Mechanism Design | pdf, pptx | Curry | Differentiable convex optimization layers: link | |
