{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,8]],"date-time":"2025-12-08T07:15:22Z","timestamp":1765178122494,"version":"3.37.3"},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2022,12,19]],"date-time":"2022-12-19T00:00:00Z","timestamp":1671408000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,12,19]],"date-time":"2022-12-19T00:00:00Z","timestamp":1671408000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003549","name":"Hungarian Scientific Research Fund","doi-asserted-by":"publisher","award":["K128611"],"award-info":[{"award-number":["K128611"]}],"id":[{"id":"10.13039\/501100003549","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003825","name":"Magyar Tudom\u00e1nyos Akad\u00e9mia","doi-asserted-by":"publisher","award":["LP2021-2"],"award-info":[{"award-number":["LP2021-2"]}],"id":[{"id":"10.13039\/501100003825","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2024,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We introduce a new two-sided stable matching problem that describes the summer internship matching practice of an Australian university. The model is a case between two models of Kamada and Kojima on matchings with distributional constraints. We study three solution concepts, the strong and weak stability concepts proposed by Kamada and Kojima, and a new one in between the two, called cutoff stability. Kamada and Kojima showed that a strongly stable matching may not exist in their most restricted model with disjoint regional quotas. Our first result is that checking its existence is NP-hard. We then show that a cutoff stable matching exists not just for the summer internship problem but also for the general matching model with arbitrary heredity constraints. We present an algorithm to compute a cutoff stable matching and show that it runs in polynomial time in our special case of summer internship model. However, we also show that finding a maximum size cutoff stable matching is NP-hard, but we provide a Mixed Integer Linear Program formulation for this optimisation problem.<\/jats:p>","DOI":"10.1007\/s10107-022-01917-1","type":"journal-article","created":{"date-parts":[[2022,12,19]],"date-time":"2022-12-19T14:03:39Z","timestamp":1671458619000},"page":"247-269","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Cutoff stability under distributional constraints with an application to summer internship matching"],"prefix":"10.1007","volume":"203","author":[{"given":"Haris","family":"Aziz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anton","family":"Baychkov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7011-3463","authenticated-orcid":false,"given":"P\u00e9ter","family":"Bir\u00f3","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,12,19]]},"reference":[{"issue":"3","key":"1917_CR1","doi-asserted-by":"publisher","first-page":"729","DOI":"10.1257\/000282803322157061","volume":"93","author":"A Abdulkadiro\u011flu","year":"2003","unstructured":"Abdulkadiro\u011flu, A., S\u00f6nmez, T.: School choice: a mechanism design approach. Am. Econ. Rev. 93(3), 729\u2013747 (2003)","journal-title":"Am. Econ. Rev."},{"issue":"3","key":"1917_CR2","doi-asserted-by":"publisher","first-page":"729","DOI":"10.1257\/000282803322157061","volume":"93","author":"A Abdulkadiro\u011flu","year":"2003","unstructured":"Abdulkadiro\u011flu, A., S\u00f6nmez, T.: School choice: a mechanism design approach. Am. Econ. Rev. 93(3), 729\u2013747 (2003)","journal-title":"Am. Econ. Rev."},{"issue":"1","key":"1917_CR3","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/j.jda.2006.03.006","volume":"5","author":"DJ Abraham","year":"2007","unstructured":"Abraham, D.J., Irving, R.W., Manlove, D.: Two algorithms for the student-project allocation problem. J. Discrete Algorithms 5(1), 73\u201390 (2007)","journal-title":"J. Discrete Algorithms"},{"issue":"4","key":"1917_CR4","doi-asserted-by":"publisher","first-page":"1371","DOI":"10.1007\/s10878-016-0085-x","volume":"32","author":"KC \u00c1goston","year":"2016","unstructured":"\u00c1goston, K.C., Bir\u00f3, P., McBride, I.: Integer programming methods for special college admissions problems. J. Comb. Optim. 32(4), 1371\u20131399 (2016)","journal-title":"J. Comb. Optim."},{"key":"1917_CR5","first-page":"59","volume":"5","author":"KC \u00c1goston","year":"2018","unstructured":"\u00c1goston, K.C., Bir\u00f3, P., Sz\u00e1nt\u00f3, R.: Stable project allocation under distributional constraints. Oper. Res. Perspect. 5, 59\u201368 (2018)","journal-title":"Oper. Res. Perspect."},{"key":"1917_CR6","volume-title":"Network Flows: Theory, Algorithms, and Applications","author":"RK Ahuja","year":"1993","unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms, and Applications. Prentice Hall, Hoboken (1993)"},{"key":"1917_CR7","unstructured":"Artemov, G., Che, Y.-K., He, Y.: Strategic \u2018mistakes\u2019: implications for market design research. Work. Pap., Melbourne Univ., Melbourne, Aust (2017)"},{"issue":"5","key":"1917_CR8","doi-asserted-by":"publisher","first-page":"1235","DOI":"10.1086\/687476","volume":"124","author":"EM Azevedo","year":"2016","unstructured":"Azevedo, E.M., Leshno, J.D.: A supply and demand framework for two-sided matching markets. J. Polit. Econ. 124(5), 1235\u20131268 (2016)","journal-title":"J. Polit. Econ."},{"key":"1917_CR9","unstructured":"Aziz, H., Chen, J., Gaspers, S., Sun, Z.: Stability and pareto optimality in refugee allocation matchings. In: Proceedings\u00a0of 17th AAMAS Conference, pp. 964\u2013972 (2018)"},{"key":"1917_CR10","unstructured":"Aziz, H., Gaspers, S., Sun, Z., Walsh, T.: From matching with diversity constraints to matching with regional quotas. In: Proceedings\u00a0of 18th AAMAS Conference, pp. 377\u2013385 (2019)"},{"key":"1917_CR11","unstructured":"Aziz, H., Baychkov, A., Bir\u00f3, P.: Summer internship matching with funding constraints. In: Proceedings\u00a0of 19th AAMAS Conference, pp. 97\u2013104 (2020)"},{"key":"1917_CR12","doi-asserted-by":"crossref","unstructured":"Aziz, H., Bir\u00f3, P., Yokoo, M.: Matching market design with constraints. In: Proceedings\u00a0of 36th AAAI Conference, pp 12308\u201312316 (2022)","DOI":"10.1609\/aaai.v36i11.21495"},{"issue":"3","key":"1917_CR13","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1007\/s101070050004","volume":"87","author":"M Ba\u00efou","year":"2000","unstructured":"Ba\u00efou, M., Balinski, M.: The stable admissions polytope. Math. Program. 87(3), 427\u2013439 (2000)","journal-title":"Math. Program."},{"issue":"1","key":"1917_CR14","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1006\/jeth.1998.2469","volume":"84","author":"M Balinski","year":"1999","unstructured":"Balinski, M., S\u00f6nmez, T.: A tale of two mechanisms: student placement. J. Econ. Theory 84(1), 73\u201394 (1999)","journal-title":"J. Econ. Theory"},{"key":"1917_CR15","unstructured":"Bir\u00f3, P.: Applications of matching models under preferences. In: Trends in Computational Social Choice, pp. 345\u2013373. AI Access Foundation (2017)"},{"issue":"4","key":"1917_CR16","doi-asserted-by":"publisher","first-page":"727","DOI":"10.1007\/s10100-013-0320-9","volume":"23","author":"P Bir\u00f3","year":"2015","unstructured":"Bir\u00f3, P., Kiselgof, S.: College admissions with stable score-limits. CEJOR 23(4), 727\u2013741 (2015)","journal-title":"CEJOR"},{"issue":"34\u201336","key":"1917_CR17","doi-asserted-by":"publisher","first-page":"3136","DOI":"10.1016\/j.tcs.2010.05.005","volume":"411","author":"P Biro","year":"2010","unstructured":"Biro, P., Fleiner, T., Irving, R.W., Manlove, D.F.: The college admissions problem with lower and common quotas. Theor. Comput. Sci. 411(34\u201336), 3136\u20133153 (2010)","journal-title":"Theor. Comput. Sci."},{"key":"1917_CR18","doi-asserted-by":"crossref","unstructured":"Bir\u00f3, P., Manlove, D.F., McBride, I.: The hospitals\/residents problem with couples: complexity and integer programming models. In: International symposium on experimental algorithms, pp. 10\u201321. Springer (2014)","DOI":"10.1007\/978-3-319-07959-2_2"},{"key":"1917_CR19","doi-asserted-by":"publisher","DOI":"10.1016\/j.econlet.2022.110675","volume":"217","author":"Sung-Ho Cho","year":"2022","unstructured":"Cho, Sung-Ho., Koshimura, Miyuki, Mandal, Pinaki, Yahiro, Kentaro, Yokoo, Makoto: Impossibility of weakly stable and strategy-proof mechanism. Econ. Lett. 217, 110675 (2022)","journal-title":"Econ. Lett."},{"key":"1917_CR20","unstructured":"Delacr\u00e9taz, D., Kominers, S.D., Teytelboym, A.: Refugee resettlement. (2016)"},{"issue":"2","key":"1917_CR21","doi-asserted-by":"publisher","first-page":"426","DOI":"10.1016\/j.ejor.2019.03.017","volume":"277","author":"M Delorme","year":"2019","unstructured":"Delorme, M., Garc\u00eda, S., Gondzio, J., Kalcsics, J., Manlove, D., Pettersson, W.: Mathematical models for stable matching problems with ties and incomplete lists. Eur. J. Oper. Res. 277(2), 426\u2013441 (2019)","journal-title":"Eur. J. Oper. Res."},{"issue":"8","key":"1917_CR22","doi-asserted-by":"publisher","first-page":"2679","DOI":"10.1257\/aer.20130929","volume":"105","author":"F Echenique","year":"2015","unstructured":"Echenique, F., Yenmez, M.B.: How to control controlled school choice. Am. Econ. Rev. 105(8), 2679\u201394 (2015)","journal-title":"Am. Econ. Rev."},{"issue":"1","key":"1917_CR23","doi-asserted-by":"publisher","first-page":"32","DOI":"10.3390\/a7010032","volume":"7","author":"T Fleiner","year":"2014","unstructured":"Fleiner, T., Jank\u00f3, Z.: Choice function-based two-sided markets: stability, lattice property, path independence and algorithms. Algorithms 7(1), 32\u201359 (2014)","journal-title":"Algorithms"},{"issue":"2","key":"1917_CR24","doi-asserted-by":"publisher","first-page":"863","DOI":"10.3982\/TE2195","volume":"12","author":"D Fragiadakis","year":"2017","unstructured":"Fragiadakis, D., Troyan, P.: Improving matching under hard distributional constraints. Theor. Econ. 12(2), 863\u2013908 (2017)","journal-title":"Theor. Econ."},{"issue":"1","key":"1917_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2841226","volume":"4","author":"D Fragiadakis","year":"2016","unstructured":"Fragiadakis, D., Iwasaki, A., Troyan, P., Ueda, S., Yokoo, M.: Strategyproof matching with minimum quotas. ACM Trans. Econ. Comput. 4(1), 1\u201340 (2016)","journal-title":"ACM Trans. Econ. Comput."},{"key":"1917_CR26","doi-asserted-by":"publisher","first-page":"977","DOI":"10.1007\/s10107-021-01722-2","volume":"195","author":"A Frank","year":"2021","unstructured":"Frank, A., Murota, K.: Decreasing minimization on m-convex sets: background and structures. Math. Program. 195, 977\u20131025 (2021)","journal-title":"Math. Program."},{"issue":"1","key":"1917_CR27","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1080\/00029890.1962.11989827","volume":"69","author":"D Gale","year":"1962","unstructured":"Gale, D., Shapley, L.S.: College admissions and the stability of marriage. Am. Math. Mon. 69(1), 9\u201315 (1962)","journal-title":"Am. Math. Mon."},{"issue":"1","key":"1917_CR28","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1080\/00029890.1962.11989827","volume":"69","author":"D Gale","year":"1962","unstructured":"Gale, D., Shapley, L.S.: College admissions and the stability of marriage. Am. Math. Mon. 69(1), 9\u201315 (1962)","journal-title":"Am. Math. Mon."},{"key":"1917_CR29","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/j.artint.2016.02.002","volume":"235","author":"M Goto","year":"2016","unstructured":"Goto, M., Iwasaki, A., Kawasaki, Y., Kurata, R., Yasuda, Y., Yokoo, M.: Strategyproof matching with regional minimum and maximum quotas. Artif. Intell. 235, 40\u201357 (2016)","journal-title":"Artif. Intell."},{"issue":"2","key":"1917_CR30","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1257\/mic.20160124","volume":"9","author":"M Goto","year":"2017","unstructured":"Goto, M., Kojima, F., Kurata, R., Tamura, A., Yokoo, M.: Designing matching mechanisms under general distributional constraints. Am. Econ. J. Microecon. 9(2), 226\u2013262 (2017)","journal-title":"Am. Econ. J. Microecon."},{"key":"1917_CR31","unstructured":"Guillen, P., Kesten, O., Kiefer, A., Melatos, M.: A field evaluation of a matching mechanism: University applicant behaviour in Australia. Technical report (2020)"},{"issue":"3","key":"1917_CR32","doi-asserted-by":"publisher","first-page":"30-es","DOI":"10.1145\/1273340.1273346","volume":"3","author":"MM Halld\u00f3rsson","year":"2007","unstructured":"Halld\u00f3rsson, M.M., Iwama, K., Miyazaki, S., Yanagisawa, H.: Improved approximation results for the stable marriage problem. ACM Trans. Algorithms (TALG) 3(3), 30-es (2007)","journal-title":"ACM Trans. Algorithms (TALG)"},{"key":"1917_CR33","doi-asserted-by":"crossref","unstructured":"Ismaili, A., Yamaguchi, T., Yakoo, M.: Student-project-resource allocation: complexity of the symmetric case. In: PRIMA 2018: Principles and Practice of Multi-Agent Systems. Springer, pp. 226\u2013241 (2018)","DOI":"10.1007\/978-3-030-03098-8_14"},{"key":"1917_CR34","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1613\/jair.1.11582","volume":"65","author":"A Ismaili","year":"2019","unstructured":"Ismaili, A., Hamada, N., Zhang, Y., Suzuki, T., Yokoo, M.: Weighted matching markets with budget constraints. J. Artif. Intell. Res. 65, 393\u2013421 (2019)","journal-title":"J. Artif. Intell. Res."},{"issue":"1","key":"1917_CR35","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1257\/aer.20101552","volume":"105","author":"Y Kamada","year":"2015","unstructured":"Kamada, Y., Kojima, F.: Efficient matching under distributional constraints: theory and applications. Am. Econ. Rev. 105(1), 67\u201399 (2015)","journal-title":"Am. Econ. Rev."},{"issue":"5","key":"1917_CR36","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1257\/aer.p20171047","volume":"107","author":"Y Kamada","year":"2017","unstructured":"Kamada, Y., Kojima, F.: Recent developments in matching with constraints. Am. Econ. Rev. 107(5), 200\u2013204 (2017)","journal-title":"Am. Econ. Rev."},{"key":"1917_CR37","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/j.jet.2016.12.006","volume":"168","author":"Y Kamada","year":"2017","unstructured":"Kamada, Y., Kojima, F.: Stability concepts in matching under distributional constraints. J. Econ. Theory 168, 107\u2013142 (2017)","journal-title":"J. Econ. Theory"},{"issue":"2","key":"1917_CR38","doi-asserted-by":"publisher","first-page":"761","DOI":"10.3982\/TE2717","volume":"13","author":"Y Kamada","year":"2018","unstructured":"Kamada, Y., Kojima, F.: Stability and strategy-proofness for matching with constraints: a necessary and sufficient condition. Theor. Econ. 13(2), 761\u2013793 (2018)","journal-title":"Theor. Econ."},{"key":"1917_CR39","unstructured":"Kamada, Y., Kojima, F.: Fair matching under constraints: theory and applications. Rev. Econ. Studies. (2020)"},{"key":"1917_CR40","doi-asserted-by":"crossref","unstructured":"Kawase, Y., Iwasaki, A.: Near-feasible stable matchings with budget constraints. In: Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI-17, pp. 242\u2013248 (2017)","DOI":"10.24963\/ijcai.2017\/35"},{"key":"1917_CR41","doi-asserted-by":"crossref","unstructured":"Kawase, Y., Iwasaki, A.: Approximately stable matchings with budget constraints. In: Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), pp. 1113\u20131120 (2018)","DOI":"10.1609\/aaai.v32i1.11470"},{"key":"1917_CR42","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1613\/jair.5297","volume":"58","author":"R Kurata","year":"2017","unstructured":"Kurata, R., Hamada, N., Iwasaki, A., Yokoo, M.: Controlled school choice with soft bounds and overlapping types. J. Artif. Intell. Res. 58, 153\u2013184 (2017)","journal-title":"J. Artif. Intell. Res."},{"key":"1917_CR43","doi-asserted-by":"crossref","unstructured":"Kwanashie, A., Manlove, D.F.: An integer programming approach to the hospitals\/residents problem with ties. In: Operations Research Proceedings 2013. Springer, pp. 263\u2013269 (2014)","DOI":"10.1007\/978-3-319-07001-8_36"},{"issue":"6","key":"1917_CR44","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/0020-0190(78)90016-9","volume":"7","author":"V Malhotra","year":"1962","unstructured":"Malhotra, V., Kumar, M.P., Maheshwari, S.N.: An $${O}(|{V}|^3)$$ algorithm for finding maximum flows in networks. Inf. Process. Lett. 7(6), 277\u2013278 (1962)","journal-title":"Inf. Process. Lett."},{"key":"1917_CR45","doi-asserted-by":"publisher","DOI":"10.1142\/8591","volume-title":"Algorithmics of Matching Under Preferences","author":"DF Manlove","year":"2013","unstructured":"Manlove, D.F.: Algorithmics of Matching Under Preferences. World Scientific Publishing Company, Singapore (2013)"},{"issue":"1\u20132","key":"1917_CR46","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/S0304-3975(01)00206-7","volume":"276","author":"DF Manlove","year":"2002","unstructured":"Manlove, D.F., Irving, R.W., Iwama, K., Miyazaki, S., Morita, Y.: Hard variants of stable marriage. Theor. Comput. Sci. 276(1\u20132), 261\u2013279 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"1917_CR47","doi-asserted-by":"crossref","unstructured":"Roth, A.E.: On the allocation of residents to rural hospitals: a general property of two-sided matching markets. Econometrica 425\u2013427 (1986)","DOI":"10.2307\/1913160"},{"key":"1917_CR48","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1007\/s00182-008-0117-6","volume":"36","author":"AE Roth","year":"2008","unstructured":"Roth, A.E.: Deferred acceptance algorithms: history, theory, practice, and open questions. Intern. J. Game Theory 36, 537\u2013569 (2008)","journal-title":"Intern. J. Game Theory"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-022-01917-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-022-01917-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-022-01917-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,9]],"date-time":"2024-02-09T18:08:21Z","timestamp":1707502101000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-022-01917-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,19]]},"references-count":48,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2024,1]]}},"alternative-id":["1917"],"URL":"https:\/\/doi.org\/10.1007\/s10107-022-01917-1","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2022,12,19]]},"assertion":[{"value":"10 March 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 December 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 December 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}