Consider a version of the stable matching problem where there are n students and
ID: 3749946 • Letter: C
Question
Consider a version of the stable matching problem where there are n students and n colleges as before. Assume each student ranks the colleges (and vice versa), but now we allow ties in the ranking. In other words, we could have a school that is indifferent two students s1 and s2, but prefers either of them over some other student s3 (and vice versa). We say a student s prefers college c1 to c2 if c1 is ranked higher on the s’s preference list andc1 and c2 are not tied.
(a) Strong Instability. A strong instability in a matching is a student-college pair, each of which prefer each other to their current pairing. In other words, neither is indifferent about the switch. Does there always exist a matching with no strong instability? Either give an example of a set of colleges and students with preference lists for which every perfect matchings has a strong instability; or give an algorithm that is guaranteed to find a matching with no strong instability and prove that it is correct.
(b) Weak Instability. A weak instability in a matching is a student-college pair where one party prefers the other, and the other may be indifferent. Formally, a student s and a college c with pairs c and s form a weak instability if either
• s prefers c to c and c either prefers s to s or is indifferent between s and s.
• c prefers s to s and s either prefers c to c or is indifferent between c and c.
In other words, the pairing between c and s is either preferred by both, or preferred by one while the other is indifferent. Does there always exist a perfect matching with no weak instability? Either give an example of a set of colleges and students with preference lists for which every perfect matching has a weak instability; or give an algorithm that is guaranteed to find a perfect matching with no weak instability.
Explanation / Answer
a)Yes, even for cases where we allow ties in preference lists of students and colleges, if we run the following algorithm, it will always find a a matching with no strong disabilities :
The algorithms is same as the stable matching algorithm used for preference lists without a tie, except for the fact that in the new scenario (preference lists with ties), it uses a scheme to break the ties. For example, let’s assume the algorithm uses lexicography to break the ties. If two colleges are equally preferred by a student, then the college name which is lexicographically smaller will be chosen by the algorithm as the preferred college among the two. Similarly, if two students are equally preferred by a college, then the student with lexicographically smaller name will be treated as the more preferred one.
Proof of correctness: The algorithm is identical to the stable matching algorithm if lexicographical tie-breaking is allowed. Hence, there won’t be any instability. If any strong instability is created because of the removal of lexicographical preference after the pairs are created, then re-adding the lexicographical preference is not going to eliminate the instability (e.g, if a student prefers one college over the other without lexicographical tie-breaking, then the lexicographical tie-breaker does not apply to the college pair, since they are not tied in the preference list), because preference will not be reversed. Hence, if there are strong instabilities with the tied lists, then there has to be strong instabilities in matching with the lexicographical scheme, which is impossible since the algorithm with lexicographical tie-breaker runs like normal stable matching algorithm and only produces matching without strong instability.
b)No, it might not always be possible to achieve perfect matching without weak instabilities. For example, let there be 2 students s1 and s2 and two colleges c1 and c2. s1, s2 both prefer c1 over c2, but c1 is indifferent about s1 and s2. In this case, whoever is paired with c2, will prefer c1 over its own college. But,c1 has no preference between s1 and s2. Hence the student paired with c2 will form a weak instability together with c1.