Legal Assignments and Fast EADAM with Consent via Classic Theory of Stable Matchings

References

• Abdulkadiroğlu A, Sönmez T (2003) School choice: A mechanism design approach. Amer. Econom. Rev. 93(3):729–747.Crossref, Google Scholar
• Abdulkadiroğlu A, Che YK, Yasuda Y (2015) Expanding “choice” in school choice. Amer. Econom. J. Microeconomics 7(1):1–42.Crossref, Google Scholar
• Abdulkadiroğlu A, Pathak PA, Roth AE (2009) Strategy-proofness vs. efficiency in matching with indifferences: Redesigning the NYC high school match. Amer. Econom. Rev. 99(5):1954–1978.Crossref, Google Scholar
• Afacan MO, Aliog¨ullari ZH, Barlo M (2017) Sticky matching in school choice. Econom. Theory 64(3):509–538.Crossref, Google Scholar
• Ashlagi I, Nikzad A (2020) What matters in school choice tie-breaking? How competition guides design. J. Econom. Theory 190:105120.Google Scholar
• Baïou M, Balinski M (2004) Student admissions and faculty recruitment. Theoretical Comput. Sci. 322(2):245–265.Crossref, Google Scholar
• Bando K (2014) On the existence of a strictly strong Nash equilibrium under the student-optimal deferred acceptance algorithm. Games Econom. Behav. 87:269–287.Crossref, Google Scholar
• Bansal V, Agrawal A, Malhotra VS (2007) Polynomial time algorithm for an optimal stable assignment with multiple partners. Theoretical Comput. Sci. 379(3):317–328.Crossref, Google Scholar
• Benjamin AT, Converse C, Krieger HA (1995) How do I marry thee? Let me count the ways. Discrete Appl. Math. 59(3):285–292.Crossref, Google Scholar
• Birkhoff G (1937) Rings of sets. Duke Math. J. 3(3):443–454.Crossref, Google Scholar
• Dur U, Gitmez AA Yilmaz O (2019) School choice under partial fairness. Theoret. Econom. 14(4):1309–1346.Google Scholar
• Ehlers L (2007) von Neumann–Morgenstern stable sets in matching problems. J. Econom. Theory 134(1):537–547.Crossref, Google Scholar
• Ehlers L, Morrill T (2020) (Il)legal assignments in school choice. Rev. Econom. Stud. 87(4):1837–1875.Crossref, Google Scholar
• Erdil A, Ergin H (2008) What’s the matter with tie-breaking? Improving efficiency in school choice. Amer. Econom. Rev. 98(3):669–689.Crossref, Google Scholar
• Ergin HI (2002) Efficient resource allocation on the basis of priorities. Econometrica 70(6):2489–2497.Crossref, Google Scholar
• Faenza Y, Zhang X (2020) Affinely representable lattices, stable matchings, and choice functions. Singh M, Williamson D, eds. Proc. IPCO 2021 (Springer, Cham), 89–103.Google Scholar
• Gale D, Shapley LS (1962) College admissions and the stability of marriage. Amer. Math. Monthly 69(1):9–15.Crossref, Google Scholar
• Gusfield D (1987) Three fast algorithms for four problems in stable marriage. SIAM J. Comput. 16(1):111–128.Crossref, Google Scholar
• Gusfield D, Irving RW (1989) The Stable Marriage Problem: Structure and Algorithms (MIT Press, Cambridge, MA).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
• Karlin AR, Gharan SO, Weber R (2018) A simply exponential upper bound on the maximum number of stable matchings. Henzinger M, ed. Proc. 50th Annual ACM SIGACT Sympos. Theory Comput. (ACM, New York), 920–925.Google Scholar
• Kesten O (2010) School choice with consent. Quart. J. Econom. 125(3):1297–1348.Crossref, Google Scholar
• Kloosterman A, Troyan P (2016) Efficient and Essentially Stable Assignments (University of Virginia).Google Scholar
• Knuth DE (1976) Mariages Stables et Leurs Relations avec d’autres Problèmes Combinatoires: Introduction à l’analyse Mathématique des Algorithmes (Presses de l’Université de Montréal, Montréal).Google Scholar
• Kunysz A, Paluch K, Ghosal P (2016) Characterisation of strongly stable matchings. Krauthgamer R, ed. Proc. 27th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 107–119.Google Scholar
• Manlove DF (2002) The structure of stable marriage with indifference. Discrete Appl. Math. 122(1–3):167–181.Crossref, Google Scholar
• Manlove DF (2013) Algorithmics of Matching Under Preferences, vol. 2 (World Scientific).Crossref, Google Scholar
• Morrill T (2016) Which school assignments are legal? Technical report, University of North Carolina.Google Scholar
• Narita Y (2016) Match or mismatch: Learning and inertia in school choice. Working paper, Yale University.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, Peranson E (1999) The redesign of the matching market for American physicians: Some engineering aspects of economic design. Amer. Econom. Rev. 89(4):748–780.Crossref, Google Scholar
• Roth AE, Rothblum UG (1999) Truncation strategies in matching markets—In search of advice for participants. Econometrica 67(1):21–43.Crossref, Google Scholar
• Roth AE, Sotomayor M (1992) Two-sided matching. Handbook of Game Theory with Economic Applications, vol. 1, (Amsterdam), 485–541.Google Scholar
• Roth AE, Sönmez T, Ünver MU (2005) Pairwise kidney exchange. J. Econom. Theory 125(2):151–188.Crossref, Google Scholar
• Tang Q, Yu J (2014) A new perspective on Kesten’s school choice with consent idea. J. Econom. Theory 154:543–561.Crossref, Google Scholar
• Tang Q, Zhang Y (2021) Weak stability and Pareto efficiency in school choice. Econom. Theory 71(2):533–552.Google Scholar
• Von Neumann J, Morgenstern O (1953) Theory of Games and Economic Behavior. 3rd ed. (Princeton University Press, Princeton, NJ).Google Scholar
• Wako J (2010) A polynomial-time algorithm to find von Neumann-Morgenstern stable matchings in marriage games. Algorithmica 58(1):188–220.Crossref, Google Scholar