Institute for Logic, Language and Computation

17 December 2012, Computational Social Choice Seminar, Femke Bekius

Speaker: Femke Bekius
Title: College Admissions with Stable Score-Limits
Date: Monday 17 December 2012
Time: 11:00
Location: Room B0.209, Science Park 904, Amsterdam


The Gale-Shapley algorithm provides a stable matching between two sets of elements given the preferences over each element in the other set. Assigning students to colleges is a real life-example where the Gale-Shapley algorithm is used. In this case an additional factor, the examination-scores of the students have to be taken into account. If students have the same scores, ties can occur. Different policies are used to break these ties. In Hungary, for example, the equal treatment policy is used, i.e., students with the same score are either all accepted or all rejected. Whether the last group of students with the same score should be accepted or rejected corresponds to the concepts of H-stable and L-stable score-limits. The college-oriented and applicant-oriented algorithms are natural extensions of the Gale-Shapley algorithm and produce H-stable and L-stable score-limits. Moreover, comparison of the score-limits shows that the applicant-oriented algorithm gives lower score-limits than the college-oriented one, and L-stable score-limits are lower than the H-stable score-limits. To express the "degree of happiness" of the students and the colleges we extend the model and formalize social welfare for students and colleges separately.

For more information, see or contact Ulle Endriss ().

The websites of the UvA make use of cookiesThis site uses cookies More informationMore info Hide this message XHide X