Question

The Stable Matching Problem, as discussed in the text, assumes that all men and women have a fully ordered list of preferences. In this problem we will consider a version of the problem in which men and women can be indifferent between certain options. As before we have a set M of n men and a set W of n women. Assume each man and each woman ranks the members of the opposite gender, but now we allow ties in the ranking.

For example (with n = 4), a woman could say that m1 is ranked in first place; second place is a tie between m2 and m3 (she has no preference between them); and m4 is in last place. We will say that w prefers m to m0 if m is ranked higher than m0 on her preference list (they are not tied). With indifferences in the rankings, there could be two natural notions for stability. And for each, we can ask about the existence of stable matchings, as follows.

1 1. A strong instability in a perfect matching S consists of a man m and woman w, such that each of m and w prefers the other to their partner in S. Does there always exist a perfect matching with no strong instability?

Either give an example of a set of men and women with preference lists for which every perfect matching has a strong instability; or give an algorithm that is guaranteed to find a perfect matching with no strong instability and prove the guarantee.

2. A weak instability in a perfect matching S consists of a man m and a woman w such that their partners in S are w 0 and m0 , respectively, and one of the following holds:

• m prefers w to w 0 , and either w prefers m to m0 or is indifferent; or

• w prefers m to m0 , and m either prefers w to w 0 or is indifferent.

In other words, the pairing between m and w 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 men and women 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 and prove the guarantee.