Given hospitals, students, and their ranked lists, let ℎ be the stable matching output by the Gale - Shapely algorithm when hospitals propose to students and let Ms be the stable matching output by the Gale - Shapely algorithm when students propose to hospitals. Select the proof below that proves the following claim: if ℎ = , then there is a unique stable matching of hospitals with students.
a. The claim is false. There cannot be a unique stable matching since Mh matches each hospital with its best valid partner and Ms matches each hospital with its worst valid partner.
b. Recall that the Gale - Shapely algorithm outputs a stable matching. Also, note that there are only two cases: hospitals can propose to students or students can propose to hospitals. Hence, Mh and Ms are the only two possible matchings. Thus, since Mh = Ms , there is a unique stable matching of hospitals with students.
c. Assume to the contrary that Mh = Ms but there is some stable matching M other than Mh or Ms . This implies that there is a pair ℎ - s in Mh that is not contained in M . Recall that Mh is hospital - optimal and Ms is student - optimal. Since ℎ = , this means that is the best valid partner of ℎ and ℎ is the best valid partner of . Hence, ℎ prefers s over its partner in and prefers ℎ over its partner in . Therefore, ℎ - is an unstable pair with respect to , which contradicts the fact that is stable. This proves the claim.
d. Recall that Mh is hospital - optimal and Ms is student - optimal. This means that, for each pair h - s in Mh , is the best valid partner of ℎ and ℎ is the best valid partner ofs. This implies that there is a unique valid partner for each hospital, and so there is a unique stable matching of hospitals with students.