CSCI 570 - Fall 2021 - HW 1Due: Sep 3rd1. Reading Assignment: Kleinberg and Tardos, Chapter 1.2. Solve Kleinberg and Tardos, Chapter 1, Exercise 1.False. Suppose we have two men m, m0and two women w, w0. Let mrank w first; w rank m0first; m0rank w0first; and w0rank m first. Wesee 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 explanation3. Solve Kleinberg and Tardos, Chapter 1, Exercise 2.True. Suppose S is a stable matching where m and w are not paired witheach other. Suppose that contains the pairs (m, w0) and (m0, w) instead,for some m06= m, w06= w. Clearly, the pairing (m, w) is preferred byboth 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 explanation4. State True/False: An instance of the stable marriage problem has a uniquestable matching if and only if the version of the Gale-Shapely algorithmwhere the male proposes and the version where the female proposes bothyield 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 algorithm1where the male proposes and the version where the female proposes areboth correct and hence will both yield a stable matching. However sincethere is a unique stable matching, both versions of the algorithms shouldyield the same matching.Next, we prove the converse: “If the version of the Gale-Shapely algorithmwhere the male proposes and the version where the female proposes bothyield the exact same matching then there is a unique stable matching.”The proof of the converse is perhaps more interesting. For the definition ofbest valid partner, worst valid partner etc., see page 10-11 in the textbook.Let S denote the stable matching obtained from the version where menpropose and let S0be the stable matching obtained from the version wherewomen propose.From (page 11, statement 1.8 in the text), in S, every woman is paired withher worst valid partner. Applying (page 10, statement 1.7) by symmetryto the version of Gale-Shapely where women propose, it follows that inS0, every woman is paired with her best valid partner. Since S and S0are the same matching, it follows that for every woman, the best validpartner and the worst valid partner are the same. This implies that everywoman has a unique valid partner which implies that there is a uniquestable 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 claim5. A stable roommate problem with 4 students a, b, c, d is defined as follows.Each student ranks the other three in strict order of preference. A match-ing is defined as the separation of the students into two disjoint pairs. Amatching is stable if no two separated students prefer each other to theircurrent roommates. Does a stable matching always exist? If yes, give aproof. Otherwise give an example roommate preference where no stablematching 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, bprefers 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. Withoutloss of generality, suppose a gets paired with d (thus, b, c with eachother). Now, a prefers c over his current partner d and c also prefer to2dont understand how this is enough for a proof- is it because we assume correctness and can use the definition?be with each other. Thus every matching is unstable no stable matchingexists 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 exists6. Solve Kleinberg and Tardos, Chapter 1, Exercise 3.We will give an example (with n = 2) of a set of TV shows/associatedratings for which no stable pair of schedules exists. Let a1, a2be set theshows of A and let b1; b2be the set of shows of B. Let the ratings of a1;a2; b1; b2be 1, 3, 2 and 4 respectively. In every schedule that A and Bcan choose, either a1shares a slot with b1or a1shares a slot with b2. Ifa1shares a slot with b1, then A has an incentive to make a1share a slotwith b2thereby increasing its number of winning slots from 0 to 1. If a1shares a slot with b2, then B has an incentive to make b2share a slot witha2thereby increasing its number of winning slots from 1 to 2. Thus everyschedule that A and B can choose is unstable.Rubric (6pt):• 1 pt: Correct claim that there are configurations of shows withoutstable matching• 5 pt: Provides a correct counterexample7. Solve Kleinberg and Tardos, Chapter 1, Exercise 4.We will use a variation of Gale and Shapley (GS) algorithm, then showthat the solution returned by this algorithm is a stable matching.In the following algorithm (see next page), we use hospitals in the placeof men; and students in the place of women, with respect to the earlierversion of the GS algorithm given in Chapter 1.This algorithm terminates in O(mn) steps because each hospital offers aposition to a student at most once, and in each iteration some hospitaloffers 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 filled, since, any hos-pital that did not fill all of its positions must have offered them to everystudent. Every student who rejected must be committed to some otherhospital. Thus, if h still has available positions, it would mean total num-ber of available positions is > n, the number of students. This contradictsthe assumption given, proving that all the positions get filled.3is drawing a picture for the counterexample ok?1: while