17 December 2012, Computational Social Choice Seminar, Femke Bekius

Abstract

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 http://www.illc.uva.nl/~ulle/seminar/ or contact Ulle Endriss (ulle.endriss at uva.nl).