CSCI 570 Fall 2021 HW 1 Due Sep 3rd 1 Reading Assignment Kleinberg and Tardos Chapter 1 2 Solve Kleinberg and Tardos Chapter 1 Exercise 1 False Suppose we have two men m m0 and two women w w0 Let m rank w rst w rank m0 rst m0 rank w0 rst and w0 rank m rst We see that such a pair as described by the claim does not exist Rubric 5pt 2 pt Correct T F claim 3 pt Provides a correct counterexample as explanation 3 Solve Kleinberg and Tardos Chapter 1 Exercise 2 True Suppose S is a stable matching where m and w are not paired with each other Suppose that contains the pairs m w0 and m0 w instead for some m0 cid 54 m w0 cid 54 w Clearly the pairing m w is preferred by both m and w over their current pairings contradicting the stability of S Thus by contradiction every stable matching must contain m w Rubric 5pt 2 pt Correct T F claim 3 pt Provides a correct explanation 4 State True False An instance of the stable marriage problem has a unique stable matching if and only if the version of the Gale Shapely algorithm where the male proposes and the version where the female proposes both yield the exact same matching True Proving the given statement requires proving the claims in two directions if and only if Claim If there is a unique stable matching then the version of the Gale Shapely algorithm where the male proposes and the version where the fe male proposes both yield the exact same matching The proof of the above claim is clear by virtue of the correctness of Gale Shapely algorithm That is the version of the Gale Shapely algorithm 1 where the male proposes and the version where the female proposes are both correct and hence will both yield a stable matching However since there is a unique stable matching both versions of the algorithms should yield the same matching Next we prove the converse If the version of the Gale Shapely algorithm where the male proposes and the version where the female proposes both yield the exact same matching then there is a unique stable matching The proof of the converse is perhaps more interesting For the de nition of best valid partner worst valid partner etc see page 10 11 in the textbook Let S denote the stable matching obtained from the version where men propose and let S0 be the stable matching obtained from the version where women propose From page 11 statement 1 8 in the text in S every woman is paired with her worst valid partner Applying page 10 statement 1 7 by symmetry to the version of Gale Shapely where women propose it follows that in S0 every woman is paired with her best valid partner Since S and S0 are the same matching it follows that for every woman the best valid partner and the worst valid partner are the same This implies that every woman has a unique valid partner which implies that there is a unique stable matching Rubric 10pt 4pts Correct proof a 1pt Correctly state forward claim b 3pt Correctly justify forward claim 6pts Correct proof a 1pt Correctly state backwards claim b 5pts Correctly justify backwards claim 5 A stable roommate problem with 4 students a b c d is de ned as follows Each student ranks the other three in strict order of preference A match ing is de ned as the separation of the students into two disjoint pairs A matching is stable if no two separated students prefer each other to their current roommates Does a stable matching always exist If yes give a proof Otherwise give an example roommate preference where no stable matching exists A stable matching need not exist Consider the following list of prefer ences Let a b c all have d last on their lists Say a prefers b over c b prefers c over a and c prefers a over b In every matching one of a b c should be paired with d and the other two with each other Without loss of generality suppose a gets paired with d thus b c with each other Now a prefers c over his current partner d and c also prefer to 2 be with each other Thus every matching is unstable no stable matching exists in this case Rubric 6pt 1pts Correct answer i e matching need not exist 5pts Correct counter example as explanation a 2pt Describe the preference lists b 3pts Explain why no stable matching exists 6 Solve Kleinberg and Tardos Chapter 1 Exercise 3 We will give an example with n 2 of a set of TV shows associated ratings for which no stable pair of schedules exists Let a1 a2 be set the shows of A and let b1 b2 be the set of shows of B Let the ratings of a1 a2 b1 b2 be 1 3 2 and 4 respectively In every schedule that A and B can choose either a1 shares a slot with b1 or a1 shares a slot with b2 If a1 shares a slot with b1 then A has an incentive to make a1 share a slot with b2 thereby increasing its number of winning slots from 0 to 1 If a1 shares a slot with b2 then B has an incentive to make b2 share a slot with a2 thereby increasing its number of winning slots from 1 to 2 Thus every schedule that A and B can choose is unstable Rubric 6pt 1 pt Correct claim that there are con gurations of shows without stable matching 5 pt Provides a correct counterexample 7 Solve Kleinberg and Tardos Chapter 1 Exercise 4 We will use a variation of Gale and Shapley GS algorithm then show that the solution returned by this algorithm is a stable matching In the following algorithm see next page we use hospitals in the place of men and students in the place of women with respect to the earlier version of the GS algorithm given in Chapter 1 This algorithm terminates in O mn steps because each hospital o ers a position to a student at most once and in each iteration some hospital o ers a position to some student The algorithm terminates by producing a matching M for any given pref erence list Suppose there are p 0 positions available at hospital h The algorithm terminates with all of the positions lled since any hos pital that did not ll all of its positions must have o ered them to every student Every student who rejected must be committed to some other hospital Thus if h still has available positions it would mean total num ber of available positions is n the number of students This contradicts the assumption given proving that all the positions get lled 3 1 while there exists a hospital h that has available positions do 2 O er position to the next highest ranked student s in the preference list of h that wasn t …