CPSC 320 Sample Solution, The Stable Marriage Problem
September 13, 2018
1 Trivial and Small Instances
1. Write down all the trivial instances of SMP. We think of an instance as “trivial” roughly if its solution
requires no real reasoning about the problem.
SOLUTION: If you think of the smallest possible instances, it usually guides you towards trivial
instances. In SMP, it’s tempting to say that the smallest possible instance has one man and one
woman, but we can go smaller! Degenerate cases like “zero men and zero women” are often helpful!
So, is zero men and zero women trivial? Sure! There’s exactly one solution, in which no one is
matched with anyone else.
What about one man and one woman? Regardless of their preferences (which, in fact, must be simply
for each other), the only solution is for the one man to marry the one woman.
So, zero men/women and one man/woman are the trivial instances.
FROM SOLUTION REPRESENTATION: The solution for a problem with n = 0 is the empty
set of pairings {}. The solution for a problem with n = 1 is {(m1, w1)}.
What about two men and women? You might start that here, but you’ll quickly realize it belongs in
the next slot. . .
2. Write down two small instances of SMP. One should be based on your candy/baked goods example
above (but we’ll just make one up for the sample solution):
SOLUTION: Here’s what we might have come up with. This is just a sample of three men and
women and their preferences for each other that could come from the baked goods example:
w1: m2 m1 m3 m1: w3 w1 w2
w2: m1 m2 m3 m2: w3 w2 w1
w3: m2 m1 m3 m3: w2 w1 w3
Each woman lists their preferences for men in order from most to least preferred.
Each man lists their preferences for women in the same order.
FROM PROBLEM REPRESENTATION: We can rephrase this with our new notation, but
honestly, there’s not much to do. n = 3, clearly. W = {w1, w2, w3}, but all that changes there is
subscripts vs. numbers on the side. P [w1] is the first list on the left. Similarly, we can see the men
and the other preference lists.
FROM SOLUTION REPRESENTATION: There happens to be only one stable solution to this
instance: {(m2, w3), (m1, w1), (m3, w2)}.
On to the next question. . .
The other can be even smaller, but not trivial:
SOLUTION: We can go smaller and still have a trivial example. So, let’s do so. Two men and two
women:
This work is licensed under a Creative Commons Attribution 4.0 International License. cb
For license purposes, the author is the University of British Columbia.
http://creativecommons.org/licenses/by/4.0/
w1: m1 m2 m1: w1 w2
w2: m1 m2 m2: w2 w1
With two men/women, there are only two choices of preference list. So, I gave the women matching
preference lists and the men opposite preference lists, just to illustrate both possibilities. That may
be useful or may not!
FROM PROBLEM REPRESENTATION: I won’t explicitly use our new names here, since little
has changed, as noted above.
FROM SOLUTION REPRESENTATION: Again, there happens to be only one stable solution
to this instance: {(m1, w1), (m2, w2)}. (Want one with more than one solution? Try tweaking w1’s
preference list.)
2 Represent the Problem
In this part, we try to understand what an instance of the problem looks like. Imagine you were writing
a function to solve this problem. We’re asking what are the parameters to your function, what types are
they, and what constraints/preconditions are there on them and their relationships?
1. What are the quantities that matter in this problem? Give them short, usable names.
SOLUTION: You may have come up with more, fewer, or different quantities than me, but here are
some useful ones.
• n, the number of men and the number of women.
• M , the set of men {m1,m2, . . . ,mn} (so, n = |M |)
• W , the set of women {w1, w2, . . . , wn} (again, n = |W |)
• Each man’s preference list—which we might call P [mi] for man i—is a permutation of W , the
set of women. Note that I’m forcing the men to have complete preferences for all the women,
no ties. That’s the simplest version of the problem; so, probably the one to start with. I’ll also
assume that everyone prefers being married to not being married.
• Similarly, each woman’s preference list, P [wj ], is a permutation of M .
• It’s good to have a notation to indicate whether a woman prefers one man to another (or similarly
for a man). I’ll use mi >wj mk to mean that wj prefers mi to mk, i.e., mi occurs earlier in wj ’s
preference list than mk.
2. Go back up to your trivial and small instances and rewrite them using these names.
SOLUTION: See above.
3. Describe using your representational choices above what a valid instance looks like:
SOLUTION: What “shape” is an instance (in programming terms, what inputs of what type con-
stitute an input) and what additional constraints are there on inputs of that “shape” for them to be
valid?
The crucial piece of an instance is the preference lists for the men and women. We need to know how
many of those there are.
So, we might describe an instance as a tuple: (n, PW , PM ), where n is the number of women (and
also the number of men), PW is a list of n preference lists for the women (where element i is wi’s
preferences), and PM is a list of n preference lists for the men.
If you’re more comfortable thinking in programming input/output terms, you might say that the input
is: one line with a (non-negative) integer n, then n lines representing the women’s preference lists
This work is licensed under a Creative Commons Attribution 4.0 International License. cb
For license purposes, the author is the University of British Columbia.
http://creativecommons.org/licenses/by/4.0/
each with n whitespace-separated numbers forming a permutation of 1, . . . , n, and finally n similar
lines representing the men’s preference lists.
3 Represent the Solution
In this part, we try to understand what a solution to an instance of the problem looks like. Imagine you
were write a function to solve this problem. We’re asking what will your function return, what type is it,
and what postconditions does it satisfy?
1. What are the quantities that matter in the solution to the problem? Give them short, usable names.
SOLUTION: Central to our solution are marriages, which are pairs (mi, wj) indicating that man i
and woman j are married. A solution, then is a set of pairings (with some constraints we describe
next).
2. Describe using these quantities what makes a solution valid and good:
SOLUTION: There’s no technical weight intended here for the words “valid” and “good”. They’re
just ways to think about how you might judge solutions. A solution might be invalid if it violates a
constraint. It might be bad if it’s low-quality for some reason. (Later, we’ll also solve optimization
problems where we really are searching for the best among many valid solutions.)
In this case, let’s focus on validity measuring whether we’ve successfully married everyone off just
once. A valid solution is a perfect matching: a set of pairings such that each woman appears in
exactly one pairing and each man appears in exactly one as well.
Any such set of pairings is one we could propose to our women and men as a way to pair them off.
A good one is “self-enforcing” in the sense that no man and woman who aren’t married will decide to
break the arrangement we suggested. So, a good solution is stable in that it contains no instabilities.
Next, what’s an instability? An instability can occur for a man mi and woman wj who are not
matched in the solution ((mi, wj) 6∈ the set of pairings). Let w′ be mi’s partner in the solution and
m′ be wj ’s partner. Then, mi and wj constitute an instability if mi >wj m
′ and wj >mi w
′. That is,
each of mi and wj prefers the other to their assigned partners.
3. Go back up to your trivial and small instances and write out one or more solutions to each using
these names.
SOLUTION: See above.
4. Draw at least one solution. (We would normally ask you to draw an instance as well, but SMP isn’t
an especially graphical problem!)
SOLUTION: For this instance:
w1: m2 m1 m3 m1: w3 w1 w2
w2: m1 m2 m3 m2: w3 w2 w1
w3: m2 m1 m3 m3: w2 w1 w3
Here’s our drawing:
w1
w2
w3
m1
m2
m3
This work is licensed under a Creative Commons Attribution 4.0 International License. cb
For license purposes, the author is the University of British Columbia.
http://creativecommons.org/licenses/by/4.0/
4 Similar Problems
As the course goes on, we’ll have more and more problems we can compare against, but you’ve already
learned some. So. . .
Give at least one problem you’ve seen before that seems related in terms of its surface features (“story”),
problem or solution structure, or representation to this one:
SOLUTION: You may not have enough background in problems to feel like you’ve seen a lot of similar
problems, but you have at least seen problems where you organize a bunch of values by comparisons among
them: sorting. If you’ve worked with bipartite graphs and matching problems, anything associated with
them seems promising, especially maximum matching. (We often discuss “goodness” measures that give
more points to a first preference than a second and so forth, like the Borda count. You could frame that
problem as a maximum matching problem!) This also feels a bit like an election or auction, which takes us
toward game theory. Maybe you’d even decide this feels a bit like hashing (mapping a value in one set to
a different value in another set).
The point isn’t to be “right” yet; it’s to have a lot of potential tools on hand! As you collect more tools,
you’ll start to judge which are more promising and which less.
5 Brute Force?
You should usually start on any algorithmic problem by using “brute force”: generate all possible solutions
and test each one to see if it is, in fact, the solution we’re looking for.
1. A possible SMP solution takes the form of a perfect matching: a pairing of each woman with exactly
one man. We’ll call a perfect matching a “valid” (but not necessarily good) solution.
It’s more difficult than the usual brute force algorithm to produce all possible perfect matchings;
instead, we’ll count how many there are. Imagine lining all the men up in a row in a particular order.
How many different ways we can line up (permute) the women next to them?
SOLUTION: There are n women we can line up with the first man. Once we’ve chosen the first,
there are n− 1 to line up next to the second. Then, n− 2 next to the third, and so on. Overall, then,
that’s n × n − 1 × n − 2 × . . . × 2 × 1 = n!. There are n! perfect matchings, our “valid” solutions.
That’s already super-exponential, even if it takes only constant time per solution to produce them!
We asked in the challenge problems for an algorithm to produce these. It’s unusually challenging to
design for a brute force algorithm, but it’s useful to think about; so, we’ll work through it here.
Before we dive into an algorithm, let’s just try creating all solutions for an example. We might start
by just marrying the first person (say, w1) off to someone. After all, we know she needs to be married
to somebody!
w1
w2
w3
m1
m2
m3
We can now set w1 and m1 aside, which gives us. . . another SMP instance that’s smaller. As soon
as you hear words like “and that leaves us with [something that looks like our original problem] but
smaller”, you should be thinking of recursion. Let’s just assume we can recursively construct all
possible solutions. That will give us back a bunch of sets of pairings, in this case two:
w2
w3
m2
m3 and
w2
w3
m2
m3
This work is licensed under a Creative Commons Attribution 4.0 International License. cb
For license purposes, the author is the University of British Columbia.
https://en.wikipedia.org/wiki/Borda_count
http://creativecommons.org/licenses/by/4.0/
We can add our set-aside pairing (m1, w1) onto each of these:
w1
w2
w3
m1
m2
m3 and
w1
w2
w3
m1
m2
m3
That’s all the solutions in which w1 weds m1. Who else can w1 marry? Each of the other men. We
can use the same procedure for each other possible pairing. Must w1 marry someone? Yes, because
we need a perfect matching. So, that covers all the possibilities for w1 and, recursively, for everyone
else.
Now we’re ready for an algorithm. Let’s call it AllSolns. It’s recursive; so, what’s the base case?
Our trivial cases are where n = 0 or n = 1. Let’s try n = 0 as a base case. Looking back at the trivial
cases, I see the solution for n = 0 is the empty set of pairings {}. With that, let’s build the algorithm.
I’ll use return when I’m producing the whole set at once and yield to produce one at a time. (You
could just initialize a variable to the empty set and add in each yielded solution, returning the whole
set at the end.)
procedure AllSolns(W , M)
if |W | = 0 then . The base case we chose.
return {{}} . The set of sol’ns, containing only the empty sol’n.
else
choose a w ∈W . Any one, e.g., the first.
for all m ∈M do . Iterate through the men,
for all S ∈ AllSolns(W − {w},M − {m}) do . and the subproblem sol’ns.
yield {(m,w)} ∪ S . Add the set-aside pairing.
end for
end for
end if
end procedure
If we use our analysis techniques to count the number of solutions this creates, the analysis will
parallel the recursive function itself. In the base case when n = 0, AllSolns produces one solution.
Otherwise, for each of the n men, it makes a recursive call with n′ = n − 1 (one fewer man and one
fewer woman in the subproblem). For each solution produced by that recursive call, it also generates
one solution. If we give the number of solutions a name, we can express this as a recurrence:
N(n) =
{
1 when n = 0
n ∗N(n− 1) otherwise
So, for example, N(4) = 4∗N(3) = 4∗3∗N(2) = 4∗3∗2∗N(1) = 4∗3∗2∗1∗N(0) = 4∗3∗2∗1∗1 = 4!.
And, indeed, this is exactly the definition of factorial. So, N(n) = n!. There are n! solutions to a
problem of size n.
2. Once we have a possible solution, we must test whether it’s the solution we’re looking for. Informally,
we’ll refer to this as asking whether it’s a “good” solution.
A perfect matching is a good solution if it has no instabilities. Design a (brute force!) algorithm
that—given an instance of SMP and a perfect matching—determines whether that perfect matching
contains an instability. (As always, it helps to give a name to your algorithm and its parameters,
especially if your algorithm is recursive. Remember, for brute force: generate each possible solution
(possible instability, in this case) and then test whether it really is a solution.)
SOLUTION: The form of a potential instability is a pair (man and woman). We therefore want to
go through each pair of one man and one woman and check that (1) they are not already married (or
they cannot cause an instability) and (2) they’d rather be with each other that their partners. (I’ll
This work is licensed under a Creative Commons Attribution 4.0 International License. cb
For license purposes, the author is the University of British Columbia.
http://creativecommons.org/licenses/by/4.0/
assume we have a quick way to find a partner, which shouldn’t be hard to create.) That should look
like the following, where (n, PW , PM ) is an instance of SMP and S is a solution to that instance (a
perfect match and therefore a set of pairings (mi, wj)):
procedure IsStable((n, PW , PM ), S)
for all w ∈ {w1, . . . , wn} do
for all m ∈ {m1, . . . ,mn} do
if (m,w) 6∈ S then
find m′ such that (m′, w) ∈ S
find w′ such that (m,w′) ∈ S
if m >w m′ and w >m w′ then
return false
end if
end if
end for
end for
return true
end procedure
3. Exactly or asymptotically, how long does your algorithm take? (Again, you should explicitly name
the size of an instance and perform your analysis in terms of that name!)
SOLUTION: Let’s assume we do an efficient (constant-time) job of operations like comparing w’s
preferences for the two men and checking if (m,w) is in S. (It’s not immediately obvious how to do
this, but with some careful data structures and O(n2) preprocessing, it’s doable!) The number of
iterations in the inner loop is independent of which iteration we’re on in the outer one. The body
takes constant time. So, in the worst case (when we find no instability), this takes |M | ∗ |W | ∗O(1) =
n ∗ n ∗O(1) = O(n2) time.
4. Brute force would generate each valid solution and then test whether it’s good. Will brute force be
sufficient for this problem for the domains we’re interested in?
SOLUTION: Looks like brute force will take O(n2n!) time. That’s horrendous. It won’t do for even
quite modest values of n. (But, it is good enough to solve the n = 3 example we demonstrated in the
classroom.)
6 Promising Approach
Unless brute force is good enough, describe—in as much detail as you can—an approach that looks promis-
ing.
SOLUTION: You may have thought of lots of ideas. For example, you might have noticed that if a
man and a woman both most-prefer each other, we must pair them; that might form the kernel of some
kind of algorithm. We won’t go into ideas here. Rather, we refer you to the textbook’s description of the
Gale-Shapley algorithm.
7 Challenge Your Approach
1. Carefully run your algorithm on your instances above. (Don’t skip steps or make assumptions;
you’re debugging!) Analyse its correctness and performance on these instances:
SOLUTION: For fun, we’ll use G-S with women proposing.
This work is licensed under a Creative Commons Attribution 4.0 International License. cb
For license purposes, the author is the University of British Columbia.
http://creativecommons.org/licenses/by/4.0/
G-S correctly terminates immediately on any n = 0 example with an empty set of marriages. With
n = 1, the one woman proposes to the one man, who must accept, and the algorithm correctly
terminates with them married.
Going back to our other two examples:
(a) Example #1:
w1: m2 m1 m3 m1: w3 w1 w2
w2: m1 m2 m3 m2: w3 w2 w1
w3: m2 m1 m3 m3: w2 w1 w3
G-S doesn’t specify what order the women propose. We’ll work from top to bottom:
i. w1 proposes to m2, who accepts. E = {(m2, w1)}
ii. w2 proposes to m1, who accepts. E = {(m2, w1), (m1, w2)}
iii. w3 proposes to m2, who prefers w3 to w1. m2 breaks his engagement with w1 and accepts
w3’s proposal. E = {(m2, w3), (m1, w2)}
iv. w1 proposes to m1 (2nd on her list), who prefers w1 to w2. m1 breaks his engagement with
w2 and accepts w1’s proposal. E = {(m2, w3), (m1, w1)}
v. w2 proposes to m2, who prefers w3 to w2 and so declines the proposal. E = {(m2, w3), (m1, w1)}
vi. w2 proposes to m3 (last on her list!), who accepts. E = {(m2, w3), (m1, w1), (m3, w2)}
vii. The algorithm terminates with the correct solution S = {(m2, w3), (m1, w1), (m3, w2)}.
(b) Example #2:
w1: m1 m2 m1: w1 w2
w2: m1 m2 m2: w2 w1
We’ll again use G-S with women proposing, working top to bottom.
i. w1 proposes to m1, who accepts. E = {(m1, w1)}
ii. w2 proposes to m1, who declines (prefers w1 to w2). E = {(m1, w1)}
iii. w2 proposes to m2, who accepts. E = {(m1, w1), (m2, w2)}
iv. The algorithm terminates with the correct solution S = {(m1, w1), (m2, w2)}.
2. Design an instance that specifically challenges the correctness (or performance) of your algorithm.
This time, we suggest designing an instance with n = 3 to be solved by G-S with men proposing
where either the maximum number of proposals is made or men get as bad an outcome as possible.
SOLUTION: We’ll focus on men getting as bad an outcome as possible. We’ll work through this
by ignoring irrelevant choices and trying to make (and backtrack to) relevant choices carefully. For
example, who proposes first is an irrelevant question. It might as well be m1. If it were m2 instead,
we could just swap the second and first man and make it m1.
So, m1 proposes first and may as well propose to w1:
m1: w1 w1:
m2: w2:
m3: w3:
w1 has to accept, but we want her to eventually break off the engagement with m1 for someone else
(to make the outcome bad for m1). Let’s have m2 propose to her and w1 accept. Notice that we
don’t specify all of the preferences for w1, just enough to know she prefers m2 to m1:
m1: w1 w1: m2 > m1
m2: w1 w2:
m3: w3:
This work is licensed under a Creative Commons Attribution 4.0 International License. cb
For license purposes, the author is the University of British Columbia.
http://creativecommons.org/licenses/by/4.0/
Note that that was a choice, however. We could have had both m2 and m3 prefer w2 to w1. We may
have to come back to that. (Why not w3? Well, if they both prefer w3, we’ll just swap w2 and w3. If
the prefer different people, then G-S will stop after three iterations with all men getting their top
choice, which isn’t what we want! Can you see why?)
Then, we’ll have m3 propose to w1 and be accepted. Again, this is a choice we may have to revisit!
m1: w1 w1: m3 > m2 > m1
m2: w1 w2:
m3: w1 w3:
Oh, wait. If we do that, m3 will definitely end up with w1, getting his top choice. Can we force him
to do worse? Let’s try a different approach and have m3 propose to w2.
m1: w1 w1: m2 > m1
m2: w1 w2: m3
m3: w2 w3:
Then, m1 can break in on that engagement:
m1: w1 w2 w1: m2 > m1
m2: w1 w2: m1 > m3
m3: w2 w3:
m2 is still engaged to w1. So, maybe m3 can break in on that engagement now? That doesn’t give
m3 his worst outcome, though. Maybe we’ll need to come back to this?
m1: w1 w2 w1: m3 > m2 > m1
m2: w1 w2: m1 > m3
m3: w2 w1 w3:
Now, m2 can break in on m1:
m1: w1 w2 w1: m3 > m2 > m1
m2: w1 w2 w2: m2 > m1 > m3
m3: w2 w1 w3:
And, finally, m1 can propose to w3:
m1: w1 w2 w3 w1: m3 > m2 > m1
m2: w1 w2 w2: m2 > m1 > m3
m3: w2 w1 w3: m1
Is that the best we can do? Could we get another man to his worst choice? It turns out we actually
cannot. See if you can prove it. Specifically: if a man proposes to the last woman on his preference
list, G-S must terminate on that iteration. (Hint: how many couples must already be engaged for a
man to propose to the last woman on his preference list? And. . . can that last woman herself already
be engaged?)
Let’s turn that into an actual instance:
m1: w1 w2 w3 w1: m3 m2 m1
m2: w1 w2 w3 w2: m2 m1 m3
m3: w2 w1 w3 w3: m1 m2 m3
This work is licensed under a Creative Commons Attribution 4.0 International License. cb
For license purposes, the author is the University of British Columbia.
http://creativecommons.org/licenses/by/4.0/
8 Repeat!
Hopefully, we’ve already bounced back and forth between these steps in today’s worksheet! You usually
will have to. Especially repeat the steps where you generate instances and challenge your approach(es).
SOLUTION: We bounced back and forth quite a bit, even in this carefully crafted solution.
P.S. No solutions to challenge problems, but feel free to talk to us about them!
This work is licensed under a Creative Commons Attribution 4.0 International License. cb
For license purposes, the author is the University of British Columbia.
http://creativecommons.org/licenses/by/4.0/
Trivial and Small Instances
Represent the Problem
Represent the Solution
Similar Problems
Brute Force?
Promising Approach
Challenge Your Approach
Repeat!