CMSC498T – Spring 2022

Mechanism Design

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 Kanye 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?

Who: John P. Dickerson and Marina Knittel
When: Monday and Wednesday, 2:00–3:15 PM
Where: IRB 1116 & Panopto live-stream, or sometimes Zoom (link on ELMS), Piazza (link on ELMS), & Slack (link on ELMS)
Office hours: Whenever; email us first at {johnd,mknittel} at umd.edu

Description of Course

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 mid-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 mid-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 16, 2022 at 1:30PM). Examples of projects from recent years that developed into full papers:

In addition to the course project, students will write two short blog posts and/or give two short, pre-recorded video presentations covering some research topic relevant to the class—a paper, papers, book chapter, recent event, topic of interest, and so on. This can be written using Google Docs/Word/Medium/etc, and/or recorded via Zoom or another, similar piece of software. Unless the student objects, we'll post this publicly on the course website. You're very welcome to instead write a publicly-available summary of a paper as a blog post—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. Here are some example blog-post-style writeups that cover academic papers in the mechanism design space: GAIW write-ups, e.g., Example 1 and Example 2.

We expect final grades to be calculated as follows, although this may change as the semester progress (any updates to grading procedure will be addressed in class and updated here appropriately):


 

This course is aimed at strong B.Sc. students with a reasonable degree of mathematical maturity and an interest in applied mechanism design. No background in economics is expected. If in doubt, e-mail me: johnd@umd.edu!

Schedule

(Schedule subject to change as the semester progresses!)
# Date Topic Reading Slides Lecturer Notes
1 1/24 Introduction Alvin E. Roth. The economist as engineer: Game theory, experimentation, and computation as tools for design economics. Econometrica, 2002. (Section 1, or more if you'd like!) pdf, pptx Dickerson THIS LECTURE WILL BE VIRTUAL
Part I: The Basics of Game Theory and Mechanism Design
2 1/26 Intro to Game Theory Chapters 1 and 2 of Algorithmic Game Theory. pdf, pptx Dickerson In-person lecture (& recorded/on ELMS)
3 1/31 Intro to Game Theory, Continued Chapter 3 of Algorithmic Game Theory. pdf, pptx Dickerson Seinfeld RPS Colab: link
4 2/2 Intro to Game Theory, Continued — pdf, pptx Dickerson Integer game from lecture: .xlsx
5 2/7 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
6 2/9 Primer in Combinatorial Optimization, Continued — pdf, pptx Dickerson
7 2/14 Stable Matching — pdf, pptx Knittel
8 2/16 Stable Matching, Continued — pdf, pptx Knittel
9 2/21 Application: Faculty Hiring The Affiliate Matching Problem pdf, pptx Knittel
10 2/23 Intro to Mechanism Design Chapter 9 of Algorithmic Game Theory. pdf, pptx Dickerson
11 2/28 Intro to Mechanism Design, Continued Chapter 2 of the Handbook for Computational Social Choice. (password: cam1CSC) pdf, pptx Dickerson THIS LECTURE WILL BE PRE-RECORDED & VIRTUAL (NOT LIVE); Lectures posted in the Zoom directory on ELMS
12 3/2 Intro to Mechanism Design, Continued — pdf, pptx Dickerson THIS LECTURE WILL BE PRE-RECORDED & VIRTUAL (NOT LIVE); Lectures posted in the Zoom directory on ELMS
13 3/7 Intro to Mechanism Design, Continued Roger Myerson. Optimal Auction Design. Mathematics of Operations Research, 1981. pdf, pptx Dickerson
14 3/9 Intro to Mechanism Design, Continued — pdf, pptx Dickerson
15 3/14 Security Games Kiekintveld et al. Computing optimal randomized resource allocations for massive security games. AAMAS, 2009. pdf, pptx Dickerson Happy Pi Day!
16 3/16 Fair Allocations Brams and Taylor. An Envy-Free Cake Division Protocol. The American Mathematical Monthly, 1995. pdf, pptx Knittel First paper presentation due!
3/18 — Project proposal due
3/21 SPRING BREAK — — —
3/23 SPRING BREAK — — —
17 3/28 Fair Allocation, Continued — pdf, pptx Knittel
18 3/30 Fair Allocation, Continued — pdf, pptx Knittel
19 4/4 Stochastic Games & Primer on Markov Decision Processes (MDPs) — pdf, pptx Dickerson
20 4/6 Stochastic Games & Primer on Markov Decision Processes (MDPs), Continued — pdf, pptx Dickerson
21 4/11 Stochastic Games & Primer on Markov Decision Processes (MDPs), Continued — pdf, pptx Dickerson
22 4/13 Fairness in Machine Learning Dwork et al. Fairness Through Awareness. Innovations in Theoretical Computer Science, 2012. ; Barocas, Hardt, and Narayanan. Fairness and Machine Learning. ; and, Barocas & Selbst. Big Data's Disparate Impact. pdf, pptx Knittel
23 4/18 Fair Clustering — pdf, pptx Knittel Fair clustering tutorial: fairclustering.com
24 4/20 Fair Clustering, Continued — pdf, pptx Knittel
25 4/25 Single-Agent Mechanism Design — pdf, pptx Guest Speaker: Michael Curry Project checkup due
26 4/27 Single-Agent Mechanism Design, Continued — pdf, pptx Guest Speaker: Michael Curry
27 5/2 Fair Dataset Design — Schumann et al. A Step Toward More Inclusive People Annotations for Fairness, AIES, 2021. Guest Speaker: Candice Schumann Second paper presentation due
28 5/4 Project & Team Day Please spend this time explicitly meeting with your project group, and feel free to reach out to the instructors You, but virtually! Marina and I will be available to discuss your projects, or we can chat asynchronously
29 5/9 Final Project Presentations — You (either in person or virtual)! Final project summary