Description
1. 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.
2. In the context of a stable roommates 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 ove their current roommates.
Does a stable matching always exist in this scenario?
3. True or False: In every instance of the Stable Matching Problem, there is a stable matching containing
a pair (m, w) such that m is ranked first on the preference list of w and w is ranked first on the preference
list of m.
4. True or False: Consider an instance of the Stable Matching Problem in which there exists a man m and
a woman w such that m is ranked first on the preference list of w and w is ranked first on the preference
list of m. Then in every stable matching S for this instance, the pair (m, w) belongs to S.
5. True or False: 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. True or False: 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. Can a man or woman end up better off by lying about his or her preferences? Consider a woman w,
who prefers man m to m’, but both are low on her list of preferences. Can w end up with a man m” that
she truly prefers to both m and m’ by falsely claiming that she prefers m’ to m?
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:
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.
