Matching Market Design with Constraints

Two-sided matching deals with finding a desirable combination of two parties, e.g., students and colleges, workers and companies, and medical residents to hospitals. Beautiful theoretical results on two-sided matching have been obtained, i.e., the celebrated Deferred Acceptance mechanism is strategyproof for students, and obtains the student optimal matching among all stable matchings.  However, these results are applicable only for the standard model, where only distributional constraints are the maximum quota (capacity limit) of each college.  In many real application domains, various distributional constraints are imposed due to social requirements. For example, a college needs a certain number of students to operate, or some medical residents must be assigned to a rural hospital.

In this talk, I represent a simple and general abstract model, and introduce a few representative constraints that can be formalized using this model. In this model, distributional constraints are defined over a set of allocation vectors, each of which describes the number of students allocated to each college.  Then, I present two general mechanisms.  One is the generalized DA, which works when distributional constraints satisfy two conditions: hereditary and an M-natural-convex set.  More specifically, the generalized DA is strategyproof, and finds the student optimal matching among all matchings that satisfy some stability requirement.  The other is the adaptive DA, which works when distributional constraints satisfy hereditary condition. It is strategyproof and nonwasteful.