Who: John P. Dickerson
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.
|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!)|
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: firstname.lastname@example.org!
|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.||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||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||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||pdf1, pptx1, pdf2||Dickerson (1/2) & Nidhi Shah (1/2)|
|16||10/20||Combinatorial Assignment Problems||
||pdf1, pptx1, pdf2||Dickerson (1/2) & Konstantinos Xirogiannopoulos (1/2)||
|17||10/25||Incentive Auctions & Spectrum Repacking||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||
|19||11/1||Fair Division: Practice||Kurokawa, Procaccia, and Shah. Leximin Allocations in the Real World. EC, 2015.||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|
|24||11/17||School Choice||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|
|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|
|Final||12/19||Final exam||48-hour take-home final must be turned in by this date at 1:30PM|