Description
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)