Here's a paper motivated in part by the issues that arise in matching refugee families to localities in which to settle (once they have been granted asylum in a particular country). It's also a good example of the way that operations research methods are playing an increasing role in market design.
Hai Nguyen, Thành Nguyen, Alexander Teytelboym (2021) Stability in Matching Markets with Complex Constraints. Management Science 67(12):7438-7454. https://doi.org/10.1287/mnsc.2020.3869
Abstract. "We develop a model of many-to-one matching markets in which agents with multiunit demand aim to maximize a cardinal linear objective subject to multidimensional knapsack constraints. The choice functions of agents with multiunit demand are therefore not substitutable. As a result, pairwise stable matchings may not exist and even when they do, may be highly inefficient. We provide an algorithm that finds a group-stable matching that approximately satisfies all the multidimensional knapsack constraints. The novel ingredient in our algorithm is a combination of matching with contracts and Scarf’s Lemma. We show that the degree of the constraint violation under our algorithm is proportional to the sparsity of the constraint matrix. The algorithm, therefore, provides practical constraint violation bounds for applications in contexts, such as refugee resettlement, day care allocation, and college admissions with diversity requirements. Simulations using refugee resettlement data show that our approach produces outcomes that are not only more stable, but also more efficient than the outcomes of the Deferred Acceptance algorithm. Moreover, simulations suggest that in practice, constraint violations under our algorithm would be even smaller than the theoretical bounds."
"Around 50,000 refugees are resettled to the United States every year. Nine American resettlement agencies coordinate networks of dozens of local communities (which we refer to as localities) that support refugees during their first few years in the United States. Localities are allowed to admit different numbers of refugees and offer different services (e.g., language support, support for large families, support for single parents, etc.) that may or may not match the needs of the refugees (Ahani et al. 2021, Delacrétaz et al. 2019). In order to secure government approval to conduct resettlement, resettlement agencies must aim to maximize the number of refugees who are employed within 90 days of arrival. Some resettlement agencies have begun using integer optimization and machine learning in order to improve refugee outcomes (Bansak et al. 2018, Ahani et al. 2021); however, as far as we know, refugees’preferences over localities are presently not collected anywhere in the world.
...
Our algorithm is a novel combination of Scarf’s Lemma and a rounding procedure. We build on the approach of Nguyen and Vohra (2018); however, we make a number of substantial extensions and modifications. The novelty of our approach is the way we apply Scarf’s Lemma to capture group stability. To use Scarf’s Lemma for stable matching problems, one needs to create a constraint matrix Q, where each column corresponds to a possible blocking coalition. Hitherto, two methods to construct such a matrix have been proposed: first, with columns corresponding to all possible blocking coalitions (Scarf 1967); second, with columns corresponding to small blocking coalitions (a hospital and a doctor or a doctor couple and two hospitals) (see Nguyen and Vohra 2018). Although the method of Nguyen and Vohra only obtains matchings that are immune to deviations by small coalitions, Scarf’s method can, in principle, capture group stability. However, the disadvantage of Scarf’s method is that the resulting constraint matrix is not sparse, which prevents us from guaranteeing small error bounds in the rounding procedure.
"Our main structural contribution is a new way of combining ideas from matching with contracts with Scarf’s method in order to create an appropriate constraint matrix. A contract specifies both agents in the match as well as a “price” for one of the dimensions of the knapsack constraints. Our method allows us to get the best of both methods: the sparsity of our constraint matrix does not change, but the prices specified in the contracts still allow us to capture group stability via pairwise stability."
***********
Earlier:
Posts
No comments:
Post a Comment