CMSC828M – Spring 2021

Applied Mechanism Design

Diversity of ideas image from Grasshopper Herder Lean Startup Blog

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.

Get pumped! High-level recommended reading.
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:

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:

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

(Schedule subject to change as the semester progresses!)
# 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 Intro to Mechanism Design Snow Day Chapter 9 of Algorithmic Game Theory. pdf, pptx Dickerson 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
  • Fang et al. When Security Games Go Green: Designing Defender Strategies to Prevent Poaching and Illegal Fishing. IJCAI, 2015.
  • Fang et al. Deploying PAWS: Field Optimization of the Protection Assistant for Wildlife Security. AAAI, 2016.
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
  • Ashlagi and Gonczarowski. Stable matching mechanisms are not obviously strategy-proof. Journal of Economic Theory, 2018.
  • Ashlagi and Roth. Free riding and participation in large scale, multi-hospital kidney exchange. Theoretical Economics, 2014.
pdf, pptx Dickerson
20 4/9 Incentives & Matching II: Organ Exchange
  • Blum et al. Opting Into Optimal Matchings. SODA, 2017.
  • Anderson et al. Finding long chains in kidney exchange using the traveling salesman problem. PNAS, 2015.
  • Dickerson et al. Position-Indexed Formulations for Kidney Exchange. EC, 2016.
pdf, pptx Dickerson
21 4/13 Organ Exchange: Batch Optimization
  • Anderson et al. Finding long chains in kidney exchange using the traveling salesman problem. PNAS, 2015.
  • Dickerson et al. Position-Indexed Formulations for Kidney Exchange. EC, 2016.
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
  • Eric Budish. The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes. Journal of Political Economy, 2011.
  • Budish et al. Course Match: A Large-Scale Implementation of Approximate Competitive Equilibrium from Equal Incomes for Combinatorial Allocation. Operations Research, 2017.
pdf, pptx Dickerson Wharton's Course Match website
24 4/22 Fair Division & Combinatorial Assignment Problems
  • Kash, Procaccia, Shah. No Agent Left Behind: Dynamic Fair Division of Multiple Resources. JAIR, 2014.
  • Chapters 11 and 12 of the Handbook for Computational Social Choice. (password: cam1CSC)
pdf, pptx Dickerson
25 4/27 Fair Division & Combinatorial Assignment Problems
  • Kash, Procaccia, Shah. No Agent Left Behind: Dynamic Fair Division of Multiple Resources. JAIR, 2014.
  • Chapters 11 and 12 of the Handbook for Computational Social Choice. (password: cam1CSC)
pdf, pptx Dickerson
26 4/29 Incentive Auctions & Spectrum Repacking
  • Peter Cramton. Spectrum Auction Design, Review of Industrial Organization, 2013.
  • Fréchette, Newman, & Leyton-Brown. Solving the Station Repacking Problem. AAAI, 2016.
pdf, pptx Dickerson Priceonomics blog post
27 5/4 Differentiable Economics: Deep Learning for Mechanism Design
  • Dütting et al. Optimal Auctions through Deep Learning. ICML, 2019.
  • Amos & Kolter. OptNet: Differentiable Optimization as a Layer in Neural Networks. ICML, 2017.
  • Curry*, Chiang*, et al. Certifying Strategyproof Auction Networks. NeurIPS, 2020.
pdf, pptx Curry Differentiable convex optimization layers: link