CPSC 320: Reductions & Resident Matching *
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
1.
2.
Trivial and Small Instances
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.
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 dierent with this one.
SOLUTION: Let’s make an instance that actually illustrates what’s unique to the RHP. (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
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?
SOLUTION: Instances 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.
3.
*
Copyright Notice: UBC retains the rights to this document. You may not distribute this document without permission.
1
2
1.
2.
3.
3
1.
2.
Represent the Problem
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 dierences: 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 many slots it has. We’ll use s(h) to denote the number of slots in hospital h.
Rewrite one of your small instances using these names.
SOLUTION: Left to you.
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.
Represent the Solution
What are the quantities that matter in the solution to the problem? Give them short, usable names.
SOLUTION: 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).
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 denition of an instability is “a hospital h matched with residents Hh = {r1′ , r2′ , . . . 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.
Write out one or more solutions to one of your small instances using these names. SOLUTION: We’ll work with this example:
r1: h1 h2
r2: h2 h1
r3: h1 h2
h1 (1): r2 r1 r3
h2 (2): r1 r2 r3
notation, a solution might be {(h1, r1), (h2, r2), (h2, r3)}. (This happens
Using our
stable solution to this instance.)
to be the only
2
4
SOLUTION: Working on the same repeated instance, here’s that solution:
r1 h1
r2 h2
r3
Similar Problems
4. Draw at least one solution.
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. Choose an appropriate variable to represent the “size” of an instance. SOLUTION: n seems appropriate.
2. What can you say about the number of valid solutions, as a function of the instance size? Does it grow exponentially? Worse? (If you have time, or if it is helpful, sketch an algorithm to produce every valid solution, similar to the brute force algorithm for generating valid SMP solutions which is covered in the sample solutions to the rst worksheet. It will help to give a name to your algorithm and its parameters, especially if your algorithm is recursive.)
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! . Notice that the larger the hospitals are, the h∈H (s(h))!
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! , which is very large (worse than 2Θ(n)). (n/2)!2
And here’s an informal solution sketch for an algorithm AllSolns(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. Foreverysolutionm∈AllSolns(H′,R′,s′),add{(h,r)}∪mtoM.
(e) Finally, return M
3
6
3.
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 ecient 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.
Will brute force be sucient for this problem for the domains we’re interested in? SOLUTION: Not unless some hospital is taking almost everyone!
Promising Approach
4.
We’ll use a reduction for our promising approach. Informally, a reduction is simply a way of solving a new problem by leveraging an algorithm that solves an already familiar problem. Here we describe reductions somewhat formally, so you know what you are doing when proceeding informally. We need two denitions:
An instance of a problem is simply a valid input, drawn from the space of possible inputs the problem allows. For example, the 4-element array [5, 1, 4, 3] is an instance of the problem of sorting arrays of integers.
A reduction from problem A to problem B provides a way to solve problem A by using an algorithm that solves B. There are two key parts to a reduction: (i) an algorithm that transforms any instance, say I, of problem A to an instance, say I′, of B, and then (ii) an algorithm that transforms a solution for I′ back to a solution for I. (When coming up with a reduction, you don’t need to design the algorithm that solves B; we think of that algorithm as a “black box” because the reduction does not depend on its details.) 1 Here’s a diagram of how the parts t together:
Describe an approach to solve RHP using a reduction, along with an algorithm that solves B. We reduce from RHP to some other problem B.
1Reductions can be dened more generally, where part (i) constructs many instances of B. 4
1. Choose a problem B to reduce to. SOLUTION: Let’s reduce to SMP.
2. Reduction part (i) example: Transform a small instance of RHP into an instance of B. SOLUTION: Here’s our running example again:
r1: h1 h2 h1(1):r2r1r3 r2: h2 h1 h2(2):r1r2r3 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
r2: h2 h1
r3: h1 h2
h1: r2 r1 r3
h2_1: r1 r2 r3
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
r2: h2_1 h2_2 h1
r3: h1 h2_1 h2_2
h1: r2 r1 r3
h2_1: r1 r2 r3
h2_2: r1 r2 r3
Now that looks like an SMP instance.
3. Reduction part (ii) example: Transform a solution to your B instance into a solution to the RHP instance.
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.
4. Generalize: part (i): Design an algorithm to transform any instance I of RHP into an instance I′ 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.
5
7
8
5.
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.
Generalize part (ii): Design an algorithm to transform a solution S′ for I′ of B into a solution S for
instance I of. RHP.
SOLUTION: The Gale-Shapley algorithm will give us back a stable, perfect matching M to our SMP instance I′. With the solution representation we used, the only thing dierent about M 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 match and each hospital had s(h) hospital-slots, each hospital in the RHP solution will now have s(h) matches, as we expect. The residents will still each have exactly one match, since we haven’t changed them.
Challenge Your Approach
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: Left to you.
Design an instance that specically challenges the correctness (or performance) of your algorithm:
SOLUTION: Left to you.
Proof of Correctness
1.
2.
See if you can prove that your reduction produces a correct solution for any RHP instance. This may well involve showing that if S′ is a good solution for the instance I′ produced by part (i) of your reduction (where S′ is the output of the black box algorithm for problem B in the diagram), then part (ii) of your reduction transforms S′ into a good (i.e., valid and stable) solution S for the original instance I of RHP.
SOLUTION: First, we already showed that any good solution S′ (i.e., stable matching) for instance I′ of SMP 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). So solution S must be valid.
To show that S is stable, let’s prove the contrapositive: Assuming that S is unstable, we’ll show that S′ must also be unstable, contradicting our assumption that S′ is good.
Since S 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 = {r1′ , r2′ , . . . r′ } and resident
s(h)
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 S’s pairing of r with one of h′’s slots, say h′k. Let’s also
look at S’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 with respect to ′, r and hj form an instability with respect to S′.
Do they form an instability?
Well, r prefers h to h′ in instance I of RHP. The “cloning” we did to split hospitals into hospital-slots in instance I′ keeps all the slots of a hospital together. So, in instance I′, r must prefer all slots of h to all slots of h′, and so r prefers hj to h′k.
6
Similarly, all of h’s slots in I′ have the same preferences as h in instance I. So, just as h prefers r to r′ inI′,hj mustpreferrtor′ inI.
So, r and hj do indeed constitute an instability with respect to S.
Why did we do all that again? Since the SMP solution S′ is unstable if the RHP solution S is unstable, we can conclude that the RHP solution is stable if the SMP solution is stable. We know the SMP solution S′ is stable, which means the RHP solution S is as well!
7