1 Stable Marriage
Consider the set of men M = {1, 2, 3} and the set of women W = {A, B,C} with the following preferences.
Men
Women
Women
Men
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 traditional propose-and-reject algorithm on this example. How many days does it take and what is the resulting pairing? (Show your work.)
2 Universal Preference
Suppose that preferences in a stable marriage instance are universal: all n men share the preferences W1 W2 ··· Wn and all women share the preferences M1 M2 ··· Mn.
(a) What pairing do we get from running the algorithm with men proposing? Can you prove this happens for all n?
(b) What pairing do we get from running the algorithm with women proposing?
(c) What does this tell us about the number of stable pairings?
CS 70, Fall 2018, DIS 2A 1
3 Propose-and-Reject Proofs
Prove the following statements about the traditional propose-and-reject algorithm.
(a) In any execution of the algorithm, if a woman receives a proposal on day i, then she receives some proposal on every day thereafter until termination.
(b) In any execution of the algorithm, if a woman receives no proposal on day i, then she receives no proposal on any previous day j, 1 ≤ j < i.
(c) In any execution of the algorithm, there is at least one woman who only receives a single proposal. (Hint: use the parts above!)
