Matching with Constraints

1 Introduction

There has been rapid growth over recent years in the theory of matching that studies how to match two different groups of agents or objects while taking account of agents' preferences. The importance of this research area has been highlighted by the 2012 Nobel Prize in Economics to Alvin Roth and Lloyd Shapley for their contribution to "the theory of stable allocations and the practice of market design." The theory has been successfully applied to many real-life markets, including the National Resident Matching Program (NRMP) in the United States [Roth, 1984], the reform of school choice in Boston and New York city [Abdulkadiro˘glu et al., 2005], and the establishment of nationwide clearinghouses of kidney exchange [Abraham et al., 2007].

In recent years, a number of new challenges have been observed in the application of matching theory, in which refugee settlement is one of the most pressing problems. Determining which refugee family should be matched to which country and not only considering how many refugees are matched is the major objective of relocation. For instance, a refugee family may prefer to thrive in a country where they have a community or they can support themselves, and the host country may prefer migrants who can speak the same language. However, the current placement of refugees to host countries is implemented in an ad hoc manner in which the preferences of both refugees and hosts are not taken into account.

This demands for a centralized matching market approach to handle the refugee allocation problem. Delacr´etaz et al. [2016] were the first to formalize this issue as a centralized matching market problem. Different from the traditional twosided matching model such as school choice where a student occupies one school seat, a refugee family could be placed at a host country only if the multi-dimensional requirement of the family is satisfied. For instance, it may involve different types of services such as house beds, children's day care and special medical treatments. Thus the refugee resettlement is a generalization of the traditional matching problem by taking multi-dimensional feasibility constraints into consideration. Because there may not exist a stable outcome with respect to the standard stability definition, one fundamental question is how to define a weaker but reasonable stability concept which guarantees the existence of a stable outcome.

Another important realization is that real-life matching markets are often subject to various distributional constraints. For example, there has been increased attention to school choice models that take account of affirmative action and diversity concerns. This form of distributional constraints is studied intensely in the literature of controlled school choice in which students are associated with a set of types [Abdulkadiro˘glu and S¨onmez, 2003]. These types capture traits such as being from a disadvantaged group or being extra-talented. Schools impose quotas on each distinct type that need to be taken into account while deciding the match. For example, a school may have a target lower quota for accepting students from some disadvantaged group. Then a student from the disadvantaged group should be given higher precedence to other students outside of the group until the target lower quota of that school is filled.

The other form of distributional constraints occurs in the Japan Residency Matching Program (JRMP) where certain subsets of hospitals form regions and quotas are imposed on regions [Kamada and Kojima, 2015]. This is motivated by the fact that urban hospitals attract too many doctors while rural areas are suffering from a shortage. For instance, in 2008 Japanese government introduced regional caps to restrict the number of doctors that could be matched to different regions. Individual minimums could be considered as a special case of regional quotas, and has been studied in the Hungary college admission problems [Bir´o et al., 2010].

Although both lines of work have progressed in the past few years, their development has been generally distinct from each other. Since each of the lines of work stems from different real-life requirements, there has not been much work on identifying formal connections between different new models. One interesting research question is to explore the connection between two forms of distributional constraints.

2 Contribution and FutureWork

We approach these new emerging problems from the perspective of axiom analysis and algorithm design. The objective is to propose algorithms that satisfy desirable properties and compute a matching efficiently.

2.1 Refugee Resettlement

Delacr´etaz et al. [2016] proposed a quasi-stability concept for the refugee resettlement problem that satisfies the requirement of fairness at the expense of leading to a wasteful outcome, which may be undesirable in practice. Instead we started from the standard concept and weaken it in two directions: (1) a deviating refugee family can replace at most one other family, and (2) when a family replaces a set of families, at most the same amount of service for each type can be used by the new family as the set of families to be replaced. We show that each weakening operation does not generate a stability concept that guarantees existence of stable outcomes. Then we applied both weakening operations to obtain a natural stability concept, which is weak enough to guarantee existence of a stable outcome while still strong enough to lead to reasonable outcomes. We presented a clear taxonomy of these stability concepts and studied the complexity of computing stable matching with respect to different notions [Aziz et al., 2018]. Our presented solution for handling refugee resettlement still leaves a lot to be explored. For example, how to make better use of resources and how to design mechanisms when the market is dynamic.

2.2 Distributional Constraints

Although the theory of matching with distributional constraints progressed rapidly in recent years, the research directions on (1) school choice with diversity constraints and (2) hospital-doctor matching with regional quotas have been distinct from each other. Previous literature treated these two forms of distributional constraints as different models. In particular, several influential papers remark that one form of distributional constraint is different from the other [Ehlers et al., 2014]. We demonstrate that although the two models seem different, there are strong mathematical connections between them. We identify the formal connections by presenting a polynomial-time reduction to transform an instance of (1) into a corresponding instance of (2). We show how the feasibility and stability of corresponding outcomes are preserved under the reduction [Aziz et al., 2019]. In view of this, this helps unify some of the results that have been presented in the literature and provides an efficient route to transform results from one model to the other. For instance, we first prove that it is NP-complete to check the existence of feasible and stable outcomes for (1). Our reduction implies that these complexity results hold for (2) as well. Note that most work on controlled school choice assumes that each student belongs to at most one types. However, in reality students may be associated with multiple types. The remaining question is how to design mechanisms that cater to diversity objectives while still satisfying desirable properties.