Abstract The theory of two-sided matching has been extensively developed and applied to many real-life application domains. As the theory has been applied to increasingly diverse types of environments, researchers and practitioners have encountered various forms of distributional constraints. Arguably, the most general class of distributional constraints would be hereditary constraints; if a matching is feasible, then any matching that assigns weakly fewer students at each college is also feasible. However, under general hereditary constraints, it is shown that no strategyproof mechanism exists that simultaneously satisfies fairness and weak nonwastefulness, which is an efficiency (students’ welfare) requirement weaker than nonwastefulness. We propose a new strategyproof mechanism that works for hereditary constraints called the Multi-Stage Generalized Deferred Acceptance mechanism (MS-GDA). It uses the Generalized Deferred Acceptance mechanism (GDA) as a subroutine, which works when distributional constraints belong to a well-behaved class called hereditary M $$^{\natural }$$ -convex set. We show that GDA satisfies several desirable properties, most of which are also preserved in MS-GDA. We experimentally show that MS-GDA strikes a good balance between fairness and efficiency (students’ welfare) compared to existing strategyproof mechanisms when distributional constraints are close to an M $$^{\natural }$$ -convex set * .

In this work, we consider a student-project-resource matching-allocation problem, where students have preferences over projects and the projects have preferences over students. In this problem, students and indivisible resources are many-to-one matched to projects whose capacities are endogenously determined by the resources allocated to them. Traditionally, this problem is decomposed into two separate problems: (1) resources are allocated to projects based on expectations (a resource allocation problem), and (2) students are matched to projects based on the capacities determined in the previous problem (a matching problem). Although both problems are well-understood, if the expectations used in the first are incorrect, we obtain a sub-optimal outcome. Thus, this problem should be solved as a whole without dividing it into two parts. We show that no strategyproof mechanism satisfies fairness and weak efficiency requirements. Given this impossibility result, we develop a new class of strategyproof mechanisms called Sample and Deferred Acceptance (SDA), which satisfies several properties on fairness and efficiency. We experimentally compare several SDA instances as well as existing mechanisms, and show that an SDA instance strikes a good balance of fairness and efficiency when students are divided into different types according to their preferences.