---
title: "Matching with Constraints"
authors:
  - "Zhaohong Sun"
doi: "10.24963/ijcai.2019/921"
url: "https://ijcai.org/proceedings/2019/921"
pdf: "https://ijcai.org/proceedings/2019/0921.pdf"
venue: "Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence"
year: 2019
pages: "6464-6465"
track: "Doctoral Consortium"
keywords:
  - "Agent-based and Multi-agent Systems: Resource Allocation"
  - "Agent-based and Multi-agent Systems: Economic Paradigms, Auctions and Market-Based Systems"
  - "Agent-based and Multi-agent Systems: Algorithmic Game Theory"
  - "Agent-based and Multi-agent Systems: Computational Social Choice"
---

# Matching with Constraints

Zhaohong Sun

*Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence*, pages 6464-6465. DOI: [10.24963/ijcai.2019/921](https://doi.org/10.24963/ijcai.2019/921)

## Abstract

In recent years, a number of new challenges have been observed in the application of matching theory. One of the most pressing problems concerns how to allocate refugees to hosts safely and in a timely manner. Currently, this placement is implemented on an ad hoc basis where the preferences of both refugees and hosts are not taken into account. 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. The objective of this research is to design efficient algorithms while satisfying desirable properties for these new emerging problems.

## Full text

## 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.

## References

1. [Abdulkadiroglu and Sönmez, 2003] Atila Abdulkadiroglu and Tayfun Sönmez. School choice: A mechanism de- sign approach. American economic review, 93(3):729- 747, 2003.
2. [Abdulkadiroglu et al., 2005] Atila Abdulkadiroglu, Parag Pathak, Alvin Roth, and Tayfun Sönmez. The boston pub- lic school match. American Economic Review, 95(2):368- 371, 2005.
3. [Abraham et al., 2007] David J Abraham, Avrim Blum, and Tuomas Sandholm. Clearing algorithms for barter ex- change markets: Enabling nationwide kidney exchanges. In Proceedings of the 8th ACM conference on Electronic commerce, pages 295-304. ACM, 2007.
4. [Aziz et al., 2018] Haris Aziz, Jiayin Chen, Serge Gaspers, and Zhaohong Sun. Stability and pareto optimality in refugee allocation matchings. In Proceedings of the 17th International Conference on Autonomous Agents and Mul- tiAgent Systems, pages 964-972. International Foundation for Autonomous Agents and Multiagent Systems, 2018.
5. [Aziz et al., 2019] Haris Aziz, Serge Gaspers, Zhaohong Sun, and Toby Walsh. From matching with diversity con- straints to matching with regional quotas. In Proceed- ings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, pages 377-385. Interna- tional Foundation for Autonomous Agents and Multiagent Systems, 2019.
6. [Biró et al., 2010] Péter Biró, Tamás Fleiner, Robert W Irv- ing, and David F Manlove. The college admissions prob- lem with lower and common quotas. Theoretical Com- puter Science, 411(34-36):3136-3153, 2010.
7. [Delacrétaz et al., 2016] David Delacrétaz, Scott Duke Kominers, and Alexander Teytelboym. Refugee resettle- ment. University of Oxford Department of Economics Working Paper, 2016.
8. [Ehlers et al., 2014] Lars Ehlers, Isa E Hafalir, M Bumin Yenmez, and Muhammed A Yildirim. School choice with controlled choice constraints: Hard bounds versus soft bounds. Journal of Economic Theory, 153:648-683, 2014.
9. [Kamada and Kojima, 2015] Yuichiro Kamada and Fuhito Kojima. Efficient matching under distributional con- straints: Theory and applications. American Economic Review, 105(1):67-99, 2015.
10. [Roth, 1984] Alvin E Roth. The evolution of the labor mar- ket for medical interns and residents: a case study in game theory. Journal of political Economy, 92(6):991-1016, 1984.