Stability in Matching Markets with Complex Constraints

• 成果类型: Article
• 署名作者: Nguyen, Hai; Nguyen, Thanh; Teytelboym, Alexander
• 署名单位: Purdue University System; Purdue University; Purdue University System; Purdue University; University of Oxford; University of Oxford
• 刊物名称: MANAGEMENT SCIENCE
• ISSN/ISSBN: 0025-1909
• DOI: 10.1287/mnsc.2020.3869
• 发表日期: 2021
• 页码: 7438-7454
• 关键词: Matching markets; market design; Group stability; multidimensional constraints; knapsack constraints; Refugee resettlement

摘要

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.