[SOLVED] Csci570 – homework 1

1. State whether the following statement is True or False: “It is possible to have an instance of the Stable Matching problem in which two women have the same best valid partner.” (5pts)
2. 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)