In Solved Exercise 2 (p. 19 of Kleinberg), our book modifies the code for Gale- Shapley. Let us instead solve the problem using the following reduction to the standard stable matching problem. Given an instance where some pairs are forbidden, move the forbidden part- ners of each man to the bottom of his list without disturbing the relative order of the other women in his list. Perform the analogous operation the women's lists. Find a standard stable matching S for these lists. - Remove all forbidden marriages in S, and return the set S' of matchings that are left. The people that aren't in a marriage in S' are single. Prove by contradiction that S' is stable under the new definition of stability that is given on page 20 of the Kleinberg text. To do this, assume S' violates one of the stability conditions of the new problem. In each case, show that S is also unstable, contradicting how S was chosen. (ii) There is a pair (m, w) ES, and a man m', so that m' is not part of any pair in the matching, (m', w) &F, and w prefers m' to m. (A single man is more desirable and not forbidden.) (iii) There is a pair (m, w) ES, and a woman w', so that w' is not part of any pair in the matching, (m,w) &F, and m prefers w' to w. (A single woman is more desirable and not forbidden.) (iv) There is a man m and a woman w, neither of whom is part of any pair in the matching, so that (m, w) F. (There are two single people with nothing preventing them from getting married to each other.) Note that under these more general definitions, a stable matching need not be a perfect matching. Now we can ask: For every set of preference lists and every set of forbidden pairs, is there always a stable matching? Resolve this question by doing one of the following two things: (a) give an algorithm that, for any set of preference lists and forbidden pairs, produces a stable matching; or (b) give an example of a set of preference lists and forbidden pairs for which there is no stable matching. Solution The Gale-Shapley algorithm is remarkably robust to variations on the Stable Matching Problem. So, if you're faced with a new variation of the problem and can't find a counterexample to stability, it's often a good idea to check whether a direct adaptation of the G-S algorithm will in fact produce stable matchings. That turns out to be the case here. We will show that there is always a stable matching, even in this more general model with forbidden pairs, and we will do this by adapting the G-S algorithm. To do this, let's consider why the original G-S algorithm can't be used directly. The difficulty, of course, is that the G-S algorithm doesn't know anything about forbidden pairs, and so the condition in the While loop, While there is a man m who is free and hasn't proposed to every woman, Solved Exercises 21 won't work: we don't want m to propose to a woman w for which the pair (m, w) is forbidden. Thus, let's consider a variation of the G-S algorithm in which we make only one change: we modify the While loop to say, . While there is a man m who is free and hasn't proposed to every woman w for which (m, w) &F. Here is the algorithm in full. Initially all me M and we are free While there is a man m who is free and hasn't proposed to every woman w for which (m, w) C F Choose such a man m Let w be the highest-ranked woman in m's preference list to which m has not yet proposed If w is free then (m, w) become engaged Else w is currently engaged to m' If w prefers m' to m then m remains free Else w prefers m to m' (m, w) become engaged m' becomes free Endif Endif Endwhile Return the set S of engaged pairs We now prove that this yields a stable matching, under our new definition of stability. - To begin with, facts (1.1), (1.2), and (1.3) from the text remain true (in particular, the algorithm will terminate in at most na iterations). Also, we don't have to worry about establishing that the resulting matching S is perfect (indeed, it may not be). We also notice an additional pairs of facts. If m is a man who is not part of a pair in S, then m must have proposed to every nonforbidden woman; and if w is a woman who is not part of a pair in S, then it must be that no man ever proposed to w. Finally, we need only show (1.9) There is no instability with respect to the returned matching S. Chapter 1 Introduction: Some Representative Problems Proof. Our general definition of instability has four parts: This means that we have to make sure that none of the four bad things happens. Proof. Our general definition of instability has four parts: This means that we have to make sure that none of the four bad things happens. First, suppose there is an instability of type (i), consisting of pairs (m, w) and (m', w') in S with the property that (m, w') &F, m prefers w' to w, and w' prefers in to m'. It follows that m must have proposed to w'; so w' rejected m, and thus she prefers her final partner to m-a contradiction. Next, suppose there is an instability of type (ii), consisting of a pair (m, w) ES, and a man m', so that m' is not part of any pair in the matching, (m', w) & F, and w prefers m' to m. Then m' must have proposed to w and been rejected; again, it follows that w prefers her final partner to m'-a contradiction. Third, suppose there is an instability of type (iii), consisting of a pair (m, w) ES, and a woman w', so that w' is not part of any pair in the matching, (m, w') &F, and m prefers w' to w. Then no man proposed to w' at all; in particular, m never proposed to w', and so he must prefer w to w'-a contradiction. Finally, suppose there is an instability of type (iv), consisting of a man m and a woman w, neither of which is part of any pair in the matching, so that (m, w) & F. But for m to be single, he must have proposed to every nonforbidden woman; in particular, he must have proposed to w, which means she would no longer be singlea contradiction. In Solved Exercise 2 (p. 19 of Kleinberg), our book modifies the code for Gale- Shapley. Let us instead solve the problem using the following reduction to the standard stable matching problem. Given an instance where some pairs are forbidden, move the forbidden part- ners of each man to the bottom of his list without disturbing the relative order of the other women in his list. Perform the analogous operation the women's lists. Find a standard stable matching S for these lists. - Remove all forbidden marriages in S, and return the set S' of matchings that are left. The people that aren't in a marriage in S' are single. Prove by contradiction that S' is stable under the new definition of stability that is given on page 20 of the Kleinberg text. To do this, assume S' violates one of the stability conditions of the new problem. In each case, show that S is also unstable, contradicting how S was chosen. In Solved Exercise 2 (p. 19 of Kleinberg), our book modifies the code for Gale- Shapley. Let us instead solve the problem using the following reduction to the standard stable matching problem. Given an instance where some pairs are forbidden, move the forbidden part- ners of each man to the bottom of his list without disturbing the relative order of the other women in his list. Perform the analogous operation the women's lists. Find a standard stable matching S for these lists. - Remove all forbidden marriages in S, and return the set S' of matchings that are left. The people that aren't in a marriage in S' are single. Prove by contradiction that S' is stable under the new definition of stability that is given on page 20 of the Kleinberg text. To do this, assume S' violates one of the stability conditions of the new problem. In each case, show that S is also unstable, contradicting how S was chosen. (ii) There is a pair (m, w) ES, and a man m', so that m' is not part of any pair in the matching, (m', w) &F, and w prefers m' to m. (A single man is more desirable and not forbidden.) (iii) There is a pair (m, w) ES, and a woman w', so that w' is not part of any pair in the matching, (m,w) &F, and m prefers w' to w. (A single woman is more desirable and not forbidden.) (iv) There is a man m and a woman w, neither of whom is part of any pair in the matching, so that (m, w) F. (There are two single people with nothing preventing them from getting married to each other.) Note that under these more general definitions, a stable matching need not be a perfect matching. Now we can ask: For every set of preference lists and every set of forbidden pairs, is there always a stable matching? Resolve this question by doing one of the following two things: (a) give an algorithm that, for any set of preference lists and forbidden pairs, produces a stable matching; or (b) give an example of a set of preference lists and forbidden pairs for which there is no stable matching. Solution The Gale-Shapley algorithm is remarkably robust to variations on the Stable Matching Problem. So, if you're faced with a new variation of the problem and can't find a counterexample to stability, it's often a good idea to check whether a direct adaptation of the G-S algorithm will in fact produce stable matchings. That turns out to be the case here. We will show that there is always a stable matching, even in this more general model with forbidden pairs, and we will do this by adapting the G-S algorithm. To do this, let's consider why the original G-S algorithm can't be used directly. The difficulty, of course, is that the G-S algorithm doesn't know anything about forbidden pairs, and so the condition in the While loop, While there is a man m who is free and hasn't proposed to every woman, Solved Exercises 21 won't work: we don't want m to propose to a woman w for which the pair (m, w) is forbidden. Thus, let's consider a variation of the G-S algorithm in which we make only one change: we modify the While loop to say, . While there is a man m who is free and hasn't proposed to every woman w for which (m, w) &F. Here is the algorithm in full. Initially all me M and we are free While there is a man m who is free and hasn't proposed to every woman w for which (m, w) C F Choose such a man m Let w be the highest-ranked woman in m's preference list to which m has not yet proposed If w is free then (m, w) become engaged Else w is currently engaged to m' If w prefers m' to m then m remains free Else w prefers m to m' (m, w) become engaged m' becomes free Endif Endif Endwhile Return the set S of engaged pairs We now prove that this yields a stable matching, under our new definition of stability. - To begin with, facts (1.1), (1.2), and (1.3) from the text remain true (in particular, the algorithm will terminate in at most na iterations). Also, we don't have to worry about establishing that the resulting matching S is perfect (indeed, it may not be). We also notice an additional pairs of facts. If m is a man who is not part of a pair in S, then m must have proposed to every nonforbidden woman; and if w is a woman who is not part of a pair in S, then it must be that no man ever proposed to w. Finally, we need only show (1.9) There is no instability with respect to the returned matching S. Chapter 1 Introduction: Some Representative Problems Proof. Our general definition of instability has four parts: This means that we have to make sure that none of the four bad things happens. Proof. Our general definition of instability has four parts: This means that we have to make sure that none of the four bad things happens. First, suppose there is an instability of type (i), consisting of pairs (m, w) and (m', w') in S with the property that (m, w') &F, m prefers w' to w, and w' prefers in to m'. It follows that m must have proposed to w'; so w' rejected m, and thus she prefers her final partner to m-a contradiction. Next, suppose there is an instability of type (ii), consisting of a pair (m, w) ES, and a man m', so that m' is not part of any pair in the matching, (m', w) & F, and w prefers m' to m. Then m' must have proposed to w and been rejected; again, it follows that w prefers her final partner to m'-a contradiction. Third, suppose there is an instability of type (iii), consisting of a pair (m, w) ES, and a woman w', so that w' is not part of any pair in the matching, (m, w') &F, and m prefers w' to w. Then no man proposed to w' at all; in particular, m never proposed to w', and so he must prefer w to w'-a contradiction. Finally, suppose there is an instability of type (iv), consisting of a man m and a woman w, neither of which is part of any pair in the matching, so that (m, w) & F. But for m to be single, he must have proposed to every nonforbidden woman; in particular, he must have proposed to w, which means she would no longer be singlea contradiction. In Solved Exercise 2 (p. 19 of Kleinberg), our book modifies the code for Gale- Shapley. Let us instead solve the problem using the following reduction to the standard stable matching problem. Given an instance where some pairs are forbidden, move the forbidden part- ners of each man to the bottom of his list without disturbing the relative order of the other women in his list. Perform the analogous operation the women's lists. Find a standard stable matching S for these lists. - Remove all forbidden marriages in S, and return the set S' of matchings that are left. The people that aren't in a marriage in S' are single. Prove by contradiction that S' is stable under the new definition of stability that is given on page 20 of the Kleinberg text. To do this, assume S' violates one of the stability conditions of the new problem. In each case, show that S is also unstable, contradicting how S was chosen