CMSC828M – Fall 2016

Applied Mechanism Design for Social Good

Gears

Who: John P. Dickerson
When: Tuesday and Thursday, 12:30–1:45 PM
Where: CSI 2118
Office hours: Whenever; email me first at john@cs.umd.edu

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 Trump 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! username: agt1user, password: camb2agt)
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!)

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 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-October, 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-November, to ensure progress is being made. A whitepaper—formatted as a conference paper—will be due by the exam date for this course (Monday, December 19 at 1:30PM).

Students will either scribe (twice) or present (once) during the semester (assuming roughly 25 students, this should be feasible). Scribing basically entails fully understanding that lecture's required reading, and writing a short summary of the content and any course discussion. We'll post the scribe notes on this website; a template for the scribe notes can be found here. Presenting in class is just that—spending 30 or so minutes presenting to the class on the required reading for that day. We'll also post the student presentation (either slides or notes) online.

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 late October, 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, December 19 at 1:30PM).

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 8/30 Introduction Alvin E. Roth. The economist as engineer: Game theory, experimentation, and computation as tools for design economics. Econometrica, 2002. pdf, pptx Dickerson
2 9/1 Intro to Game Theory Chapters 1 and 2 of Algorithmic Game Theory. (username: agt1user, password: camb2agt) pdf, pptx Dickerson
3 9/6 Intro to Mechanism Design Chapters 9 and 10 of Algorithmic Game Theory. (username: agt1user, password: camb2agt) pdf, pptx Dickerson
4 9/8 Primer in Combinatorial Optimization Cornuéjols, Trick, and Saltzman. A Tutorial on Integer Programming. 1995. pdf, pptx Dickerson
5 9/13 Selfish Routing Roughgarden and Tardos. How Bad Is Selfish Routing. JACM, 2002. pdf Sushant Patkar
6 9/15 Security Games Kiekintveld et al. Computing optimal randomized resource allocations for massive security games. AAMAS, 2009. pdf1, pptx1, pdf2, pptx2 Dickerson (1/2) & Neal Gupta (1/2) Scribe: Katherine Scola, pdf:
7 9/20 Green Security Games
  • Yin et al. TRUSTS: Scheduling Randomized Patrols for Fare Inspection in Transit Systems Using Game Theory. AI Magazine, 2013.
  • Fang et al. Deploying PAWS: Field Optimization of the Protection Assistant for Wildlife Security. AAAI, 2016.
pdf1, pptx1, pdf2 Kiran Javkar (1/2) & Rock Stevens (1/2)
8 9/22 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; Candice's NRMP lecture will be on 9/27.
9 9/27 Deceased Donor Organ Allocation Bertsimas, Farias, and Trichakis. Fairness, Efficiency, and Flexibility in Organ Allocation for Kidney Transplantation. Operations Research, 2013. pdf1, pptx1, pdf2 Candice Schumann (1/2) & Lida Apergi (1/2) Scribe: Brian Brubach
10 9/29 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. Working paper, 2016.
pdf, pptx Dickerson Scribe: Brian Brubach
11 10/4 Organ Exchange: Batch Optimization Dickerson et al. Position-Indexed Formulations for Kidney Exchange. EC, 2016. pdf, pptx Dickerson Scribe: Michael Saugstad, pdf:
12 10/6 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 Scribe: Michael Saugstad, pdf:
13 10/11 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, key2 Zuxuan Wu (1/2) & Daniel Votipka (1/2)
14 10/13 Guest Lecture Efficient Decision-Making and Learning from Big Ranking Data — Lirong Xia
15 10/18 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.
pdf1, pptx1, pdf2 Dickerson (1/2) & Nidhi Shah (1/2)
16 10/20 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. Working paper, 2016.
pdf1, pptx1, pdf2 Dickerson (1/2) & Konstantinos Xirogiannopoulos (1/2)
17 10/25 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.
pdf1, pptx1, pdf2 Dickerson (1/2) & Faez Ahmed (1/2)
18 10/27 Fair Division: Theory Chapters 11 and 12 of the Handbook for Computational Social Choice. (password: cam1CSC) pdf, pptx Dickerson
  • Scribe: Katura Harvey, pdf:
  • 24-hour take-home midterm out today
19 11/1 Fair Division: Practice Kurokawa, Procaccia, and Shah. Leximin Allocations in the Real World. EC, 2015. pdf Dickerson (1/2) & Hadi Yami (1/2)
20 11/3 Dynamic Matching Market Design John Dickerson gives HCIL BBL Talk — Dickerson Talk is at 12:30 in HCIL (2105 Hornbake, South Wing); talk series website: link
21 11/8 Voting Chapter 2 of the Handbook for Computational Social Choice. (password: cam1CSC) pdf1, pptx1, pdf2, pptx2 Dickerson (1/2) & Roozbeh Yousefzad (1/2)
22 11/10 Social Networks Kempe, Kleinberg, and Tardos. Maximizing the Spread of Influence through a Social Network. KDD, 2003. pdf, pptx Faizan Wajid Submodularity website: link
23 11/15 Project Day! — — — INFORMS
24 11/17 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.
pdf1, pdf2, pptx2 Saba Ahmadi (1/2) & Duncan McElfresh (1/2) Course project checkups due
25 11/22 Prediction Markets & Ethics Chen and Pennock. Designing markets for prediction. AI Magazine, 2010. pdf, pptx Dickerson
– 11/24 Thanksgiving — — —
26 11/29 Fairness, Accountability, and Transparency in Machine Learning Joseph et al. Rawlsian Fairness for Machine Learning. Working paper, 2016. pdf, pptx Dickerson FATML workshop
27 12/1 Student Presentations
28 12/6 Student Presentations NIPS
29 12/8 Student Presentations NIPS
Final 12/19 Final exam 48-hour take-home final must be turned in by this date at 1:30PM

Web Accessibility