2. (Rural Hospital Theorem) Consider an arbitrary marriage problem. Let fM be the mer proposing DA matching of this problem. Let fW be the women-proposing DA matchin of this problem. Let f be an arbitrary stable matching of this problem. We show via th following steps that the set of matched/unmatched agents at f is the same as that at fM an that at fW. In other words, the set of matched/unmatched agents remain unchanged acros all stable matchings. (a) Assume that man m1 is matched (i.e., is not single) at fW. Argue that man m1 prefer his outcome at fW to being single. (b) Argue that man m1 is matched at f. (Hint: Use the opposing interests result and th result in the previous step to argue that man m1 cannot be single at f.) (c) Argue that man m1 is matched at fM. (Hint: Use the optimality of men-proposing D. algorithm and the result in the previous step to argue that man m1 cannot be single a fM.) (d) Through the above steps, we can conclude that every man matched at fW is also matched at f, and every man matched at f is also matched at fM. Provide similar arguments to show that every woman matched at fM is also matched at f, and every woman matched at f is also matched at fW. (e) Argue that the set of matched men at fM contains the set of matched men at f which further contains the set of matched men at fW. Similarly, argue that the set of matched women at fW contains the set of matched women at f which further contains the set of matched women at fM. (f) Argue that the number of matched men at fM is the same as the number of matched men at f which is the same as the number of matched men at fW. (Hint: The number of matched women is the same as the number of matched men at every matching. Use the result in the previous step to write down two sequence of inequalities in terms of the numbers of matched men at f,fM,fW. Then find a sequence of equalities.) (g) (7 points) Use the results in the previous two steps to argue that the set of matched men at fM is the same as the set of matched men at f which is the same as the set of matched men at fW. (h) (7 points) Argue that the set of matched/unmatched agents remains the same at all stable matchings. 2. (Rural Hospital Theorem) Consider an arbitrary marriage problem. Let fM be the mer proposing DA matching of this problem. Let fW be the women-proposing DA matchin of this problem. Let f be an arbitrary stable matching of this problem. We show via th following steps that the set of matched/unmatched agents at f is the same as that at fM an that at fW. In other words, the set of matched/unmatched agents remain unchanged acros all stable matchings. (a) Assume that man m1 is matched (i.e., is not single) at fW. Argue that man m1 prefer his outcome at fW to being single. (b) Argue that man m1 is matched at f. (Hint: Use the opposing interests result and th result in the previous step to argue that man m1 cannot be single at f.) (c) Argue that man m1 is matched at fM. (Hint: Use the optimality of men-proposing D. algorithm and the result in the previous step to argue that man m1 cannot be single a fM.) (d) Through the above steps, we can conclude that every man matched at fW is also matched at f, and every man matched at f is also matched at fM. Provide similar arguments to show that every woman matched at fM is also matched at f, and every woman matched at f is also matched at fW. (e) Argue that the set of matched men at fM contains the set of matched men at f which further contains the set of matched men at fW. Similarly, argue that the set of matched women at fW contains the set of matched women at f which further contains the set of matched women at fM. (f) Argue that the number of matched men at fM is the same as the number of matched men at f which is the same as the number of matched men at fW. (Hint: The number of matched women is the same as the number of matched men at every matching. Use the result in the previous step to write down two sequence of inequalities in terms of the numbers of matched men at f,fM,fW. Then find a sequence of equalities.) (g) (7 points) Use the results in the previous two steps to argue that the set of matched men at fM is the same as the set of matched men at f which is the same as the set of matched men at fW. (h) (7 points) Argue that the set of matched/unmatched agents remains the same at all stable matchings