×

Improving matching under hard distributional constraints. (English) Zbl 1396.91568

Summary: Distributional constraints are important in many market design settings. Prominent examples include the minimum manning requirements at each Army branch in military cadet matching and diversity considerations in school choice, whereby school districts impose constraints on the demographic distribution of students at each school. Standard assignment mechanisms implemented in practice are unable to accommodate these constraints. This leads policymakers to resort to ad hoc solutions that eliminate blocks of seats ex ante (before agents submit their preferences) to ensure that all constraints are satisfied ex post (after the mechanism is run). We show that these current solutions ignore important information contained in the submitted preferences, resulting in avoidable inefficiency. We then introduce new dynamic quotas mechanisms that result in Pareto superior allocations while at the same time respecting all distributional constraints and satisfying important fairness and incentive properties. We expect the use of our mechanisms to improve the performance of matching markets with distributional constraints in the field.

MSC:

91B68 Matching models
Full Text: DOI

References:

[1] Abdulkadiroğlu, Atila (2005), “College admissions with affirmative action.” International Journal of Game Theory, 33, 535-549. 10.1007/s00182-005-0215-7 · Zbl 1086.91049
[2] Abdulkadiroğlu, Atila, Yeon‐KooChe, and YusukeYasuda (2011), “Resolving conflicting preferences in school choice: The “Boston” mechanism reconsidered.” American Economic Review, 101, 399-410.
[3] Abdulkadiroğlu, Atila, Parag A.Pathak, Alvin E.Roth, and TayfunSönmez (2005), “The Boston Public School match.” American Economic Review: Papers and Proceedings, 95, 368-371.
[4] Abdulkadiroğlu, Atila and TayfunSönmez (2003), “School choice: A mechanism design approach.” American Economic Review, 93, 729-747.
[5] Afacan, Mustafa Oğuz (2013), “Filling position incentives in matching markets.” Working paper, Sabanci University.
[6] Akbarpour, Mohammad, ShengwuLi, and Shayan OveisGharan (2016), “Thickness and information in dynamic matching markets.” Unpublished paper.
[7] Akyol, Ethem (2013), “Welfare comparison of school choice mechanisms under incomplete information.” Unpublished paper, Pennsylvania State University.
[8] Aygün, Orhan and InácioBó (2016), “College admission with multidimensional privileges: The Brazilian affirmative action case.” Unpublished paper, WZB Berlin Social Science Center.
[9] Aygün, Orhan and TayfunSönmez (2013), “Matching with contracts: Comment.” American Economic Review, 103, 2050-2051.
[10] Balinski, Michel and TayfunSönmez (1999), “A tale of two mechanisms: Student placement.” Journal of Economic Theory, 84, 73-94. 10.1006/jeth.1998.2469 · Zbl 0916.90008
[11] Bergemann, Dirk and StephenMorris (2005), “Robust mechanism design.” Econometrica, 73, 1771-1813. · Zbl 1151.91327
[12] Biró, Peter, TamásFleiner, Robert W.Irving, and David F.Manlove (2010), “The college admissions problem with lower and common quotas.” Theoretical Computer Science, 411, 3136-3153. · Zbl 1193.91099
[13] Braun, Sebastian, NadjaDwenger, DorotheaKübler, and AlexanderWestkamp (2014), “Implementing quotas in university admission: An experimental analysis.” Games and Economic Behavior, 85, 232-251. · Zbl 1292.91135
[14] Budish, Eric, Yeon‐KooChe, FuhitoKojima, and PaulMilgrom (2013), “Designing random allocation mechanisms: Theory and applications.” American Economic Review, 103, 585-623.
[15] Cowen Institute for Public Education Initiatives (2011), “Case studies of school choice and open enrollment in four cities.” Technical report, Tulane University.
[16] Doğan, Battal (2016), “Responsive affirmative action in school choice.” Journal of Economic Theory, 165, 69-105. · Zbl 1371.91133
[17] Dubins, Lester E. and David A.Freedman (1981), “Machiavelli and the Gale-Shapley algorithm.” American Mathematical Monthly, 88, 485-494. · Zbl 0449.92024
[18] Echenique, Federico and M. BuminYenmez (2015), “How to control controlled school choice.” American Economic Review, 105, 2679-2694.
[19] Ehlers, Lars, Isa E.Hafalir, M. BuminYenmez, and Muhammed A.Yildirim (2014), “School choice with controlled choice constraints: Hard bounds versus soft bounds.” Journal of Economic Theory, 153, 648-683. 10.1016/j.jet.2014.03.004 · Zbl 1309.91102
[20] Ehlers, Lars and BettinaKlaus (2004), “Resource‐monotonicity for house allocation problems.” International Journal of Game Theory, 32, 545-560. · Zbl 1098.91080
[21] Erdil, Aytek and TaroKumano (2013), “Prioritizing diversity in school choice.” Unpublished paper, University of Cambridge.
[22] Featherstone, Clayton and MurielNiederle (2014), “Improving on strategyproof school choice mechanisms: An experimental investigation.” Unpublished paper, Stanford University.
[23] Fleiner, Tamás (2003), “A fixed‐point approach to stable matchings and some applications.” Mathematics of Operations Research, 28, 103-126. · Zbl 1082.90096
[24] Fragiadakis, Daniel, AtsushiIwasaki, PeterTroyan, SuguruUeda, and MakotoYokoo (2015), “Strategyproof matching with minimum quotas.” ACM Transactions on Economics and Computation, 4, 6.1-6.40.
[25] Gale, David and Lloyd S.Shapley (1962), “College admissions and the stability of marriage.” American Mathematical Monthly, 69, 9-15. 10.2307/2312726 · Zbl 0109.24403
[26] Gale, David and Marilda A. OliveiraSotomayor (1985a), “Ms. Machiavelli and the stable matching problem.” American Mathematical Monthly, 92, 261-268. · Zbl 0595.90004
[27] Gale, David and Marilda A. OliveiraSotomayor (1985b), “Some remarks on the stable matching problem.” Discrete Applied Mathematics, 11, 223-232. · Zbl 0596.90054
[28] Hafalir, Isa E., M. BuminYenmez, and Muhammed A.Yildirim (2013), “Effective affirmative action in school choice.” Theoretical Economics, 8, 325-363. · Zbl 1395.91344
[29] Hamada, Koki, KazuoIwama, and ShuichiMiyazaki (2011), “The hospitals/residents problem with quota lower bounds.” In Proceedings of the 19th Annual European Symposium on Algorithms (ESA 2011), 180-191, Springer, Berlin. · Zbl 1331.68090
[30] Hatfield, John W. and FuhitoKojima (2009), “Group incentive compatibility for matching with contracts.” Games and Economic Behavior, 67, 745-749. · Zbl 1180.91211
[31] Hatfield, John W. and FuhitoKojima (2010), “Substitutes and stability for matching with contracts.” Journal of Economic Theory, 145, 1704-1723. · Zbl 1245.91068
[32] Hatfield, John W. and Scott DukeKominers (2011), “Contract design and stability in matching markets.” Unpublished paper, Harvard University.
[33] Hatfield, John W. and Scott DukeKominers (2012), “Matching in networks with bilateral contracts.” American Economic Journal: Microeconomics, 4, 176-208.
[34] Hatfield, John W. and Paul R.Milgrom (2005), “Matching with contracts.” American Economic Review, 95, 913-935.
[35] Kadam, Sangram V. and Maciej H.Kotowski (2014), “Multi‐period matching.” Unpublished paper, Harvard University.
[36] Kamada, Yuichiro and FuhitoKojima (2015), “Efficient matching under distributional concerns: Theory and application.” American Economic Review, 105, 67-99.
[37] Kelso, Alexander S. and Vincent P.Crawford (1982), “Job matching, coalition formation, and gross substitutes.” Econometrica, 50, 1483-1504. · Zbl 0503.90019
[38] Kennes, John, DanielMonte, and NorovsambuuTumennasan (2014a), “The day care assignment: A dynamic matching problem.” American Economic Journal: Microeconomics, 6, 362-406.
[39] Kennes, John, DanielMonte, and NorovsambuuTumennasan (2014b), “Dynamic matching markets and the deferred acceptance mechanism.” Unpublished paper, Dalhousie University.
[40] Kesten, Onur (2006), “On two competing mechanisms for priority‐based allocation problems.” Journal of Economic Theory, 127, 155-171. 10.1016/j.jet.2004.11.001 · Zbl 1125.91019
[41] Kojima, Fuhito (2012), “School choice: Impossibilities for affirmative action.” Games and Economic Behavior, 75, 685-693. 10.1016/j.geb.2012.03.003 · Zbl 1239.91039
[42] Kojima, Fuhito, AkihisaTamura, and MakotoYokoo (2014), “Designing matching mechanisms under constraints: An approach from discrete convex analysis.” Unpublished paper, Munich Personal RePEc Archive.
[43] Kominers, Scott Duke and TayfunSönmez (2016), “Matching with slot‐specific priorities: Theory.” Theoretical Economics, 11, 683-710. 10.3982/TE1839 · Zbl 1395.91346
[44] Konishi, Hideo and M. UtkuÜnver (2006), “Games of capacity manipulation in hospital‐intern markets.” Social Choice and Welfare, 27, 3-24. 10.1007/s00355-006-0097-z · Zbl 1180.91024
[45] Martínez, Ruth, JordiMassó, AlejandroNeme, and JorgeOviedo (2000), “Single agents and the set of many‐to‐one stable matchings.” Journal of Economic Theory, 91, 91-105. · Zbl 0955.91048
[46] McVitie, David G. and Leslie B.Wilson (1971), “The stable marriage problem.” Communications of the ACM, 14, 486-490.
[47] Nambiar, Meera and JoshBavas (2010), “Rudd plan won”t fix rural doctor shortage: RDA.” ABC. Available at http://www.abc.net.au/news/2010-03-16/rudd-plan-wont-fix-rural-doctor-shortage-rda/365524.
[48] Orange, Richard (2015), “Sweden urged to rethink parents” choice over schools after education decline.” The Guardian. Available at http://www.theguardian.com/world/2015/may/04/sweden-school-choice-education-decline-oecd.
[49] Pathak, Parag A. and TayfunSönmez (2008), “Leveling the playing field: Sincere and sophisticated players in the Boston mechanism.” American Economic Review, 98, 1636-1652.
[50] Pathak, Parag A. and TayfunSönmez (2013), “School admissions reform in Chicago and England: Comparing mechanisms by their vulnerability to manipulation.” American Economic Review, 103, 80-106.
[51] Roth, Alvin E. (1982), “The economics of matching: Stability and incentives.” Mathematics of Operations Research, 7, 617-628. · Zbl 0496.90008
[52] Roth, Alvin E. (1984), “The evolution of the labor market for medical interns and residents: A case study in game theory.” Journal of Political Economy, 92, 991-1016.
[53] Roth, Alvin E. (1986), “On the allocation of residents to rural hospitals: A general property of two‐sided matching markets.” Econometrica, 54, 425-427.
[54] Roth, Alvin E. (1991), “A natural experiment in the organization of entry‐level labor markets: Regional markets for new physicians and surgeons in the United Kingdom.” American Economic Review, 81, 415-440.
[55] Roth, Alvin E. (2002), “The economist as engineer: Game theory, experimentation, and computation as tools for design economics.” Econometrica, 70, 1341-1378. · Zbl 1137.91339
[56] Roth, Alvin E. and ElliottPeranson (1999), “The redesign of the matching market for American physicians: Some engineering aspects of economic design.” American Economic Review, 89, 748-780.
[57] Roth, Alvin E. and Marilda A. OliveiraSotomayor (1990), Two‐Sided Matching: A Study in Game‐Theoretic Modeling and Analysis, volume 18 of Econometric Society Monographs. Cambridge University Press, Cambridge. · Zbl 0726.90003
[58] Shapley, Lloyd S. and Herbert E.Scarf (1974), “On cores and indivisibility.” Journal of Mathematical Economics, 1, 23-37. 10.1016/0304-4068(74)90033-0 · Zbl 0281.90014
[59] Sönmez, Tayfun (1997), “Manipulation via capacities in two‐sided matching markets.” Journal of Economic Theory, 77, 197-204. 10.1006/jeth.1997.2316 · Zbl 0892.90011
[60] Sönmez, Tayfun and Tobias B.Switzer (2013), “Matching with (branch‐of‐choice) contracts at United States Military Academy.” Econometrica, 81, 451-488. 10.3982/ECTA10570 · Zbl 1274.91334
[61] Talbott, Chris (2007), “Shortage of doctors affects rural U.S.” The Washington Post. Available at http://www.washingtonpost.com/wp-dyn/content/article/2007/07/21/AR2007072100432.html.
[62] Thomson, William (2010), “Fair allocation rules.” In Handbook of Social Choice and Welfare, Vol. 2 (Kenneth J.Arrow (ed.), Amartya K.Sen (ed.), and KotaroSuzumura (ed.), eds.), 393-506, Elsevier, Amsterdam.
[63] Troyan, Peter (2012), “Comparing school choice mechanisms by interim and ex‐ante welfare.” Games and Economic Behavior, 75, 936-947. · Zbl 1239.91050
[64] Westkamp, Alexander (2013), “An analysis of the German university admissions system.” Economic Theory, 53, 561-589. · Zbl 1278.91108
[65] Wilson, Robert (1987), “Game‐theoretic analyses of trading processes.” In Advances in Economic Theory: Fifth World Congress (Truman F.Bewley (ed.), ed.), Econometric Society Monographs, 33-70, Cambridge University Press, Cambridge. · Zbl 0729.90694
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.