Stability in Matching Markets with Complex Constraints

Management Science - 2021
Huy Hung Nguyen1, Thành Tiên Nguyễn2, Alexander Teytelboym3
1Department of Computer Science, Purdue University, West Lafayette, Indiana 47907
2Krannert School of Management, Purdue University, West Lafayette, Indiana 47907
3Department of Economics and St. Catherine’s College, University of Oxford, Oxford OX1 3UQ, United Kingdom

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

10.1257/000282803322157061

10.1016/S0095-8956(02)00028-X

10.1006/jctb.1997.1731

10.1287/mnsc.2015.2162

Ashlagi I, 2020, Oper. Res., 68, 467

10.1257/aer.p20171049

10.1086/687476

10.1126/science.aao4408

10.1016/j.disopt.2015.02.002

10.1016/j.ejor.2020.03.018

10.1016/j.dam.2011.11.003

10.1007/s10472-015-9491-5

10.1016/j.tcs.2010.05.005

Bronfman S, 2018, ACM Trans. Econom. Comput., 6, 21

10.3982/TE2793

10.3982/ECTA13547

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.

10.1257/aer.20130929

10.1016/j.jet.2014.03.004

Fragiadakis D, 2016, ACM Trans. Econom. Comput., 4, 6

10.1080/00029890.1962.11989827

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.

10.1257/aer.p20171048

10.1257/aer.98.3.1189

10.1257/0002828054825466

Huang C-C (2010) Classified stable matching. SODA '10: Proc. 21st Annual ACM-SIAM Sympos. Discrete Algorithms, Philadelphia, 1235–1253.

10.1145/28869.28871

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.

10.1257/aer.102.3.366

10.1257/aer.20101552

10.2307/1913392

10.1016/j.jet.2004.04.006

10.1086/704074

10.1257/aer.20141188

10.1287/opre.2019.1909

10.1016/j.jet.2016.04.006

10.1086/261272

Roth AE, 1991, Amer. Econom. Rev., 81, 415

10.1111/1468-0262.00335

Roth AE, 1994, Amer. Econom. Rev., 84, 992

10.1287/moor.18.4.803

10.2307/1909383

10.1287/moor.1060.0207

10.1287/inte.2014.0781

Sönmez T, Yenmez MB (2019a) Affirmative action with overlapping reserves. Technical report, Boston College Department of Economics, Boston.

10.1016/0196-6774(91)90028-W

10.1287/moor.23.4.874

10.22574/jmid.2017.12.003

Thông tin
Thông tin xuất bản

Management Science

Thông tin tác giả