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