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 of 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 would say that m1 is ranked in the 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 of stability. And for each, we can ask about the existence of stable matchings, as follows. A strong instability in a perfect matching S consists of a man m and a 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 instability? Either give an example of a set of men and women with preference lists for which each perfect matching has a strong instability; or given an algorithm that is guaranteed to find a perfect matching with no strong instability. 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 w either prefers m to m0 or is indifferent between these two choices; or w prefers m to m0 , and m either prefers w to w 0 or is indifferent between these two choices. 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 each perfect matching has a weak instability; or given an algorithm that is guaranteed to find a perfect matching with no weak instability.