CSE 2353 Project
Assigned Nov 4th
Due Dec 5th at 11:59pm
“Stable Marriage” Problem
A well-known problem in the field of Computer Science is known as the “Stable Marriage”
problem. As it was defined, the problem describes a scenario where a set of men and an equally
sized set of women are to be matched up for marriage while taking into account their
preference of partners. In a more general case, this problem can be defined as the following:
Suppose you have two distinct sets of elements, denoted A and B. Both sets have exactly n
elements. Each element in set A is to be paired with another element in set B. Prior to pairing,
all elements in A give high-to-low preference ranking showing which elements in B they want to
be paired with, and vice-versa. A “stable pairing” is a set (denoted S) in which the following
conditions hold true:
1. The set S must be a subset of A x B (cartesian product of A and B)
2. All elements in set A have a corresponding element in set B such that the pair (a, b) is an
element of S
3. All elements in set B have a corresponding element in set A such that the pair (a, b) is an
element of S
4. There are no two pairs (a, b) and (a’, b’) in S such that b’ is higher preference for a than
b, and a is higher preference for b’ than a’ (in this case, since a and b’ both prefer each
other to their assigned match, they will choose to break their match in favor of a match
(a, b’))
5. There are no two pairs (a, b) and (a’, b’) in S such that a’ is higher preference for b than
a, and b is higher preference for a’ than b’ (again, in this case b and a’ would break their
assigned match in favor of a match (a’, b)
For example, consider students in CS 3345 and CS 3353 as two distinct sets of people (assume
that you can’t enroll in both at the same time). Your sets may look like:
A = { “Alex”, “Bob”, “Charles” }
B = { “Devin”, “Erik”, “Frank” }
Where A = CS 3345 and B = CS 3353. A joint project between the two classes requires forming
pairs of students containing one student from each class. Prior to creating pairs, each student
was tasked with defining who they want to work with, in order of high to low preference:
Alex: Devin, Frank, Erik Devin: Charles, Bob, Alex
Bob: Frank, Erik, Devin Erik: Bob, Charles, Alex
Charles: Devin, Erik, Frank Frank: Bob, Alex, Charles
A stable pairing of the two sets of students may look like the following:
Alex & Erik
Bob & Frank
Charles & Devin
This satisfies each constraint. In particular, there are no sets of pairs wherein two people from
different pairs both prefer each other compared to their given partners. For example, while
both Alex and Erik are lowest in each other’s preferences, they are also lower in everyone else’s
preferences compared to their assigned partners. As such, no one will choose to leave their
groups and the pairing is deemed “stable” (perhaps not ideal, but stable nonetheless).
A generic solution to this problem has been defined in a seminal paper by David Gale and Lloyd
Shapley, appropriately named the Gale-Shapley algorithm. You will need to do outside
research on this algorithm in order to complete this project. The original paper is publicly
available and easily found online. Your task is to do some research and theoretical analysis on
how this algorithm works and demonstrate its correctness. Then, you will implement the
algorithm so that it works with some provided constraints.
Theory (40% of grade)
On page 1 of this handout, there are 5 conditions that must be satisfied in order for a set to be
considered a stable match. For each condition, convert it to formal logic. Be explicit and clear
when it comes to defining things like your domains, your predicates, etc. Hint: most of them
contain at least one kind of quantifier.
Then, use the method of proof by contradiction to prove the following:
• If both sets contain n elements, The Gale-Shapley algorithm always results in n pairs.
• The resulting pairs are stable; as in, there are no unstable pairs when the algorithm
finishes.
Additional research will be required to understand and answer the above bullet points. In
relation to the Implementation section below: outline an algorithm that can be used to verify
that a set of matches are in fact stable. Write this algorithm in pseudocode. You will eventually
convert this pseudocode into actual code in the next section.
Your answers must be grouped into a single PDF file. Neatly handwritten or typed responses
are accepted.
Implementation (60% of grade)
Your implementation of the Gale-Shapley algorithm can be done in any of the following
languages: Java, C++, Python, or JavaScript (node). You must implement the algorithms from
scratch.
The following defines some Java-esque pseudocode for building those sets:
class Element {
String name;
List preferences;
public Element(String name) { … }
public String getName() { … }
public void addPreference(Element pref) { … }
public List getPreferences() { … }
}
class SetOfElements {
List elementsInSet;
public SetOfElements() { … }
public void addElement(Element e) { … }
public List getElements { … }
}
class StableMatchSet {
List