CMSC828M – Spring 2018

Applied Mechanism Design for Social Good

Diversity of ideas image from Grasshopper Herder Lean Startup Blog

Who: John P. Dickerson
When: Tuesday and Thursday, 9:30–10:45 AM
Where: CSI 2120
Office hours: Whenever; email me first at

Download Teaser

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!)


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. 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 14 at 8:00AM). Examples of projects from last year that developed into full papers:

Students will present during the semester (assuming roughly 30–40 students, this should be feasible). Presenting in class is just that—spending 30 or so minutes presenting to the class on the required reading for that day. Some classes will start with John lecturing for 30–45 minutes followed by one student, or will consist of two students lecturing. Students are also welcome to take the entire class, if they'd like. We'll also post the student presentation (either slides or notes) online. You'll be able to select a topic to lecture on, or you can sell me on your own.

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 14 at 8:00AM).

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:!


(Schedule subject to change as the semester progresses!)
# Date Topic Reading Slides Lecturer Notes
1 1/25 Introduction Alvin E. Roth. The economist as engineer: Game theory, experimentation, and computation as tools for design economics. Econometrica, 2002. pdf, pptx Dickerson
2 1/30 Intro to Game Theory Chapters 1 and 2 of Algorithmic Game Theory. pdf, pptx Dickerson
3 2/1 Intro to Mechanism Design Chapters 9 and 10 of Algorithmic Game Theory. pdf, pptx Dickerson Results from game played in class: ; link to corresponding NYTimes survey:
4 2/6 John is at AAAI; lecture might be cancelled ...
5 2/8 Intro to Mechanism Design, Continued pdf, pptx Dickerson
6 2/13 Primer in Combinatorial Optimization Cornuéjols, Trick, and Saltzman. A Tutorial on Integer Programming. 1995. pdf, pptx Dickerson
7 2/15 Primer in Combinatorial Optimization, Continued pdf, pptx Dickerson
8 2/20 Security Games Kiekintveld et al. Computing optimal randomized resource allocations for massive security games. AAMAS, 2009. pdf, pptx Dickerson
9 2/22 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.
pdf1, pptx1, pdf2, pptx2 Suraj Nair, Brook Stacy USC website
10 2/27 Green Security Games, & Stochastic Optimization Primer
  • Yin et al. TRUSTS: Scheduling Randomized Patrols for Fare Inspection in Transit Systems Using Game Theory. AI Magazine, 2013.
  • Powell. Clearing the Jungle of Stochastic Optimization. INFORMS Tutorials in Operations Research, 2014.
pdf1, pdf2, pptx2 Christiana Sabett, Mehdi Dadfarnia
11 3/1 National Residency Matching Program 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 We'll spend time discussing project ideas in class today.
12 3/6 Organ Exchange: Matching Theory
  • Ashlagi and Roth. Free riding and participation in large scale, multi-hospital kidney exchange. Theoretical Economics, 2014.
  • Blum et al. Opting Into Optimal Matchings. SODA, 2017.
pdf, pptx Dickerson
13 3/8 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.
pdf1, pptx1, pdf2, pptx2 Alireza Farhadi, Dickerson
14 3/13 Organ Exchange: Dynamic Optimization Dickerson and Sandholm. FutureMatch: Combining Human Value Judgments and Machine Learning to Match in Dynamic Environments. AAAI, 2015. pdf1, pptx1, pdf2, pptx2 Dickerson, Ashton Webster
15 3/15 Health Care and Wall Street Montazerhodjat, Weinstock, and Lo. Buying cures versus renting health: Financing health care with consumer loans. Science Translational Medicine, 2016. pdf1, pptx1, pdf2, pptx2, Shravan Srinivasan, Ryan Eckenrod
3/20 Spring Break
3/22 Spring Break
16 3/27 Allocation of Food to Food Banks
  • Canice Prendergast. The Allocation of Food to Food Banks. Working paper, 2015.
  • Aleksandrov et al. Online Fair Division: Analyzing a Food Bank Problem. IJCAI, 2015.
  • Kash, Procaccia, Shah. No Agent Left Behind: Dynamic Fair Division of Multiple Resources. JAIR, 2014.
Jacob Rasiel, Kevin Bock Slate article about the Prendergast paper
17 3/29 Combinatorial Assignment Problems
  • 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.
Dickerson, Janit Anjaria Wharton's Course Match website
18 4/3 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.
Sankha Guria, Allen Leis Priceonomics blog post
19 4/5 Fair Division: Theory, & Externalities Chapters 11 and 12 of the Handbook for Computational Social Choice. (password: cam1CSC) Rangfu Hu, Hamed Saleh Mohammadabad TENTATIVE: 24-hour take-home midterm out today
20 4/10 Fair Division: Practice, & Dynamics Kurokawa, Procaccia, and Shah. Leximin Allocations in the Real World. EC, 2015. Leonidas Tsepenekas, Mohammad Ghiasi Spliddit website
21 4/12 Gerrymandering
  • Pegden, Procaccia, & Yu. A Partisan Districting Protocol with Provably Nonpartisan Outcomes. Working paper, 2018.
  • Wang. Three Tests for Practical Evaluation of Partisan Gerrymandering. Stanford Law Review, 2016.
Brian Ondov, Julian Vanecek Washington Post opinion piece: link
22 4/17 Submodular Optimization & Influence Maximization
  • Submodular paper TBD
  • Kempe, Kleinberg, and Tardos. Maximizing the Spread of Influence through a Social Network. KDD, 2003.
Nathaniel Grammel, Hanuma Maddali Submodularity website: link
23 4/19 Selfish Routing & Price of Anarchy Roughgarden and Tardos. How Bad Is Selfish Routing. JACM, 2002. Yogesh Balaji, Dantong Ji TENTATIVE: Course project checkups due
24 4/24 Voting Chapter 2 of the Handbook for Computational Social Choice. (password: cam1CSC) Ivan Petrov, Frank Pike
25 4/26 Prediction Markets & Ethics
  • Chen and Pennock. Designing markets for prediction. AI Magazine, 2010.
  • Dudík et al. A Combinatorial Prediction Market for the U.S. Elections. EC, 2013.
Nicholas Labich, Denis Peskov
26 5/1 School Choice
  • Abdulkadiroğlu and Sönmez. School Choice: A Mechanism Design Approach. American Economic Review, 2003.
  • Pathak and Sönmez. Leveling the playing field: Sincere and sophisticated players in the Boston mechanism. American Economic Review, 2008.
Aya Ismail, Willem Wyndham
27 5/3 Fairness, Accountability, and Transparency in Machine Learning (FATML) Joseph et al. Fairness in Learning: Classic and Contextual Bandits. NIPS, 2016. Nirat Saini, Ben Knisely FATML workshops and resources
28 5/8 Fairness, Accountability, and Transparency in Machine Learning (FATML) TBD Yigitcan Kaya, Michael Curry
29 5/10 Game Theory & Conversation, & Course Wrap-up TBD Samuel Barham, Dickerson
Final 5/14 Final exam 48-hour take-home final must be turned in by this date at 8:00AM