101. College admissions with ties and common quotas: Integer programming approach
- Author
-
Ágoston, Kolos Csaba, Biró, Péter, Kováts, Endre, and Jankó, Zsuzsanna
- Subjects
College admissions ,Business, general ,Business ,Business, international - Abstract
Keywords Assignment; Stable matching; College admission; Distributional constraints; Integer programming Abstract Admission to universities is organised in a centralised scheme in Hungary. In this paper we investigate two major specialities of this application: ties and common quotas. A tie occur when some students have the same score at a programme. If not enough seats are available for the last tied group of applicants at a programme then there are three reasonable policies used in practice: 1) all must be rejected, as in Hungary 2) all can be accepted, as in Chile 3) a lottery decides which students are accepted from this group, as in Ireland. Even though student-optimal stable matchings can be computed efficiently for each of the above three cases, we developed (mixed) integer programming (IP) formulations for solving these problems, and compared the solutions obtained by the three policies for a real instance of the Hungarian application from 2008. In the case of Hungary common quotas arise from the faculty quotas imposed on their programmes and from the national quotas set for state-financed students in each subject. The overlapping structure of common quotas makes the computational problem of finding a stable solution NP-hard, even for strict rankings. In the case of ties and common quotas we propose two reasonable stable solution concepts for the Hungarian and Chilean policies. We developed (mixed) IP formulations for solving these stable matching problems and tested their performance on the large scale real instance from 2008 and also for one from 2009 under two different assumptions. We demonstrate that the most general case is also solvable in practice by IP technique. Author Affiliation: (a) Department of Operations Research and Actuarial Sciences, Corvinus University of Budapest, H-1093, Fovám tér 13-15., Budapest, Hungary (b) Institute of Economics, Research Centre for Economic and Regional Studies, Hungarian Academy of Sciences, H-1097, Tóth Kálmán u. 4., Budapest, Hungary (c) Budapest University of Technology and Economics, H-1111, Muegyetem rakpart 3., Budapest, Hungary * Corresponding author. Article History: Received 28 January 2020; Accepted 19 August 2021 (footnote)[white star] Earlier results of this paper have been presented in two conference papers [5,6]. (footnote)1 Supported by the Hungarian Academy of Sciences under its Momentum Programme (Engineering Economics in Matching Markets, no. LP2021-2), and by the Hungarian Scientific Research Fund -- OTKA (no. K129086). Byline: Kolos Csaba Ágoston [kolos.agoston@uni-corvinus.hu] (a), Péter Biró [peter.biro@krtk.mta.hu] (1,*,a,b), Endre Kováts [endre.kovats.92@gmail.com] (c), Zsuzsanna Jankó [zsuzsanna.janko@uni-corvinus.hu] (a,b)
- Published
- 2022
- Full Text
- View/download PDF