Description

1 Stable Matching
Consider the set of candidates C ={1, 2, 3} and the set of jobs J ={A, B,C} with the following preferences.
C J J C
1 A B C A 2 1 3
2 B A C B 1 2 3
3 A B C C 1 2 3
Run the applicant propose-and-reject algorithm on this example. How many days does it take and what is the resulting pairing? (Show your work)
2 Good, Better, Best
In a particular instance of the stable marriage problem with n applicants and n jobs, it turns out that there are exactly three distinct stable matchings, S1, S2, and S3. Also, each applicant m has a different partner in the three matchings. Therefore each applicant has a clear preference ordering of the three matchings (according to the ranking of his partners in his preference list). Now, suppose for applicant m1, this order is S1 > S2 > S3.
Prove that every applicant has the same preference ordering S1 > S2 > S3.
Hint: Recall that a applicant-optimal matching always exists and can be generated using applicant proposes matching algorithm. By reversing the roles of stable matching algorithm, what other matching can we generate?