Improving matching under hard distributional constraints
2017; Econometric Society; Volume: 12; Issue: 2 Linguagem: Inglês
10.3982/te2195
ISSN1933-6837
AutoresDaniel Fragiadakis, Peter Troyan,
Tópico(s)Experimental Behavioral Economics Studies
ResumoTheoretical EconomicsVolume 12, Issue 2 p. 863-908 Original ArticlesOpen Access Improving matching under hard distributional constraints Daniel Fragiadakis, Daniel Fragiadakis dfragiadakis@tamu.edu Department of Economics, Texas A&M UniversitySearch for more papers by this authorPeter Troyan, Peter Troyan troyan@virginia.edu Department of Economics, University of Virginia We are extremely grateful to Fuhito Kojima, Muriel Niederle, and Al Roth for numerous conversations regarding this project. We would like to thank Brian Baisa, Scott Baker, Andrey Fradkin, Guillaume Haeringer, Matt Jackson, Scott Kominers, Vikram Manjunath, Paul Milgrom, Krishna Rao, Itay Saporta-Eksten, Ilya Segal, Rodrigo Velez, Pablo Villanueva, Alex Westkamp, Alex Wolitzky, and Edison Yu for helpful comments and suggestions, as well as seminar participants at Virginia, Iowa, Cal State East Bay, Texas A&M, Western Ontario, and Illinois. We also thank a co-editor and an anonymous referee for helpful comments that improved both the results and the exposition of the paper. Generous support from the B. F. Haley and E. S. Shaw Fellowship (Troyan) and the Leonard W. Ely and Shirley R. Ely Fellowship (Fragiadakis), both through the Stanford Institute for Economic Policy Research, is gratefully acknowledged. This paper was originally circulated under the title “Market design under distributional constraints: Diversity in school choice and other applications.” Search for more papers by this author Daniel Fragiadakis, Daniel Fragiadakis dfragiadakis@tamu.edu Department of Economics, Texas A&M UniversitySearch for more papers by this authorPeter Troyan, Peter Troyan troyan@virginia.edu Department of Economics, University of Virginia We are extremely grateful to Fuhito Kojima, Muriel Niederle, and Al Roth for numerous conversations regarding this project. We would like to thank Brian Baisa, Scott Baker, Andrey Fradkin, Guillaume Haeringer, Matt Jackson, Scott Kominers, Vikram Manjunath, Paul Milgrom, Krishna Rao, Itay Saporta-Eksten, Ilya Segal, Rodrigo Velez, Pablo Villanueva, Alex Westkamp, Alex Wolitzky, and Edison Yu for helpful comments and suggestions, as well as seminar participants at Virginia, Iowa, Cal State East Bay, Texas A&M, Western Ontario, and Illinois. We also thank a co-editor and an anonymous referee for helpful comments that improved both the results and the exposition of the paper. Generous support from the B. F. Haley and E. S. Shaw Fellowship (Troyan) and the Leonard W. Ely and Shirley R. Ely Fellowship (Fragiadakis), both through the Stanford Institute for Economic Policy Research, is gratefully acknowledged. This paper was originally circulated under the title “Market design under distributional constraints: Diversity in school choice and other applications.” Search for more papers by this author First published: 26 May 2017 https://doi.org/10.3982/TE2195Citations: 43 AboutPDF ToolsRequest permissionExport citationAdd to favoritesTrack citation ShareShare Give accessShare full text accessShare full-text accessPlease review our Terms and Conditions of Use and check box below to share full-text version of article.I have read and accept the Wiley Online Library Terms and Conditions of UseShareable LinkUse the link below to share a full-text version of this article with your friends and colleagues. Learn more.Copy URL Share a linkShare onFacebookTwitterLinkedInRedditWechat Abstract 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. 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 1 Abdulkadiroğlu, Atila, Yeon-Koo Che, and Yusuke Yasuda (2011), “Resolving conflicting preferences in school choice: The “Boston” mechanism reconsidered.” American Economic Review, 101, 399– 410. 1 Abdulkadiroğlu, Atila, Parag A. Pathak, Alvin E. Roth, and Tayfun Sönmez (2005), “The Boston Public School match.” American Economic Review: Papers and Proceedings, 95, 368– 371. 1 Abdulkadiroğlu, Atila and Tayfun Sönmez (2003), “School choice: A mechanism design approach.” American Economic Review, 93, 729– 747. 1 Afacan, Mustafa Oğuz (2013), “ Filling position incentives in matching markets.” Working paper, Sabanci University. 1 Akbarpour, Mohammad, Shengwu Li, and Shayan Oveis Gharan (2016), “ Thickness and information in dynamic matching markets.” Unpublished paper. 1 Akyol, Ethem (2013), “ Welfare comparison of school choice mechanisms under incomplete information.” Unpublished paper, Pennsylvania State University. 1 Aygün, Orhan and Inácio Bó (2016), “ College admission with multidimensional privileges: The Brazilian affirmative action case.” Unpublished paper, WZB Berlin Social Science Center. 1 Aygün, Orhan and Tayfun Sönmez (2013), “Matching with contracts: Comment.” American Economic Review, 103, 2050– 2051. 1 Balinski, Michel and Tayfun Sönmez (1999), “A tale of two mechanisms: Student placement.” Journal of Economic Theory, 84, 73– 94. 10.1006/jeth.1998.2469 1 Bergemann, Dirk and Stephen Morris (2005), “Robust mechanism design.” Econometrica, 73, 1771– 1813. 1 Biró, Peter, Tamás Fleiner, Robert W. Irving, and David F. Manlove (2010), “The college admissions problem with lower and common quotas.” Theoretical Computer Science, 411, 3136– 3153. 1 Braun, Sebastian, Nadja Dwenger, Dorothea Kübler, and Alexander Westkamp (2014), “Implementing quotas in university admission: An experimental analysis.” Games and Economic Behavior, 85, 232– 251. 1 Budish, Eric, Yeon-Koo Che, Fuhito Kojima, and Paul Milgrom (2013), “Designing random allocation mechanisms: Theory and applications.” American Economic Review, 103, 585– 623. 1 Cowen Institute for Public Education Initiatives (2011), “ Case studies of school choice and open enrollment in four cities.” Technical report, Tulane University. 1 Doğan, Battal (2016), “Responsive affirmative action in school choice.” Journal of Economic Theory, 165, 69– 105. 1 Dubins, Lester E. and David A. Freedman (1981), “Machiavelli and the Gale–Shapley algorithm.” American Mathematical Monthly, 88, 485– 494. 1 Echenique, Federico and M. Bumin Yenmez (2015), “How to control controlled school choice.” American Economic Review, 105, 2679– 2694. 1 Ehlers, Lars, Isa E. Hafalir, M. Bumin Yenmez, 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 1 Ehlers, Lars and Bettina Klaus (2004), “Resource-monotonicity for house allocation problems.” International Journal of Game Theory, 32, 545– 560. 1 Erdil, Aytek and Taro Kumano (2013), “ Prioritizing diversity in school choice.” Unpublished paper, University of Cambridge. 1 Featherstone, Clayton and Muriel Niederle (2014), “ Improving on strategyproof school choice mechanisms: An experimental investigation.” Unpublished paper, Stanford University. 1 Fleiner, Tamás (2003), “A fixed-point approach to stable matchings and some applications.” Mathematics of Operations Research, 28, 103– 126. 1 Fragiadakis, Daniel, Atsushi Iwasaki, Peter Troyan, Suguru Ueda, and Makoto Yokoo (2015), “Strategyproof matching with minimum quotas.” ACM Transactions on Economics and Computation, 4, 6.1– 6.40. 1 Gale, David and Lloyd S. Shapley (1962), “College admissions and the stability of marriage.” American Mathematical Monthly, 69, 9– 15. 10.2307/2312726 1 Gale, David and Marilda A. Oliveira Sotomayor (1985a), “Ms. Machiavelli and the stable matching problem.” American Mathematical Monthly, 92, 261– 268. 1 Gale, David and Marilda A. Oliveira Sotomayor (1985b), “Some remarks on the stable matching problem.” Discrete Applied Mathematics, 11, 223– 232. 1 Hafalir, Isa E., M. Bumin Yenmez, and Muhammed A. Yildirim (2013), “Effective affirmative action in school choice.” Theoretical Economics, 8, 325– 363. 1 Hamada, Koki, Kazuo Iwama, and Shuichi Miyazaki (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. 1 Hatfield, John W. and Fuhito Kojima (2009), “Group incentive compatibility for matching with contracts.” Games and Economic Behavior, 67, 745– 749. 1 Hatfield, John W. and Fuhito Kojima (2010), “Substitutes and stability for matching with contracts.” Journal of Economic Theory, 145, 1704– 1723. 1 Hatfield, John W. and Scott Duke Kominers (2011), “ Contract design and stability in matching markets.” Unpublished paper, Harvard University. 1 Hatfield, John W. and Scott Duke Kominers (2012), “Matching in networks with bilateral contracts.” American Economic Journal: Microeconomics, 4, 176– 208. 1 Hatfield, John W. and Paul R. Milgrom (2005), “Matching with contracts.” American Economic Review, 95, 913– 935. 1 Kadam, Sangram V. and Maciej H. Kotowski (2014), “ Multi-period matching.” Unpublished paper, Harvard University. 1 Kamada, Yuichiro and Fuhito Kojima (2015), “Efficient matching under distributional concerns: Theory and application.” American Economic Review, 105, 67– 99. 1 Kelso, Alexander S. and Vincent P. Crawford (1982), “Job matching, coalition formation, and gross substitutes.” Econometrica, 50, 1483– 1504. 1 Kennes, John, Daniel Monte, and Norovsambuu Tumennasan (2014a), “The day care assignment: A dynamic matching problem.” American Economic Journal: Microeconomics, 6, 362– 406. 1 Kennes, John, Daniel Monte, and Norovsambuu Tumennasan (2014b), “ Dynamic matching markets and the deferred acceptance mechanism.” Unpublished paper, Dalhousie University. 1 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 1 Kojima, Fuhito (2012), “School choice: Impossibilities for affirmative action.” Games and Economic Behavior, 75, 685– 693. 10.1016/j.geb.2012.03.003 1 Kojima, Fuhito, Akihisa Tamura, and Makoto Yokoo (2014), “ Designing matching mechanisms under constraints: An approach from discrete convex analysis.” Unpublished paper, Munich Personal RePEc Archive. 1 Kominers, Scott Duke and Tayfun Sönmez (2016), “Matching with slot-specific priorities: Theory.” Theoretical Economics, 11, 683– 710. 10.3982/TE1839 1 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 1 Martínez, Ruth, Jordi Massó, Alejandro Neme, and Jorge Oviedo (2000), “Single agents and the set of many-to-one stable matchings.” Journal of Economic Theory, 91, 91– 105. 1 McVitie, David G. and Leslie B. Wilson (1971), “The stable marriage problem.” Communications of the ACM, 14, 486– 490. 1 Nambiar, Meera and Josh Bavas (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. 1 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. 1 Pathak, Parag A. and Tayfun Sönmez (2008), “Leveling the playing field: Sincere and sophisticated players in the Boston mechanism.” American Economic Review, 98, 1636– 1652. 1 Pathak, Parag A. and Tayfun Sönmez (2013), “School admissions reform in Chicago and England: Comparing mechanisms by their vulnerability to manipulation.” American Economic Review, 103, 80– 106. 1 Roth, Alvin E. (1982), “The economics of matching: Stability and incentives.” Mathematics of Operations Research, 7, 617– 628. 1 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. 1 Roth, Alvin E. (1986), “On the allocation of residents to rural hospitals: A general property of two-sided matching markets.” Econometrica, 54, 425– 427. 1 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. 1 Roth, Alvin E. (2002), “The economist as engineer: Game theory, experimentation, and computation as tools for design economics.” Econometrica, 70, 1341– 1378. 1 Roth, Alvin E. and Elliott Peranson (1999), “The redesign of the matching market for American physicians: Some engineering aspects of economic design.” American Economic Review, 89, 748– 780. 1 Roth, Alvin E. and Marilda A. Oliveira Sotomayor (1990), Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis, volume 18 of Econometric Society Monographs. Cambridge University Press, Cambridge. 1 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 1 Sönmez, Tayfun (1997), “Manipulation via capacities in two-sided matching markets.” Journal of Economic Theory, 77, 197– 204. 10.1006/jeth.1997.2316 1 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 1 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. 1 Thomson, William (2010), “ Fair allocation rules.” In Handbook of Social Choice and Welfare, Vol. 2 ( Kenneth J. Arrow, Amartya K. Sen, and Kotaro Suzumura, eds.), 393– 506, Elsevier, Amsterdam. 1 Troyan, Peter (2012), “Comparing school choice mechanisms by interim and ex-ante welfare.” Games and Economic Behavior, 75, 936– 947. 1 Westkamp, Alexander (2013), “An analysis of the German university admissions system.” Economic Theory, 53, 561– 589. 1 Wilson, Robert (1987), “ Game-theoretic analyses of trading processes.” In Advances in Economic Theory: Fifth World Congress ( Truman F. Bewley, ed.), Econometric Society Monographs, 33– 70, Cambridge University Press, Cambridge. Citing Literature Supporting Information Filename Description thec245-sup-0001-Supplement.pdf445.3 KB Supplement to “Improving matching under hard distributional constraints” (Theoretical Economics, Vol. 12, No. 2, May 2017, 863–908) Please note: The publisher is not responsible for the content or functionality of any supporting information supplied by the authors. Any queries (other than missing content) should be directed to the corresponding author for the article. Volume12, Issue2May 2017Pages 863-908 ReferencesRelatedInformation
Referência(s)