Stability in Matching Markets with Complex Constraints

References

• Abdulkadiroğlu A, Sönmez T (2003) School choice: A mechanism design approach. Amer. Econom. Rev. 93(3):729–747.Crossref, Google Scholar
• Ahani N, Andresson T, Martinello A, Teytelboym A, Trapp AC (2021) Placement optimization in refugee resettlement. Oper. Res. Forthcoming.Google Scholar
• Aharoni R, Fleiner T (2003) On a lemma of Scarf. J. Combin. Theory Ser. B 87(1):72–80.Crossref, Google Scholar
• Aharoni R, Holzman R (1998) Fractional kernels in digraphs. J. Combin. Theory Ser. B 73(1):1–6.Crossref, Google Scholar
• Ashlagi I, Shi P (2016) Optimal allocation without money: An engineering approach. Management Sci. 62(4):1078–1097.Link, Google Scholar
• Ashlagi I, Saberi A, Shameli A (2020) Assignment mechanisms under distributional constraints. Oper. Res. 68(2):467–479.Abstract, Google Scholar
• Aygün O, Bó I (2021) College admission with multidimensional privileges: The Brazilian affirmative action case. Working paper, Amer. Econom. J. Microeconomics. Forthcoming.Google Scholar
• Aygün O, Turhan B (2017) Large-scale affirmative action in school choice: Admissions to IITs in India. Amer. Econom. Rev. 107(5):210–213.Crossref, Google Scholar
• Azevedo EM, Leshno JD (2016) A supply and demand framework for two-sided matching markets. J. Political Econom. 124(5):1235–1268.Crossref, Google Scholar
• Bansak K, Ferwerda J, Hainmueller J, Dillon A, Hangartner D, Lawrence D, Weinstein J (2018) Improving refugee integration through data-driven algorithmic assignment. Science 359(6373):325–329.Crossref, Google Scholar
• Biró P, Fleiner T (2016) Fractional solutions for capacitated NTU-games, with applications to stable matchings. Discrete Optim. 22(A):241–254.Crossref, Google Scholar
• Biró P, Gudmundsson J (2021) Complexity of finding Pareto-efficient allocations of highest welfare. Eur. J. Oper. Res. Forthcoming.Crossref, Google Scholar
• Biró P, McDermid E (2014) Matching with sizes (or scheduling with processing set restrictions). Discrete Appl. Math. 164(2014):61–67.Crossref, Google Scholar
• Biró P, Fleiner T, Irving RW (2016) Matching couples with Scarf’s algorithm. Ann. Math. Artificial Intelligence 77(3-4):303–316.Crossref, Google Scholar
• Biró P, Fleiner T, Irving RW, Manlove DF (2010) The college admissions problem with lower and common quotas. Theoret. Comput. Sci. 411(34):3136–3153.Crossref, Google Scholar
• Bronfman S, Alon N, Hassidim A, Romm A (2018) Redesigning the Israeli medical internship match. ACM Trans. Econom. Comput. 6(3-4):21.Google Scholar
• Che Y-K, Tercieux O (2018) Payoff equivalence of efficient mechanisms in large matching markets. Theoret. Econom. 13(1):239–271.Crossref, Google Scholar
• Che Y-K, Kim J, Kojima F (2019) Stable matching in large economies. Econometrica 87(1):65–110.Crossref, Google Scholar
• Correa J, Epstein R, Escobar J, Rios I, Bahamondes B, Bonet C, Epstein N, et al.. (2019) School choice in Chile. Proc. 2019 ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 325–343.Google Scholar
• 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.Google Scholar
• Delacrétaz D (2019) Stability in matching markets with sizes. Working paper, University of Oxford, United Kingdom.Google Scholar
• Delacrétaz D, Kominers SD, Teytelboym A (2019) Matching mechanisms for refugee resettlement. Working paper, Oxford University, Oxford, UK.Google Scholar
• Echenique F, Yenmez MB (2015) How to control controlled school choice. Amer. Econom. Rev. 105(8):2679–2694.Crossref, Google Scholar
• Ehlers L, Hafalir IE, Yenmez MB, Yildirim MA (2014) School choice with controlled choice constraints: Hard bounds vs. soft bounds. J. Econom. Theory 153:648–683.Crossref, Google Scholar
• Erdil A, Kumano T (2012) Prioritizing diversity in school choice. Working paper, Washington University in St. Louis, St. Louis.Google Scholar
• Fragiadakis D, Iwasaki A, Troyan P, Ueda S, Yokoo M (2016) Strategyproof matching with minimum quotas. ACM Trans. Econom. Comput. 4(1):6.Google Scholar
• Gale D, Shapley LS (1962) College admissions and the stability of marriage. Amer. Math. Monthly 69(1):9–15.Crossref, Google Scholar
• 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.Google Scholar
• Hassidim A, Romm A, Shorrer RI (2017) Redesigning the Israeli psychology master’s match. Amer. Econom. Rev. 107(5):205–209.Crossref, Google Scholar
• Hatfield JW, Kojima F (2008) Matching with contracts. Amer. Econom. Rev. 98(3):1189–1194.Crossref, Google Scholar
• Hatfield JW, Milgrom P (2005) Matching with contracts. Amer. Econom. Rev. 95(4):913–935.Crossref, Google Scholar
• Huang C-C (2010) Classified stable matching. SODA '10: Proc. 21st Annual ACM-SIAM Sympos. Discrete Algorithms, Philadelphia, 1235–1253.Google Scholar
• Irving RW, Leather P, Gusfield D (1987) An efficient algorithm for the “optimal” stable marriage. J. ACM 34(3):532–543.Crossref, Google Scholar
• 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.Google Scholar
• Kamada Y, Kojima F (2012) Stability and strategy-proofness for matching with constraints: A problem in the Japanese medical match and its solution. Amer. Econom. Rev. 102(3):366–370.Crossref, Google Scholar
• Kamada Y, Kojima F (2015) Efficient matching under distributional constraints: Theory and applications. Amer. Econom. Rev. 105(1):67–99.Crossref, Google Scholar
• Kamada Y, Kojima F (2021) Fair matching under constraints: Theory and applications. Rev. Econom. Stud. Forthcoming.Google Scholar
• Kelso AS, Crawford VP (1982) Job matching, coalition formation, and gross substitutes. Econometrica 50(6):1483–1504.Crossref, Google Scholar
• Kintali S (2008) Scarf is ppad-complete. Preprint, submitted December 9, https://arxiv.org/abs/0812.1601.Google Scholar
• Király T, Pap J (2010) Kernels, stable matchings, and Scarf’s Lemma. Iwata S, ed., RIMS Kôkyûroku Bessatsu, B23 (Eotvos Lorand University, Budapest, Hungary), pp. 131–145.Google Scholar
• Klaus B, Klijn F (2005) Stable matchings and preferences of couples. J. Econom. Theory 121(1):75–106.Crossref, Google Scholar
• Milgrom P (2017) Discovering Prices: Auction Design in Markets with Complex Constraints (Columbia University Press, New York).Google Scholar
• Milgrom P, Segal I (2020) Clock auctions and radio spectrum reallocation. J. Political Econom. 128(1):1–31.Crossref, Google Scholar
• Nguyen T, Vohra R (2018) Near-feasible stable matchings with couples. Amer. Econom. Rev. 108(11):3154–3169.Crossref, Google Scholar
• Nguyen T, Vohra R (2019) Stable matching with proportionality constraints. Oper. Res. 67(6):1503–1519.Link, Google Scholar
• Nguyen T, Peivandi A, Vohra R (2016) Assignment problems with complementarities. J. Econom. Theory 165(2016):209–241.Crossref, Google Scholar
• Noda S (2018) Large matchings in large markets with flexible supply. Preprint, submitted November 5, https://ssrn.com/abstract=3215670.Google Scholar
• Roth AE (1984) The evolution of the labor market for medical interns and residents: A case study in game theory. J. Political Econom. 92(6):991–1016.Crossref, Google Scholar
• Roth AE (1991) A natural experiment in the organization of entry-level labor markets: Regional markets for new physicians and surgeons in the United Kingdom. Amer. Econom. Rev. 81(3):415–440.Google Scholar
• Roth AE (2002) The economist as engineer: Game theory, experimentation, and computation as tools for design economics. Econometrica 70(4):1341–1378.Crossref, Google Scholar
• Roth AE, Xing X (1994) Jumping the gun: Imperfections and institutions related to the timing of market transactions. Amer. Econom. Rev. 84(4):992–1044.Google Scholar
• Roth AE, Rothblum UG, Vande Vate JH (1993) Stable matchings, optimal assignments, and linear programming. Math. Oper. Res. 18(4):803–828.Link, Google Scholar
• Roth BN, Shorrer RI (2020) Making marketplaces safe: Dominant individual rationality and applications to market design. Management Sci., ePub ahead of print December 8, https://doi.org/10.1287/mnsc.2020.3643.Google Scholar
• Scarf HE (1967) The core of an n-person game. Econometrica 35(1):50–69.Crossref, Google Scholar
• Sethuraman J, Teo C-P, Qian L (2006) Many-to-one stable matching: Geometry and fairness. Math. Oper. Res. 31(3):581–596.Link, Google Scholar
• Shi P (2015) Guiding school-choice reform through novel applications of operations research. Interfaces 45(2):117–132.Link, Google Scholar
• Sönmez T, Yenmez MB (2019a) Affirmative action with overlapping reserves. Technical report, Boston College Department of Economics, Boston.Google Scholar
• Sönmez T, Yenmez MB (2019b) Constitutional implementation of vertical and horizontal reservations in India: A unified mechanism for civil service allocation and college admissions. Working paper, Department of Economics, Boston College, Boston.Google Scholar
• Tan JJ (1991) A necessary and sufficient condition for the existence of a complete stable matching. J. Algorithms 12(1):154–178.Crossref, Google Scholar
• Teo C-P, Sethuraman J (1998) The geometry of fractional stable matchings and its applications. Math. Oper. Res. 23(4):874–891.Link, Google Scholar
• Veski A, Biró P, Pöder K, Lauri T (2017) Efficiency and fair access in kindergarten allocation policy design. J. Mechanism Institution Design 2(1):57–104.Crossref, Google Scholar
• Wu X (2018) Core of convex matching games: A Scarf’s Lemma approach. Working paper, Department of Economics, Columbia University, New York.Google Scholar