Homework 1 Due January 17 11 59 PM PST 1 State whether the following statement is True or False It is possible to have an instance of the 2 Stable Matching problem in which two women have the same best valid partner 5pts In the context of a stable roommate problem involving four students a b c d each student ranks the others in a strict order of preference A matching involves forming two pairs of students and it is considered stable if no two separated students would prefer each other over their current roommates The question is whether a stable matching always exists in this scenario If it does provide proof if not present an example of roommate preferences where no stable matching is possible 10pts 3 Solve Kleinberg and Tardos Chapter 1 Exercise 1 10pts 4 Solve Kleinberg and Tardos Chapter 1 Exercise 2 10pts 5 Determine whether the following statement is true or false If it is true give an example If it is false give a short explanation 10pts For some n 2 there exists a set of preferences for n men and n women such that in the stable matching returned by the G S algorithm when men are proposing every woman is matched with their most preferred man even though that man does not prefer that woman the most 6 Determine whether the following statement is true or false If it is true give a short explanation If it is false give a counterexample 10pts For all n 2 there exists a set of preferences for n men and n women such that in the stable matching returned by the G S algorithm when men are proposing every woman is matched with their least preferred man 7 Solve Kleinberg and Tardos Chapter 1 Exercise 8 10pts 8 There are six students Harry Ron Hermione Ginny Draco and Cho This class requires them to pair up and work on pair programming Each has preferences over who they want to be paired with The preferences are Harry Cho Ron Hermione Ginny Draco Ron Ginny Harry Hermione Cho Draco Hermione Ron Harry Ginny Cho Draco Ginny Harry Cho Hermione Ron Draco Draco Cho Ron Ginny Hermione Harry Cho Hermione Harry Ron Ginny Draco Show that there is no stable matching That means showing that no matter who you put together there will always be two potential partners who are not matched but prefer each other to the current partner 10pts
View Full Document
Unlocking...