Computing at Glasgow University
Paper ID: 9150
DCS Tech Report Number: TR-2009-303

The College Admissions problem with lower and common quotas
Biró,P. Fleiner,T. Irving,R.W. Manlove,D.F.

Publication Type: Tech Report (internal)
Appeared in: DCS Technical Report Series
Page Numbers : 1-30
Publisher: Dept of Computing Science, University of Glasgow
Year: 2009

We study two generalised stable matching problems motivated by the current matching scheme used in the higher education sector in Hungary. The first problem is an extension of the College Admissions problem in which the colleges have lower quotas as well as the normal upper quotas. Here, we show that a stable solution may not exist and we prove that the problem of determining whether one does is NP-complete in general. The second problem is a different extension in which, as usual, individual colleges have upper quotas, but in addition, certain bounded subsets of colleges have common quotas smaller than the sum of their individual quotas. Again, we show that a stable matching may not exist and the related decision problem is NP-complete. On the other hand we prove that, when the bounded sets form a nested set system, a stable solution can be found by generalising, in non-trivial ways, both the applicant-oriented and college-oriented versions of the classical Gale-Shapley algorithm. Finally, we present an alternative view of this nested case using the concept of choice functions, and with the aid of a matroid model we establish some interesting structural results for this case.

Keywords: stable matching

PDF Bibtex entry Endnote XML