Stability in Matching Markets with Complex Constraints
Tóm tắt
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.
Từ khóa
Tài liệu tham khảo
Ashlagi I, 2020, Oper. Res., 68, 467
Bronfman S, 2018, ACM Trans. Econom. Comput., 6, 21
Correa J, Epstein R, Escobar J, Rios I, Bahamondes B, Bonet C, Epstein N, (2019) School choice in Chile. Proc. 2019 ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 325–343.
Dean BC, Goemans MX, Immorlica N (2006) The unsplittable stable marriage problem. Navarro G, Bertossi L, Kohayakawa Y, eds. 4th IFIP Internat. Conf. Theoret. Comput. Sci. TCS 2006, IFIP International Federation for Information Processing, vol. 209 (Springer, Boston), 65–75.
Fragiadakis D, 2016, ACM Trans. Econom. Comput., 4, 6
Gonczarowski YA, Nisan N, Kovalio L, Romm A (2019) Matching for the Israeli “Mechinot” gap-year programs: Handling rich diversity requirements. EC '19: Proc. 2019 ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 321.
Huang C-C (2010) Classified stable matching. SODA '10: Proc. 21st Annual ACM-SIAM Sympos. Discrete Algorithms, Philadelphia, 1235–1253.
Jagadeesan R (2017) Complementary inputs and the existence of stable outcomes in large trading networks. EC '17: Proc. 2017 ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 265.
Roth AE, 1991, Amer. Econom. Rev., 81, 415
Roth AE, 1994, Amer. Econom. Rev., 84, 992
Sönmez T, Yenmez MB (2019a) Affirmative action with overlapping reserves. Technical report, Boston College Department of Economics, Boston.