CPSC 320 Sample Solution, Reductions & Resident Matching: A Residentectomy
CPSC 320 Sample Solution, Reductions & Resident Matching: A
Residentectomy
September 19, 2018
A group of residents each needs a residency in some hospital. A group of hospitals each need some
number (one or more) of residents, with some hospitals needing more and some fewer. Each group has
preferences over which member of the other group they’d like to end up with. The total number of slots in
hospitals is exactly equal to the total number of residents.
We want to �ll the hospitals slots with residents in such a way that no resident and hospital that
weren’t matched up will collude to get around our suggestion (and give the resident a position at that
hospital instead).
1 Trivial and Small Instances
1. Write down all the trivial instances of RHP. We think of an instance as “trivial” roughly if its solution
requires no real reasoning about the problem.
SOLUTION: Certainly instances with 0 hospitals and 0 residents are trivial (solution: no matchings).
Additionally, any time we have one hospital, no matter how big it is (and therefore how many residents
there are), the solution will be trivial: place all residents with that one hospital.
2. Write down two small instances of RHP. Here’s your �rst:
SOLUTION: Here’s one, but it could as well be an SMP instance.
r1: h1 h2 h1: r2 r1
r2: h2 h1 h2: r1 r2
And here is your second. Try to explore something a bit di�erent with this one.
SOLUTION: So, it’s a good idea to make an instance that actually illustrates what’s unique to our
problem. (Otherwise, how will we know what to specify??) Here, the number in parentheses after a
hospital indicates how many slots it has.
r1: h1 h2 h1 (1): r2 r1 r3
r2: h2 h1 h2 (2): r1 r2 r3
r3: h1 h2
3. Although we probably would not call it trivial, there’s a special case where all hospitals have exactly
one slot. What makes this an interesting special case?1
SOLUTION: Any instance like our �rst small instance above where each hospital has exactly one
slot may as well be an SMP instance. That suggests a strong connection between these problems. It
also suggests that the hard part for us is going to be �guring out what to do with hospitals that have
multiple slots.
1Yes, we are doing “Similar Problems” early!
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/
2 Represent the Problem
1. What are the quantities that matter in this problem? Give them short, usable names.
SOLUTION: Generally speaking, these will be the same as in the SMP problem. A few di�erences:
we’ll let n = |R| (the size of the set of residents). Note that |H| ≤ |R|, but H may be much smaller.
We need to know, for each hospital how, big it is. We’ll say that s(h) is the number of slots in hospital
h.
2. Go back up to your trivial and small instances and rewrite them using these names.
SOLUTION: Not really necessary here, but that parenthetical after each hospital certainly was
necessary to give its number of slots!
3. Describe using your representational choices above what a valid instance looks like:
SOLUTION: Again, this is much like SMP with some extra constraints, mostly focused on the s
function that tells us how many slots a hospital has. In particular, for all h ∈ H, s(h) > 0. Further,
n =
∑
h∈H s(h). That is, there are exactly enough slots for the residents.
3 Represent the Solution
1. What are the quantities that matter in the solution to the problem? Give them short, usable names.
SOLUTION: Much like with SMP, the pairings between hospitals and residents matter. There are
at least two ways to handle the fact that every hospital can match with multiple residents. (1) Use
the same format as SMP but allow each hospital to appear multiple times. (2) Use tuples of a hospital
and a set of residents.
We’ll use (1).
2. Describe using these quantities makes a solution valid and good:
SOLUTION: Crucially, each resident must appear in exactly one tuple (be paired with one hospital),
while each hospital h must appear in exactly s(h) tuples (be paired with as many residents as it has
slots). Otherwise, this isn’t a matching of residents with hospitals at all.
BUT, what makes this matching stable? It’s not quite the same as SMP. In particular, a resident
will still want to get out of her matching if she can match with a hospital she prefers, but under what
circumstances will a hospital agree to give up one of its current residents for her? Clearly, it has to
prefer her to someone it was assigned. And, if it prefers her to anyone it was assigned, it prefers her
to the resident it was assigned that it least prefers.
So, a good de�nition of an instability is “a hospital h matched with residents Hh = {r′1, r
′
2, . . . r
′
s(h)
}
and resident r matched with h′ such that r prefers h to h′ and h prefers r to the member of Hh it
least prefers (the ‘worst’ member).”
3. Go back up to your trivial and small instances and write out one or more solutions to each using
these names.
SOLUTION: Let’s actually write this here and just bring down the example:
r1: h1 h2 h1 (1): r2 r1 r3
r2: h2 h1 h2 (2): r1 r2 r3
r3: h1 h2
Using our notation, a solution might be {(h1, r1), (h2, r2), (h2, r3)}. (This happens to be the only
stable solution to this instance.)
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. Draw at least one solution.
SOLUTION: Working on the same repeated instance, here’s that solution:
LATEX
r1
r2
r3
h1
h2
4 Similar Problems
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: Obviously this is similar to SMP. It also has some similarities to USMP. (Perhaps adding
fake entities to the hospital side will balance things out??)
5 Brute Force?
We have a way to test if something that looks like a solution but may have an instability is stable. (From
the “Represent the Solution” step.) That is, given a “valid” solution, we can check whether it’s “good”.
1. Sketch an algorithm to produce every valid solution. (It will help to give a name to your algorithm
and its parameters, especially if your algorithm is recursive.)
This will be similar to the brute force algorithm for SMP (from the challenge problems).
SOLUTION: A bit less formally than last time, here’s a solution sketch for an algorithm All-
Solns(H, R, s):
(a) If |H| = 0, return {∅}.
(b) Otherwise, let r be the �rst element of R.
(c) And, let M be an empty set (of solutions).
(d) And, for each h ∈ H:
i. Produce new set R′ = R− {r}.
ii. Produce new function s′ = s except that s′(h) = s(h)− 1.
iii. Produce new set H ′ as follows: if s′(h) = 0, then H ′ = H − {h}; otherwise, H ′ = H. (In
other words, strip out r and one slot from h, removing h if it gets to 0 slots.)
iv. For every solution m ∈ AllSolns(H ′, R′, s′), add {(h, r)} ∪m to M .
(e) Finally, return M
2. Choose an appropriate variable to represent the “size” of an instance.
SOLUTION: n seems appropriate.
3. Exactly or asymptotically, how many such “valid solutions” are there? (It will help to give a name
to the number of solutions as a function of instance size.)
SOLUTION: This is pretty messy. In particular, the �rst hospital can be grouped with any subset
of the residents of size s(h1), and subsequent hospitals have that many fewer residents to “choose
from”. Overall, this looks something like n!∏
h∈H(s(h))!
. The point here is that the larger the hospitals
are, the fewer solutions there are. Indeed, if there’s one hospital taking almost all the residents, we
actually have a small solution space to explore. However, if there are even two roughly-equal sized
hospitals, we’re looking at n!
(n/2)!2
, which is super-exponentially huge.
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. Exactly or asymptotically, how long will it take to test whether a solution form is valid and good with
a naive approach? (Write out the naive algorithm if it’s not simple!)
SOLUTION: Since we need to know the “worst” resident matched to each hospital, we might as well
start by picking out that worst resident for each hospital. That takes O(n) = O(|R|) time. Then, for
each hospital/resident pair (of which there are |H| × |R|), if they’re not matched, we check whether
they prefer each other to their partners (in the hospital’s case, its “worst” partner).
With e�cient solutions to each step (see 2.3 of the textbook!), we should be able to do this in
O(|H| × |R|) time, or if hospitals take only a reasonable (constant, actually) number of residents,
about O(n2) time.
5. Will brute force be su�cient for this problem for the domains we’re interested in?
SOLUTION: Not unless some hospital is taking almost everyone!
6 Promising Approach
Describe�in as much detail as you can�an approach to solve this problem using a reduction. We reduce
from RHP to some other problem B.
1. Choose a problem B to reduce to.
SOLUTION: Let’s reduce to SMP.
2. Change an instance of RHP into an instance of B.
SOLUTION: Here’s our running example again:
r1: h1 h2 h1 (1): r2 r1 r3
r2: h2 h1 h2 (2): r1 r2 r3
r3: h1 h2
We need to put one more item on the right. We also need to make sure h2 gets matched with two
residents. It seems like we can solve both these problems at once by “splitting up” h2:
r1: h1 h2 h1: r2 r1 r3
r2: h2 h1 h2_1: r1 r2 r3
r3: h1 h2 h2_2: r1 r2 r3
Now, each “half” of h2 is its own “hospital”. This isn’t an SMP instance yet, however. The residents
don’t have enough preferences! Well, each resident will want the two h2 slots essentially the same,
but we don’t allow ties. So, we’ll just order them arbitrarily. (Why not in numerical order?)
r1: h1 h2_1 h2_2 h1: r2 r1 r3
r2: h2_1 h2_2 h1 h2_1: r1 r2 r3
r3: h1 h2_1 h2_2 h2_2: r1 r2 r3
Now that looks like an SMP instance.
3. Change the solution to B into a solution to RHP.
SOLUTION: Running Gale-Shapley gives this solution: {(h1, r1), (h21 , r2), (h22 , r3)}.
That’s already very close to the solution we found by hand of {(h1, r1), (h2, r2), (h2, r3)}. It looks like
we just need to erase the subscripts on the hospitals, since hospital-slots are no longer separate.
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. Design an algorithm to change any valid RHP instance into an instance of B.
SOLUTION: This is probably the trickiest part. We need to eliminate the s function that tells us
the size of hospitals. It also seems likely (as in USMP) that we’ll want to make the two sets (residents
and hospitals) have the same size.
One way to accomplish both of those would be to make “clone” hospitals for every hospital that takes
more than one resident. Actually, to make it easier to describe, let’s say that will split every hospital
h into s(h) “hospital-slots”. Since we know
∑
h∈H s(h) is exactly the number of residents, this will
give us a set of hospital-slots of the same size as the number of residents.
However, we’re not done. Each of these hospital-slots needs a preference list. And, the residents’
preference lists must be augmented to include all these hospital slots instead of (as well as?) the
original hospital.
Well, we said “clone” for hospitals; so, let’s try having each hospital-slot have the same preference
list as the hospital it came from.
There’s no reason to think one “clone” is better than another, but we may as well have each resident
replace a hospital h in their preference list with h1, h2, . . . , hk for k = s(h). That is, where they
had hospital h, they now have one entry in order for each hospital-slot broken o� of h (but all are
worse than the hospital-slots coming from hospitals the resident preferred and better than those from
hospitals the resident liked less).
At that point, we have an SMP instance.
5. Design an algorithm to change the B instance’s solution into the RHP instance’s solution.
SOLUTION: SMP will give us back a stable, perfect matching. With the solution representation we
used, the only thing di�erent about the SMP solution from a possibly-stable RHP solution would be
the subscripts on the hospital-slots. If we erase those, then since each hospital-slot had one partner and
each hospital had s(h) hospital-slots, each hospital in the RHP solution will now have s(h) partners,
as we expect. (The residents will still each have exactly one partner, since we haven’t changed them!)
6. Prove that the solution you get to the RHP instance is guaranteed to be correct. (Depending on your
chosen reduction, you likely have a stable solution to an instance of B and need to show that you
get a correct solution to the RHP instance, i.e., that the solution is “valid” (has the right form) and
“good” (is stable). So, you’ll prove either if B’s solution is correct, RHP’s solution is correct or the
contrapositive, if RHP’s solution is incorrect, then B’s is incorrect as well.)
SOLUTION: I’ll do a bit of both. First, we already showed that SMP’s perfect matching gives us
a matching that follows the basic rules of RHP, i.e., each hospital is partnered with exactly the right
number of residents (and each resident with exactly one hospital).
Now, for the second constraint (stability), let’s prove the contrapositive. So, assuming RHP’s solution
is unstable, we’ll show that SMP’s is unstable.
Since RHP’s solution is unstable, there must be some pair h and r that cause the instability.
(Maybe multiple, but we don’t care about that.) In particular: h is matched with residents Hh =
{r′1, r
′
2, . . . r
′
s(h)
} and resident r is matched with h′ such that r prefers h to h′ and h prefers r to the
member of Hh it least prefers (the ‘worst’ member).
The pairing of r with h′ must have come from SMP’s pairing of r with one of h′’s slots, say h′k. Let’s
also look at SMP’s pairing of h with its least-preferred partner r′. We don’t know which slot of h’s
that is, but we’ll say it’s hj . We’d like to see that just as r and h form an instability in RHP, r and
hj form an instability in SMP.
Do they form an instability?
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/
Well, r prefers h to h′ in RHP. The “cloning” we did to split hospitals into hospital-slots keeps all
the slots of a hospital together so they all still go before the same hospitals they used to go before.
Thus, r must prefer all slots of h to all slots of h′ and so prefer hj to h
′
k.
Similarly, all of h’s slots have the same preferences as h. So, just as h prefers r to r′, hj must prefer
r to r′.
Thus, r and hj do indeed constitute an instability.
Why did we do all that again? Since the SMP solution is unstable if the RHP solution is unstable,
that shows that the RHP solution is stable if the SMP solution is stable. We know the SMP solution
is stable, which means the RHP one is as well!
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: I’ll leave this to you! (I cheated and jumped straight to a correct solution; so, this
part is not as important for me.)
2. Design an instance that speci�cally challenges the correctness (or performance) of your algorithm:
SOLUTION: I’ll leave this to you for the same reasons!
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