Stability in Matching Markets with Complex Constraints
| Autor: | Alexander Teytelboym, Thanh D. Nguyen, Hai H. Nguyen |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
050210 logistics & transportation
Lemma (mathematics) Mathematical optimization Matching (statistics) 021103 operations research Computer science Constraint violation Strategy and Management 05 social sciences 0211 other engineering and technologies Stability (learning theory) 02 engineering and technology 0102 computer and information sciences Management Science and Operations Research 01 natural sciences 010201 computation theory & mathematics Knapsack problem 0502 economics and business Pairwise comparison Constraint matrix 050207 economics Group stability |
| Zdroj: | EC |
| ISSN: | 1526-5501 0025-1909 |
| DOI: | 10.1287/mnsc.2020.3869 |
| Popis: | 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. This paper was accepted by Gabriel Weintraub, revenue management and market analytics. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|