College admissions with ties and common quotas: Integer programming approach

Ágoston, Kolos Csaba, Biró, Péter, Kováts, Endre and Jankó, Zsuzsanna ORCID: (2021) College admissions with ties and common quotas: Integer programming approach. European Journal of Operational Research . DOI

PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader

Official URL:


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.

Item Type:Article
Uncontrolled Keywords:assignment, stable matching, college admission, distributional constraints, integer programming
ID Code:6841
Deposited By: MTMT SWORD
Deposited On:23 Sep 2021 10:35
Last Modified:23 Sep 2021 10:36

Repository Staff Only: item control page


Downloads per month over past year

View more statistics