×

Strategyproof matching with regional minimum and maximum quotas. (English) Zbl 1354.91103

Summary: This paper considers matching problems with individual/regional minimum/maximum quotas. Although such quotas are relevant in many real-world settings, there is a lack of strategyproof mechanisms that take such quotas into account. We first show that without any restrictions on the regional structure, checking the existence of a feasible matching that satisfies all quotas is NP-complete. Then, assuming that regions have a hierarchical structure (i.e., a tree), we show that checking the existence of a feasible matching can be done in time linear in the number of regions. We develop two strategyproof matching mechanisms based on the Deferred Acceptance mechanism (DA), which we call Priority List based Deferred Acceptance with Regional minimum and maximum Quotas (PLDA-RQ) and Round-robin Selection Deferred Acceptance with Regional minimum and maximum Quotas (RSDA-RQ). When regional quotas are imposed, a stable matching may no longer exist since fairness and nonwastefulness, which compose stability, are incompatible. We show that both mechanisms are fair. As a result, they are inevitably wasteful. We show that the two mechanisms satisfy different versions of nonwastefulness respectively; each is weaker than the original nonwastefulness. Moreover, we compare our mechanisms with an artificial cap mechanism via simulation experiments, which illustrate that they have a clear advantage in terms of nonwastefulness and student welfare.

MSC:

91B68 Matching models

References:

[1] Aygün, O.; Sönmez, T., Matching with contracts: comment, Am. Econ. Rev., 103, 2050-2051 (2013)
[2] Biro, P.; Fleiner, T.; Irving, R.; Manlove, D., The college admissions problem with lower and common quotas, Theor. Comput. Sci., 411, 3136-3153 (2010) · Zbl 1193.91099
[3] Braun, S.; Dwenger, N.; Kübler, D.; Westkamp, A., Implementing quotas in university admissions: an experimental analysis, Games Econ. Behav., 85, 232-251 (2014) · Zbl 1292.91135
[4] Ehlers, L.; Hafalir, I. E.; Yenmez, M. B.; Yildirim, M. A., School choice with controlled choice constraints: hard bounds versus soft bounds, J. Econ. Theory, 153, 648-683 (2014) · Zbl 1309.91102
[5] Fleiner, T., A fixed-point approach to stable matchings and some applications, Math. Oper. Res., 28, 103-126 (2003) · Zbl 1082.90096
[6] Fleiner, T.; Kamiyama, N., A matroid approach to stable matchings with lower quotas, (Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA-2012) (2012)), 135-142 · Zbl 1425.91341
[7] Fragiadakis, D.; Iwasaki, A.; Troyan, P.; Ueda, S.; Yokoo, M., Strategyproof matching with minimum quotas, ACM Trans. Econ. Comput., 4, Article 6 pp. (2015)
[8] Gale, D.; Shapley, L. S., College admissions and the stability of marriage, Am. Math. Mon., 69, 9-15 (1962) · Zbl 0109.24403
[9] Goto, M.; Hashimoto, N.; Iwasaki, A.; Kawasaki, Y.; Ueda, S.; Yasuda, Y.; Yokoo, M., Strategy-proof matching with regional minimum quotas, (Thirteenth International Conference on Autonomous Agents and Multiagent Systems (AAMAS-2014) (2014)), 1225-1232
[11] Goto, M.; Kojima, F.; Kurata, R.; Tamura, A.; Yokoo, M., Designing matching mechanisms under general distributional constraints, (Proceedings of the Sixteenth ACM Conference on Economics and Computation (EC-2015) (2015)), 259-260, the full version is available at
[12] Gul, F.; Stacchetti, E., Walrasian equilibrium with gross substitutes, J. Econ. Theory, 87, 95-124 (1999) · Zbl 0998.91010
[13] Hafalir, I. E.; Yenmez, M. B.; Yildirim, M. A., Effective affirmative action in school choice, Theor. Econ., 8, 325-363 (2013) · Zbl 1395.91344
[14] Hamada, K.; Iwama, K.; Miyazaki, S., The hospitals/residents problem with lower quotas, Algorithmica, 1-26 (2014)
[15] Hatfield, J. W.; Milgrom, P. R., Matching with contracts, Am. Econ. Rev., 95, 913-935 (2005)
[16] Huang, C. C., Classified stable matching, (Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA-2010) (2010)), 1235-1253 · Zbl 1288.05275
[18] Kamada, Y.; Kojima, F., Efficient matching under distributional constraints: theory and applications, Am. Econ. Rev., 105, 67-99 (2015)
[19] Kojima, F., School choice: impossibilities for affirmative action, Games Econ. Behav., 75, 685-693 (2012) · Zbl 1239.91039
[20] Kojima, F.; Tamura, A.; Yokoo, M., Designing matching mechanisms under constraints: an approach from discrete convex analysis, (Proceedings of the Seventh International Symposium on Algorithmic Game Theory (SAGT-2014) (2014)), the full version is available at
[22] Monte, D.; Tumennasan, N., Matching with quorum, Econ. Lett., 120, 14-17 (2013) · Zbl 1284.91417
[23] Roth, A. E., The college admissions problem is not equivalent to the marriage problem, J. Econ. Theory, 36, 277-288 (1985) · Zbl 0594.90002
[24] Roth, A. E.; Sotomayor, M. A.O., Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis, Econometric Society Monographs (1990), Cambridge University Press · Zbl 0726.90003
[25] Sönmez, T., Bidding for army career specialties: improving the ROTC branching mechanism, J. Polit. Econ., 121, 186-219 (2013)
[26] Sönmez, T.; Switzer, T. B., Matching with (branch-of-choice) contracts at the United States Military Academy, Econometrica, 81, 451-488 (2013) · Zbl 1274.91334
[27] Westkamp, A., An analysis of the German university admissions system, Econ. Theory, 53, 561-589 (2013) · Zbl 1278.91108
[28] Yokoi, Y., Matroidal choice functions, 1-27 (2014), Mathematical Engineering Technical Reports 2014-32
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.