Solved CSCI570 Homework 1 1. Consider a stable roommate problem involving four students (A, B, C, D):

Description

Fall 2025

1. Consider a stable roommate problem involving four students (A, B, C, D): Each student
ranks the other three in a strict order of preference. A matching involves forming two
pairs of the students, and it is considered stable if no two separated (not matched)
students would prefer each other over their current roommates.
Prove or disprove: A stable matching always exists in this scenario.
2. 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.
Prove or disprove: In every stable matching for this instance, m is matched with w.
3. Consider the stable matching problem with n women and n men (where n ≥ 2).
Prove or disprove: It is not possible for any preference lists, that the Gale-Shapley
algorithm with men proposing can match every woman to her least preferred man.
4. There are six students in a class: Harry, Ron, Hermione, Luna, Neville, and Ginny. 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: Hermione > Neville > Ron > Ginny > Luna
Ron: Ginny > Neville > Hermione > Harry > Luna
Hermione: Ron > Neville > Ginny > Harry > Luna
Luna : Harry > Ron > Ginny > Hermione > Neville
Neville: Harry > Ron > Hermione > Ginny > Luna
Ginny: Neville > Harry > Hermione > Ron > Luna
A given matching (of students into pairs) is not stable if there are two potential partners
who are not currently paired but prefer each other over their respective current partners.
Prove or Disprove: No matching is stable for the preferences given above.
Ungraded Problems:
1. Prove or Disprove: It is possible to have an instance of the Stable Matching problem in
which two women have the same best valid partner.
2. Prove or Disprove: 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.
3. Consider the stable matching problem with n women and n men (where n ≥ 2). Suppose
the preference lists are such that for any woman w, her most preferred man m, does not
have w as his first preference
Prove or disprove: It is possible that the Gale-Shapley algorithm with men proposing can
match every woman to her most preferred man.
4. Suppose the Gale-Shapley algorithm with men proposing is run once. Then, a particular
woman w falsely reports her preferences by swapping two men’s positions in her actual
preference list. With this alteration, the Gale-Shapley algorithm with men proposing is
run once again.
Prove or disprove: It is possible for the woman w to get a more preferred partner (as per
her actual preference list), by doing the swapping alteration in her preferences.