×
Kominers, Scott Duke; Sönmez, Tayfun

Matching with slot-specific priorities: theory. (English) Zbl 1395.91346

Theor. Econ. 11, No. 2, 683-710 (2016).
Summary: We introduce a two-sided, many-to-one matching with contracts model in which agents with unit demand match to branches that may have multiple slots available to accept contracts. Each slot has its own linear priority order over contracts; a branch chooses contracts by filling its slots sequentially, according to an order of precedence. We demonstrate that in these matching markets with slot-specific priorities, branches’ choice functions may not satisfy the substitutability conditions typically crucial for matching with contracts. Despite this complication, we are able to show that stable outcomes exist in the slot-specific priorities framework and can be found by a cumulative offer mechanism that is strategy-proof and respects unambiguous improvements in priority.

Cited in 38 Documents

MSC:

91B68 Matching models

Keywords:

market design; matching with contracts; stability; strategy-proofness; school choice, affirmative action; airline seat upgrades
Cite Review PDF
Full Text: DOI

References:

[1] Abdulkadiroğlu, Atila, Parag A.Pathak, and Alvin E.Roth (2005), “The New York City high school match.” American Economic Review: Papers and Proceedings, 95, 364-367.
[2] Abdulkadiroğlu, Atila, Parag A.Pathak, and Alvin E.Roth (2009), “Strategyproofness versus efficiency in matching with indifferences: Redesigning the NYC high school match.” American Economic Review, 99, 1954-1978.
[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, Parag A.Pathak, Alvin E.Roth, and TayfunSönmez (2006), “Changing the Boston school choice mechanism: Strategy‐proofness as equal access.” Working paper, Massachusetts Institute of Technology.
[5] Abdulkadiroğlu, Atila and TayfunSönmez (2003), “School choice: A mechanism design approach.” American Economic Review, 93, 729-747.
[6] Adachi, Hiroyuki (2000), “On a characterization of stable matchings.” Economics Letters, 68, 43-49. 10.1016/S0165-1765(99)00241-4 · Zbl 0953.91048
[7] Alkan, Ahmet (2002), “A class of multipartner matching markets with a strong lattice structure.” Economic Theory, 19, 737-746. 10.1007/s001990100179 · Zbl 1050.91073
[8] Alkan, Ahmet and DavidGale (2003), “Stable schedule matching under revealed preference.” Journal of Economic Theory, 112, 289-306. 10.1016/S0022-0531(03)00096-6 · Zbl 1068.91059
[9] Aygün, Orhan and TayfunSönmez (2012), “The importance of irrelevance of rejected contracts in matching under weakened substitutes conditions.” Working paper, Boston College.
[10] Aygün, Orhan and TayfunSönmez (2013), “Matching with contracts: Comment.” American Economic Review, 103, 2050-2051.
[11] 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
[12] Braun, Sebastian, NadjaDwenger, DorotheaKübler, and AlexanderWestkamp (2014), “Implementing quotas in university admissions: An experimental analysis.” Games and Economic Behavior, 85, 232-251. 10.1016/j.geb.2014.02.004 · Zbl 1292.91135
[13] Crawford, Vincent P. and Elsie MarieKnoer (1981), “Job matching with heterogeneous firms and workers.” Econometrica, 49, 437-450. · Zbl 1202.91141
[14] Echenique, Federico (2012), “Contracts versus salaries in matching.” American Economic Review, 102, 594-601.
[15] Echenique, Federico and JorgeOviedo (2006), “A theory of stability in many‐to‐many matching markets.” Theoretical Economics, 1, 233-273.
[16] Echenique, Federico and M. BuminYenmez (2015), “How to control controlled school choice.” American Economic Review, 105, 2679-2694.
[17] 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
[18] Fleiner, Tamás (2003), “A fixed point approach to stable matchings and some applications.” Mathematics of Operations Research, 28, 103-126. 10.1287/moor.28.1.103.14256 · Zbl 1082.90096
[19] 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
[20] Hafalir, Isa E., M. BuminYenmez, and Muhammed A.Yildirim (2013), “Effective affirmative action in school choice.” Theoretical Economics, 8, 325-363. 10.3982/TE1135 · Zbl 1395.91344
[21] Hatfield, John W. and FuhitoKojima (2009), “Group incentive compatibility for matching with contracts.” Games and Economic Behavior, 67, 745-749. 10.1016/j.geb.2009.01.007 · Zbl 1180.91211
[22] Hatfield, John W. and FuhitoKojima (2010), “Substitutes and stability for matching with contracts.” Journal of Economic Theory, 145, 1704-1723. 10.1016/j.jet.2010.01.007 · Zbl 1245.91068
[23] Hatfield, John W. and FuhitoKojima (2008), “Matching with contracts: Comment.” American Economic Review, 98, 1189-1194.
[24] Hatfield, John W., FuhitoKojima, and YusukeNarita (2015), “Promoting school competition through school choice: A market design approach.” Working paper, Stanford Graduate School of Business.
[25] Hatfield, John W. and Scott DukeKominers (forthcoming), “Contract design and stability in many‐to‐many matching.” Games and Economic Behavior. · Zbl 1393.91119
[26] Hatfield, John W. and Scott DukeKominers (2012), “Matching in networks with bilateral contracts.” American Economic Journal: Microeconomics, 4, 176-208.
[27] Hatfield, John W. and Scott DukeKominers (2014), “Hidden substitutes.” Working paper, Harvard University.
[28] Hatfield, John W. and Paul R.Milgrom (2005), “Matching with contracts.” American Economic Review, 95, 913-935.
[29] Hirata, Daisuke and YusukeKasuya (2014), “Cumulative offer process is order‐independent.” Economics Letters, 124, 37-40. 10.1016/j.econlet.2014.04.008 · Zbl 1295.91073
[30] Kelso Jr., Alexander S. and Vincent P.Crawford (1982), “Job matching, coalition formation, and gross substitutes.” Econometrica, 50, 1483-1504. · Zbl 0503.90019
[31] Klaus, Bettina and FlipKlijn (2005), “Stable matchings and preferences of couples.” Journal of Economic Theory, 121, 75-106. 10.1016/j.jet.2004.04.006 · Zbl 1098.91092
[32] 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
[33] Kominers, Scott Duke (2012), “On the correspondence of contracts to salaries in (many‐to‐many) matching.” Games and Economic Behavior, 75, 984-989. 10.1016/j.geb.2011.12.002 · Zbl 1239.91110
[34] McCartney, Scott (2013), “Flier auctions: Better seats, going once, going twice….” The Wall Street Journal. Available at http://www.wsj.com/articles/SB10001424127887323335404578442702374097108.
[35] Ostrovsky, Michael (2008), “Stability in supply chain networks.” American Economic Review, 98, 897-923.
[36] 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.
[37] 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.
[38] Peranson, Elliott (2014), “Issues in real‐world matching market design.” Presented at the Jerusalem Summer School in Economic Theory. Available at https://www.youtube.com/watch?v=gWNHNm5eado.
[39] Roth, Alvin E. and MarildaSotomayor (1989), “The college admissions problem revisited.” Econometrica, 57, 559-570. 10.2307/1911052 · Zbl 0668.90004
[40] Schlegel, Jan Christoph (2015), “Contracts versus salaries in matching: A general result.” Journal of Economic Theory, 159, 552-573. 10.1016/j.jet.2015.07.015 · Zbl 1330.91118
[41] Service Academy Forums (2012), “How does ROTC cadet receive designated branch?” Available at http://www.serviceacademyforums.com/showthread.php?t=26435.
[42] Sönmez, Tayfun (2013), “Bidding for army career specialties: Improving the ROTC branching mechanism.” Journal of Political Economy, 121, 186-219.
[43] 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
[44] Ueda, Suguru, DanielFragiadakis, AtsushiIwasaki, PeterTroyan, and MakotoYokoo (2012), “Strategy‐proof mechanisms for two‐sided matching with minimum and maximum quotas.” In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems, Vol. 3, 1327-1328, ACM, New York.
[45] Westkamp, Alexander (2013), “An analysis of the German university admissions system.” Economic Theory, 53, 561-589. 10.1007/s00199-012-0704-4 · Zbl 1278.91108
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.