1 1
, Stable Matching n
Note: Exercises denoted with an asterisk ( ) tend to be more difficult, or to rely on
n n n n n n n n n n n n n n n n
some of the more advanced material.
n n n n n n
1. Gale and Shapley published their paper on the stable marriage problem in 1962; but a
n n n n n n n n n n n n n n
version of their algorithm had already been in use for ten years by the National Resident
n n n n n n n n n n n n n n n n
Matching Program, for the problem of assigning medical residents to hospitals.
n n n n n n n n n n n
Basically, the situation was the following. There were m hospitals, each with a certain
n n n n n n n n n n n n n
number of available positions for hiring residents. There were n medical students
n n n n n n n n n n n n
graduating in a given year, each interested in joining one of the hospitals. Each hospital
n n n n n n n n n n n n n n n
had a ranking of the students in order of preference, and each student had a
n n n n n n n n n n n n n n n
nranking of the hospitals in order of preference. We will assume that there were more
n n n n n n n n n n n n n n
students graduating than there were slots available in the m hospitals.
n n n n n n n n n n n
The interest, naturally, was in finding a way of assigning each student to at most one
n n n n n n n n n n n n n n n
hospital, in such a way that all available positions in all hospitals were filled.
n n n n n n n n n n n n n n
n(Since we are assuming a surplus of students, there would be some students who do
n n n n n n n n n n n n n n
not get assigned to any hospital.)
n n n n n n
We say that an assignment of students to hospitals is stable if neither of the following
n n n n n n n n n n n n n n n
situations arises.
n n
• First type of instability: There are students s and s , and a hospital h, so that
n n n n n n n n n n n n n n n n
– s is assigned to h, and n n n n n
– sr is assigned to no hospital, and
n n n n n n
– h prefers sr to s. n n n n
r r
Second type of instability: There are students s and s , and hospitals h and h ,
n n n n n n n n n n n n n n n n
so that n
– s is assigned to h, and
n n n n n
– sr is assigned to hr, and
n n n n n
– h prefers sr to s, and
n n n n n
– sr prefers h to hr.
n n n n
So we basically have the stable marriage problem from class, except that (i) hospitals
n n n n n n n n n n n n n
generally want more than one resident, and (ii) there is a surplus of medical
n n n n n n n n n n n n n n
nstudents.
Show that there is always a stable assignment of students to hospitals, and give an
n n n n n n n n n n n n n n
efficient algorithm to find one. The input size is Θ(mn); ideally, you would like
n n n n n n n n n n n n n n
nto find an algorithm with this running time.
n n n n n n n
Solution. The algorithm is very similar to the one from class. At any point in
n n n n n n n n n n n n n n n
ntime, a student is either “committed” to a hospital or “free.” A hospital either has
n n n n n n n n n n n n n n
available positions, or it is “full.” The algorithm is the following:
n n n n n n n n n n n
2
, While some hospital hi has available positions hi offers a position to the next
n n n n n n n n n n n n n
student sj on its preference list if sj is free then sj accepts the offer else
n n n n n n n n n n n n n n n n
(sj is already committed to a hospital hk) if sj prefers hk to hi then sj
n n n n n n n n n n n n n n n n
remains committed to hk else sj becomes committed to hi the number of
n n n n n n n n n n n n n
available positions at hk increases by one. the number of available
n n n n n n n n n n n
positions at hi decreases by one.
n n n n n n
The algorithm terminates in O(mn) steps because each hospital offers a
n n n n n n n n n n
npositions to a student at most once, and in each iteration, some hospital offers a
n n n n n n n n n n n n n n
position to some student.
n n n n
Suppose there are pi > 0 positions available at hospital hi. The algorithm terminates
n n n n n n n n n n n n n
with an assignment in which all available positions are filled, because any hospital that
n n n n n n n n n n n n n n
did not fill all its positions must have offered one to every student; but then, all
n n n n n n n n n n n n n n n n
these students would be committed to some hospital, which contradicts our
n n n n n n n n n n n
nassumption that n
m
i= pi < n.
n
n n
1
Finally, we want to argue that the assignment is stable. For the first kind of
n n n n n n n n n n n n n n
instability, suppose there are students s and sr, and a hospital h as above. If h
n n n n n n n n n n n n n n n n
prefers sr to s, then h would have offered a position to sr before it offered one to s;
n n n n n n n n n n n n n n n n n n n
from then on, sr would have a position at some hospital, and hence would not be
n n n n n n n n n n n n n n n n
free at the end — a contradiction.
n n n n n n n
For the second kind of instability, suppose that (hi, sj) is a pair that causes instability.
n n n n n n n n n n n n n n n
Then hi must have offered a position to sj, for otherwise it has pi residents all of
n n n n n n n n n n n n n n n n n
nwhom it prefers to sj. Moreover, sj must have rejected hi in favor of some hk which
n n n n n n n n n n n n n n n n
he/she preferred; and sj must therefore be committed to some hl (possibly different
n n n n n n n n n n n n n
from hk) which he/she also prefers to hi.
n n n n n n n n
2. We can think about a different generalization of the stable matching problem, in which
n n n n n n n n n n n n n
ncertain man-woman pairs are explicitly forbidden. In the case of employers and ap-
n n n n n n n n n n n n
nplicants, picture that certain applicants simply lack the necessary qualifications or
n n n n n n n n n n
n degree; and so they cannot be employed at certain companies, however desirable they
n n n n n n n n n n n n
nmay seem. Concretely, we have a set M of n men, a set W of n women,
n n n n n n n n n n n n n n n n
nand a set F ⊆ M × W of pairs who are simply not allowed to get married.
n n n n n n n n n n n n n n n n n
n Each man m ranks all the women w for which (m, w) /∈ F , and each woman wr ranks
n n n n n n n n n n n n n n n n n n n
nall the men mr for which (mr, wr) /∈ F .
n n n n n n n n n n
In this more general setting, we say that a matching S is stable if it does not exhibit
n n n n n n n n n n n n n n n n n
nany of the following types of instability.
n n n n n n
(i) There are two pairs (m, w) and (mr, wr) in S with the property that m prefers wr
n n n n n n n n n n n n n n n n n
to w, and wr prefers m to mr. (The usual kind of instability.)
n n n n n n n n n n n n
(ii) There is a pair (m, w) S, and a man mr, so that mr is not part of any pair in the
n n n n n n n n n n n n n n n n n n n n n n
matching, (mr, w) F , and w prefers mr to m. (A single man is more
n n n n n n n n n n n n n n n n
desirable and not forbidden.)
n n n n
3
, (iir) There is a pair (m, w)
n S, and a woman wr, so that wr is not part of
n n n n n n n n n n n n n n n n n n
any pair in the matching, (m, wr) F , and m prefers wr to w. (A single woman
n n n n n n n n n n n n n n n n n n
is more desirable and not forbidden.)
n n n n n n
(iii) There is a man m and a woman w, neither of which is part of any pair in the
n n n n n n n n n n n n n n n n n n
matching, so that (m, w) F . (There are two single people with nothing prevent-
n n n n n n n n n n n n n n n
ing them from getting married to each other.)
n n n n n n n n
Note that under these more general definitions, a stable matching need not be a perfect
n n n n n n n n n n n n n n
matching.
n
Now we can ask: for every set of preference lists and every set of forbidden pairs, is
n n n n n n n n n n n n n n n n
n there always a stable matching? Resolve this question by doing one of the
n n n n n n n n n n n n
nfollowing two things: (a) Giving an algorithm that, for any set of preference lists and
n n n n n n n n n n n n n n
forbidden pairs, produces a stable matching; or (b) Giving an example of a set of
n n n n n n n n n n n n n n n
preference lists and forbidden pairs for which there is no stable matching.
n n n n n n n n n n n n
Solution. There is always a stable matching, even in the general model with forbidden
n n n n n n n n n n n n n
pairs. The most direct way to prove this is through an algorithm that is almost the
n n n n n n n n n n n n n n n n
same as the one we used for the basic stable matching problem in class; indeed, the
n n n n n n n n n n n n n n n n
only change is that our condition for the While loop will say: “While there is a
n n n n n n n n n n n n n n n n
nman m who is free and hasn’t proposed to every woman w for which (m, w) F .”
n n n n n n n n n n n n n n n n n n
nHere is the algorithm in full:
n n n n n
Initially all m ∈ M and w ∈ W are free While there is a man m
n n n n n n n n n n n n n n n n
nwho is free and hasn’t proposed to every woman w for which (m, w)
n n n n n n n n n n n n n
n F Choose such a man m Let w be the highest-ranked woman in
n n n n n n n n n n n n n
nm’s preference list to which m has not yet proposed If w is free
n n n n n n n n n n n n n
nthen (m, w) become engaged Else w is currently engaged to mr If w
n n n n n n n n n n n n n
nprefers mr to m then m remains free Else w prefers m to mr (m, w) become
n n n n n n n n n n n n n n n n
nengaged mr becomes free Endif Endif Endwhile Return the set S of
n n n n n n n n n n n
nengaged pairs n
Now, facts (1.1) - (1.3) from the book remain true; and we don’t have to worry about
n n n n n n n n n n n n n n n n
establishing that the resulting matching S is perfect (indeed, it may not be). We also
n n n n n n n n n n n n n n n
notice an additional pairs of facts. If m is a man who is not part of a pair in S,
n n n n n n n n n n n n n n n n n n n n
then m must have proposed to every non-forbidden woman; and if w is a woman who
n n n n n n n n n n n n n n n n
is not part of a pair in S, then it must be that no man ever proposed to w.
n n n n n n n n n n n n n n n n n n n
Finally, we need only show n n n n
• There is no instability with respect to the returned matching S.
n n n n n n n n n n
Our general definition of instability has four parts; this means that we have to
n n n n n n n n n n n n n
nmake sure none of the four bad things happens.
n n n n n n n n
First, suppose that there is an instability of type (i), consisting of pairs (m, w)
n n n n n n n n n n n n n n
nand (mr, wr) in S with the property that m prefers wr to w, and wr prefers m to mr.
n n n n n n n n n n n n n n n n n n n
nIt follows that m must have proposed to wr; so wr rejected m, and thus she
n n n n n n n n n n n n n n n
4
, Stable Matching n
Note: Exercises denoted with an asterisk ( ) tend to be more difficult, or to rely on
n n n n n n n n n n n n n n n n
some of the more advanced material.
n n n n n n
1. Gale and Shapley published their paper on the stable marriage problem in 1962; but a
n n n n n n n n n n n n n n
version of their algorithm had already been in use for ten years by the National Resident
n n n n n n n n n n n n n n n n
Matching Program, for the problem of assigning medical residents to hospitals.
n n n n n n n n n n n
Basically, the situation was the following. There were m hospitals, each with a certain
n n n n n n n n n n n n n
number of available positions for hiring residents. There were n medical students
n n n n n n n n n n n n
graduating in a given year, each interested in joining one of the hospitals. Each hospital
n n n n n n n n n n n n n n n
had a ranking of the students in order of preference, and each student had a
n n n n n n n n n n n n n n n
nranking of the hospitals in order of preference. We will assume that there were more
n n n n n n n n n n n n n n
students graduating than there were slots available in the m hospitals.
n n n n n n n n n n n
The interest, naturally, was in finding a way of assigning each student to at most one
n n n n n n n n n n n n n n n
hospital, in such a way that all available positions in all hospitals were filled.
n n n n n n n n n n n n n n
n(Since we are assuming a surplus of students, there would be some students who do
n n n n n n n n n n n n n n
not get assigned to any hospital.)
n n n n n n
We say that an assignment of students to hospitals is stable if neither of the following
n n n n n n n n n n n n n n n
situations arises.
n n
• First type of instability: There are students s and s , and a hospital h, so that
n n n n n n n n n n n n n n n n
– s is assigned to h, and n n n n n
– sr is assigned to no hospital, and
n n n n n n
– h prefers sr to s. n n n n
r r
Second type of instability: There are students s and s , and hospitals h and h ,
n n n n n n n n n n n n n n n n
so that n
– s is assigned to h, and
n n n n n
– sr is assigned to hr, and
n n n n n
– h prefers sr to s, and
n n n n n
– sr prefers h to hr.
n n n n
So we basically have the stable marriage problem from class, except that (i) hospitals
n n n n n n n n n n n n n
generally want more than one resident, and (ii) there is a surplus of medical
n n n n n n n n n n n n n n
nstudents.
Show that there is always a stable assignment of students to hospitals, and give an
n n n n n n n n n n n n n n
efficient algorithm to find one. The input size is Θ(mn); ideally, you would like
n n n n n n n n n n n n n n
nto find an algorithm with this running time.
n n n n n n n
Solution. The algorithm is very similar to the one from class. At any point in
n n n n n n n n n n n n n n n
ntime, a student is either “committed” to a hospital or “free.” A hospital either has
n n n n n n n n n n n n n n
available positions, or it is “full.” The algorithm is the following:
n n n n n n n n n n n
2
, While some hospital hi has available positions hi offers a position to the next
n n n n n n n n n n n n n
student sj on its preference list if sj is free then sj accepts the offer else
n n n n n n n n n n n n n n n n
(sj is already committed to a hospital hk) if sj prefers hk to hi then sj
n n n n n n n n n n n n n n n n
remains committed to hk else sj becomes committed to hi the number of
n n n n n n n n n n n n n
available positions at hk increases by one. the number of available
n n n n n n n n n n n
positions at hi decreases by one.
n n n n n n
The algorithm terminates in O(mn) steps because each hospital offers a
n n n n n n n n n n
npositions to a student at most once, and in each iteration, some hospital offers a
n n n n n n n n n n n n n n
position to some student.
n n n n
Suppose there are pi > 0 positions available at hospital hi. The algorithm terminates
n n n n n n n n n n n n n
with an assignment in which all available positions are filled, because any hospital that
n n n n n n n n n n n n n n
did not fill all its positions must have offered one to every student; but then, all
n n n n n n n n n n n n n n n n
these students would be committed to some hospital, which contradicts our
n n n n n n n n n n n
nassumption that n
m
i= pi < n.
n
n n
1
Finally, we want to argue that the assignment is stable. For the first kind of
n n n n n n n n n n n n n n
instability, suppose there are students s and sr, and a hospital h as above. If h
n n n n n n n n n n n n n n n n
prefers sr to s, then h would have offered a position to sr before it offered one to s;
n n n n n n n n n n n n n n n n n n n
from then on, sr would have a position at some hospital, and hence would not be
n n n n n n n n n n n n n n n n
free at the end — a contradiction.
n n n n n n n
For the second kind of instability, suppose that (hi, sj) is a pair that causes instability.
n n n n n n n n n n n n n n n
Then hi must have offered a position to sj, for otherwise it has pi residents all of
n n n n n n n n n n n n n n n n n
nwhom it prefers to sj. Moreover, sj must have rejected hi in favor of some hk which
n n n n n n n n n n n n n n n n
he/she preferred; and sj must therefore be committed to some hl (possibly different
n n n n n n n n n n n n n
from hk) which he/she also prefers to hi.
n n n n n n n n
2. We can think about a different generalization of the stable matching problem, in which
n n n n n n n n n n n n n
ncertain man-woman pairs are explicitly forbidden. In the case of employers and ap-
n n n n n n n n n n n n
nplicants, picture that certain applicants simply lack the necessary qualifications or
n n n n n n n n n n
n degree; and so they cannot be employed at certain companies, however desirable they
n n n n n n n n n n n n
nmay seem. Concretely, we have a set M of n men, a set W of n women,
n n n n n n n n n n n n n n n n
nand a set F ⊆ M × W of pairs who are simply not allowed to get married.
n n n n n n n n n n n n n n n n n
n Each man m ranks all the women w for which (m, w) /∈ F , and each woman wr ranks
n n n n n n n n n n n n n n n n n n n
nall the men mr for which (mr, wr) /∈ F .
n n n n n n n n n n
In this more general setting, we say that a matching S is stable if it does not exhibit
n n n n n n n n n n n n n n n n n
nany of the following types of instability.
n n n n n n
(i) There are two pairs (m, w) and (mr, wr) in S with the property that m prefers wr
n n n n n n n n n n n n n n n n n
to w, and wr prefers m to mr. (The usual kind of instability.)
n n n n n n n n n n n n
(ii) There is a pair (m, w) S, and a man mr, so that mr is not part of any pair in the
n n n n n n n n n n n n n n n n n n n n n n
matching, (mr, w) F , and w prefers mr to m. (A single man is more
n n n n n n n n n n n n n n n n
desirable and not forbidden.)
n n n n
3
, (iir) There is a pair (m, w)
n S, and a woman wr, so that wr is not part of
n n n n n n n n n n n n n n n n n n
any pair in the matching, (m, wr) F , and m prefers wr to w. (A single woman
n n n n n n n n n n n n n n n n n n
is more desirable and not forbidden.)
n n n n n n
(iii) There is a man m and a woman w, neither of which is part of any pair in the
n n n n n n n n n n n n n n n n n n
matching, so that (m, w) F . (There are two single people with nothing prevent-
n n n n n n n n n n n n n n n
ing them from getting married to each other.)
n n n n n n n n
Note that under these more general definitions, a stable matching need not be a perfect
n n n n n n n n n n n n n n
matching.
n
Now we can ask: for every set of preference lists and every set of forbidden pairs, is
n n n n n n n n n n n n n n n n
n there always a stable matching? Resolve this question by doing one of the
n n n n n n n n n n n n
nfollowing two things: (a) Giving an algorithm that, for any set of preference lists and
n n n n n n n n n n n n n n
forbidden pairs, produces a stable matching; or (b) Giving an example of a set of
n n n n n n n n n n n n n n n
preference lists and forbidden pairs for which there is no stable matching.
n n n n n n n n n n n n
Solution. There is always a stable matching, even in the general model with forbidden
n n n n n n n n n n n n n
pairs. The most direct way to prove this is through an algorithm that is almost the
n n n n n n n n n n n n n n n n
same as the one we used for the basic stable matching problem in class; indeed, the
n n n n n n n n n n n n n n n n
only change is that our condition for the While loop will say: “While there is a
n n n n n n n n n n n n n n n n
nman m who is free and hasn’t proposed to every woman w for which (m, w) F .”
n n n n n n n n n n n n n n n n n n
nHere is the algorithm in full:
n n n n n
Initially all m ∈ M and w ∈ W are free While there is a man m
n n n n n n n n n n n n n n n n
nwho is free and hasn’t proposed to every woman w for which (m, w)
n n n n n n n n n n n n n
n F Choose such a man m Let w be the highest-ranked woman in
n n n n n n n n n n n n n
nm’s preference list to which m has not yet proposed If w is free
n n n n n n n n n n n n n
nthen (m, w) become engaged Else w is currently engaged to mr If w
n n n n n n n n n n n n n
nprefers mr to m then m remains free Else w prefers m to mr (m, w) become
n n n n n n n n n n n n n n n n
nengaged mr becomes free Endif Endif Endwhile Return the set S of
n n n n n n n n n n n
nengaged pairs n
Now, facts (1.1) - (1.3) from the book remain true; and we don’t have to worry about
n n n n n n n n n n n n n n n n
establishing that the resulting matching S is perfect (indeed, it may not be). We also
n n n n n n n n n n n n n n n
notice an additional pairs of facts. If m is a man who is not part of a pair in S,
n n n n n n n n n n n n n n n n n n n n
then m must have proposed to every non-forbidden woman; and if w is a woman who
n n n n n n n n n n n n n n n n
is not part of a pair in S, then it must be that no man ever proposed to w.
n n n n n n n n n n n n n n n n n n n
Finally, we need only show n n n n
• There is no instability with respect to the returned matching S.
n n n n n n n n n n
Our general definition of instability has four parts; this means that we have to
n n n n n n n n n n n n n
nmake sure none of the four bad things happens.
n n n n n n n n
First, suppose that there is an instability of type (i), consisting of pairs (m, w)
n n n n n n n n n n n n n n
nand (mr, wr) in S with the property that m prefers wr to w, and wr prefers m to mr.
n n n n n n n n n n n n n n n n n n n
nIt follows that m must have proposed to wr; so wr rejected m, and thus she
n n n n n n n n n n n n n n n
4