PROBLEM 1 (25 POINTS) Here is an algorithm that attempts to produce a stable matching between N hospitals and N students. 1. Let M be an arbitrary initial matching between hospitals and students; 2. Let (h,s) and (h',s") be arbitrary pairs in M such that (h,s') form an unstable pair with respect to M, i.e., an unmatched pair such that both parties prefer each other over their current match. If no such pair exists, halt with output M. 3. Modify M by swapping the assignments; remove the previous two pairs, and add two new pairs matching (h, s') and (W',s) 4. Goto line 2. We will show that this algorithm can run forever without producing a stable matching even for N = 3. To accomplish this task, denote the hospitals as H = {h1, h2, h3}, and the students as S = {51,52,53). Construct a counterexample by completing the following parts. (a) Fill in the blanks in the following preference lists for your counterexample. The leftmost entry is the most preferred; the rightmost is the least. Solution: hy: S]: h2 52: 13: (b) We assume, without loss of generality, that the initial matching is {(1,5),(h, sz), (h3,53)}. Fill in the following table with with the execution of the algorithm that leads to an infinite loop. In the "Iteration #" column, write down the iteration number; in the "Unstable Pair" column, write down the unstable pair that triggers a swap; in the "Matching After Swap" column, write down the matching after the swap is performed. Solution: Iteration # Unstable Pair Matching After Swap -). (h2 -), (13, -), (he -) (ht, -), (h2 -). (h. -). (h2, -), (h -) (h2, -). (h. -). (h2 -), (h. -), (he -), (13 (hi (h1 PROBLEM 1 (25 POINTS) Here is an algorithm that attempts to produce a stable matching between N hospitals and N students. 1. Let M be an arbitrary initial matching between hospitals and students; 2. Let (h,s) and (h',s") be arbitrary pairs in M such that (h,s') form an unstable pair with respect to M, i.e., an unmatched pair such that both parties prefer each other over their current match. If no such pair exists, halt with output M. 3. Modify M by swapping the assignments; remove the previous two pairs, and add two new pairs matching (h, s') and (W',s) 4. Goto line 2. We will show that this algorithm can run forever without producing a stable matching even for N = 3. To accomplish this task, denote the hospitals as H = {h1, h2, h3}, and the students as S = {51,52,53). Construct a counterexample by completing the following parts. (a) Fill in the blanks in the following preference lists for your counterexample. The leftmost entry is the most preferred; the rightmost is the least. Solution: hy: S]: h2 52: 13: (b) We assume, without loss of generality, that the initial matching is {(1,5),(h, sz), (h3,53)}. Fill in the following table with with the execution of the algorithm that leads to an infinite loop. In the "Iteration #" column, write down the iteration number; in the "Unstable Pair" column, write down the unstable pair that triggers a swap; in the "Matching After Swap" column, write down the matching after the swap is performed. Solution: Iteration # Unstable Pair Matching After Swap -). (h2 -), (13, -), (he -) (ht, -), (h2 -). (h. -). (h2, -), (h -) (h2, -). (h. -). (h2 -), (h. -), (he -), (13 (hi (h1
