Mechanism Design for Matching with Constraints

Abstract

In recent years, several new challenges have been observed in the application of matching theory. One important realization is that real-life matching markets are often subject to various constraints. These practical problems impose different forms of constraints on the markets which makes them different from the classical matching model. Consequently, we cannot employ classical mechanisms in these new challenges and a stable outcome, the standard solution in matching theory, is no longer guaranteed to exist.

For example, one of the most pressing issues nowadays is how to allocate refugees to hosts in a safe and timely manner. A refugee family could be placed at a host country only if the multi-dimensional requirement of the family is satisfied, which may involve different types of services such as house beds, children’s day care and special medical treatments. Such multi-dimensional constraints makes it different from the traditional two-sided matching model. Another example is the controlled school choice problem that takes account of affirmative action and diversity concerns. In this model, each student is associated with a set of types which 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 outcome.

The main objective of this research is to design efficient algorithms for these new emerging problems that satisfy desirable properties while taking agents' preferences into account. 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 resettlement is implemented in an ad hoc manner in which the preferences of both refugees and hosts are not taken into account.

Given the number of agents that participate in the market is huge, we also consider the computational efficiency to be of central importance. We are interested in designing algorithms that yield reasonable outcomes efficiently. If an algorithm could not be implemented in polynomial time, then it is not regarded as a suitable solution.