1. (30+5 points) Variations on Stable Matching (a) (10 points) Consider a variant of stable matching in which at every point, either a free college or a free student can propose. As in the Gale-Shapley algorithm, proposals are done going down in the preference list, so that a proposer cannot repeat a proposal to the same partner. Show that this algorithm always terminates with a perfect matching, but not necessarily a stable one. (b) (5 points extra credit) Consider colleges A B, C and students 1, 2, 3, with preference lists: 1: ABCA: 231 2: BCA B: 31 2 3: CAB C: 1 2 3 How many of the six perfect matchings are stable? How many stable matchings can be obtained by a version of part (a) where colleges and students alternate proposing any party can start)? (c) (10 points) Now allow proposals also from matched parties. That is, on any turn, any college or student may propose to the next partner on its preference list if this is better than the current match (if any), and if the proposal is accepted, both the proposer's and the acceptor's former partner (if any) become free. Does the algorithm always terminate? Will it always produce a perfect matching? Will it always produce a stable matching? (Hint: a college c might not get a student s when s already has a better match, but be offered by s later if s becomes unmatched. Look at n = 3 first). (d) (10 points) Consider now an algorithm that starts with an arbitrary perfect matching of colleges to students. As long as the matching is not stable, choose an instability (c, s) and eliminate it, by matching c with s, and the former partners of c and s with one another. Show that this algorithm does not always terminate with a stable matching. (Hint: an example with n = 3 suffices). 1. (30+5 points) Variations on Stable Matching (a) (10 points) Consider a variant of stable matching in which at every point, either a free college or a free student can propose. As in the Gale-Shapley algorithm, proposals are done going down in the preference list, so that a proposer cannot repeat a proposal to the same partner. Show that this algorithm always terminates with a perfect matching, but not necessarily a stable one. (b) (5 points extra credit) Consider colleges A B, C and students 1, 2, 3, with preference lists: 1: ABCA: 231 2: BCA B: 31 2 3: CAB C: 1 2 3 How many of the six perfect matchings are stable? How many stable matchings can be obtained by a version of part (a) where colleges and students alternate proposing any party can start)? (c) (10 points) Now allow proposals also from matched parties. That is, on any turn, any college or student may propose to the next partner on its preference list if this is better than the current match (if any), and if the proposal is accepted, both the proposer's and the acceptor's former partner (if any) become free. Does the algorithm always terminate? Will it always produce a perfect matching? Will it always produce a stable matching? (Hint: a college c might not get a student s when s already has a better match, but be offered by s later if s becomes unmatched. Look at n = 3 first). (d) (10 points) Consider now an algorithm that starts with an arbitrary perfect matching of colleges to students. As long as the matching is not stable, choose an instability (c, s) and eliminate it, by matching c with s, and the former partners of c and s with one another. Show that this algorithm does not always terminate with a stable matching. (Hint: an example with n = 3 suffices)