In the Design and Analysis of Algorithms, both this course and its predecessor,
we've covered a lot of famous algorithms. We've covered a lot of fundamental data
structures. We've covered lots of killer
applications. And despite the fact that I've tried to
use our time together in the optimal way, giving you the most bang for the buck,
there are fundamental topics we have not had a chance.
To cover. In these final few videos, I want to talk
about things we didn't talk about. I have a few goals.
The first goal is to give you a little bit of literacy and a few more techniques
so at least you've heard of things like bypar type matching, and the maximum flow
problem, and your aware that there are good algorithms for those sorts of
problems. Secondly, I want to get you excited to do
a little bit more study either through further courses or on your own.
And indeed generally the topics that I'll mention in these final few videos are
covered in your more comprehensive textbooks.
On algorithms. Finally I hope to convey something that I
mention in passing, in the past, is that algorithms is not a oscified field.
Rather, it's a vibrant area of research. There's still lot's of things about
fundamental problems of models that we don't get.
Understand. Let's get the ball rolling with a very
fun, classical problem known as stable matching.
We're going to think of stable matching as a graph problem and there's going to
be two sets of nodes, two sets of vertices, U and V.
For historical reasons, we will call these sets the men and the women,
respectively. A non-essential assumption that will make
for simplicity is that these 2 sets of nodes have equal cardinality.
Call that common size N. So for example, maybe N equals 3 and we
can call the first set of nodes A, B and C.
And the second set of nodes D, E and F. Now what's really important about the
stable matching problem is that every node has preferences, there are things
that advance more than others. Specifically each node in U has a rank
list of the nodes in V, each node in V has a rank list of the nodes in U.
So in this example maybe A, B, and C are all on the same page.
They all agree that D is really the best node, it's better than E, but E is
definitely better than F. That is maybe every single node on the
left hand side has the rank listed D, followed by E, followed by F.
By contrast, maybe there's heterogeneous preferences amongst vertices in capital
V. Maybe D thinks a is better than B is
better than C. While E prefers B to C to A.
And finally, F prefers C to A to B. So what might these nodes and these
ranked lists represent? Well, imagine for example that one set is colleges and the
other set is applicants, recent high school graduates.
Each college has a ranking of the applicants based on things like test
scores, grades and the fit that student is for the college.
And each student similarly has a ranking over the colleges of which one's prefers
to go to. Do over others.
As another example you might think about medical residents that is people who just
finished medical school looking for residency and the other side being
hospitals. Again hospitals are going to have a
preference over which recent graduates they accept as residents, residents,
potential residents of course have preferences over which hospital they get
assigned to. So given this data, 2 sets of nodes, and
these rank lists we're interested in computing a stable matching.
So what's a stable matching? Well, first of all, it better give you a perfect
matching. And a perfect matching means that each
node of the left, each node of U is matched to exactly one node of V and vice
versa. In addition to being a perfect matching,
it should also be stable in the sense that there should be no Blocking pair.
What that means, is that if you look at any pair of nodes, little u from capital
u, little v from capital v, if little u and little v are not matched, there
better be a good reason for them not being matched.
Specifically little u better strictly prefer Who it is matched to, call that V
prime, to this alternate V, or if that's not the case, it better be that little v
strictly prefers the node it's matched to, call it U prime, compared to the
alternative. Little u.
So what's the motivation for this definition? Well think about any perfect
matching that fails this stability property.
You're really asking for trouble for that kind of matching.
Specifically u with its wandering eye will spy v and it prefers v over v node v
prime to which It was a sign. Similiary, V is going to return that
gaze. V prefers U by assumption that this
stability property fails over the node U prime to which it was matched, so U and V
are going to have an incentive to essentially elope and disrupt this
Imagine for example that u is a student and V is a college.
And you have a matching that fails the stability property.
Then, this pair this student and this college has an incentive to do a sort of
back room deal after the fact. U might want to withdraw its commitment
from its assigned college, V-prime to try and get into V instead.
And V to college actually wants to sort of withdraw its offer from its
student, U prime, they give it to U instead.
So that's an unstable matching, but as long as there's no blocking pair of this
form, and for every pair which is not matched together there's a good reason
for it, then we deem it a stable Stable matching.
Let me tell you about an extremely elegant and justly famous algorithm for
computing a stable matching, the Gale-Shapley Proposal Algorithm.
Lloyd Shapely was one of the recipients of the 2012 Nobel Prize in economics, in
large part for this algorithm. Had David Gale still been alive, he
surely would have been a co-recipient of that Nobel Prize as well.
Let me explain the algorithm in an example, then I'll give you the general
psudeocode. We start with the empty matching, with
nobody matched with anybody else. And as long as there's some man, some
node on the left hand side which isn't matched to some woman.
We pick an arbitrary unattached man and we let it propose to a woman of its
choice. So we might start for example with The
man C. C says, well, my favorite woman is D, so
let me start by proposing to the woman D. Now D isn't necessarily very impressed
with C, you've noticed C is last in these preference list, but with a lack of other
proposals at the moment, the node D tentatively accepts this proposal from C.
Now we proceed to the next iteration of the wow loop, we look for a man that is
unattached, so maybe we pick B. B now gets its shot at proposing to its
favorite woman. In this case it is also D.
So now the node D has a bit of leverage it has two competing offers from the
nodes B and C and of course it retains the offer from the preferred suitor in
this case D prefers D to C so the edge between C and D gets deleted and replaced
with the edge between B and D. So now both of them at A and C are
unattached. Perhaps in the next iteration we let the
node A gets its shot. It again proposes to the node D, and
again D prefers A to B, so the edge between A and D is going to replace the
edge between B and D. So now we again have 2 on hatched men B
and C, lets say we pick C next so C gets to propose to what ever women it wants
and D is its favorite but it is already being rejected by D and in the algorithm
men will never re-propose to a women who has previously rejected him.
So next on C's list is the women E and so E has that not had any other offer so E.
He tentatively accepts the proposal from C.
But now, once B gets a chance, B will also propose next to E, that's B's next
favorite and it's already been rejected by D.
And E prefers B to C, so we will replace the edge between C and E with the edge
between B and E. And so now, finally, the man C is the
only one that remains unattached and it has no choice but to propose to its final
option the node F. F actually happily accepts that because c
is on the top of f's list. And that leaves us with the matching That
matches A with D, B with E, and C with F. This is clearly a perfect matching.
I'll let you check that's is also a stable matching.
Having traced through this example, I hope that the pseudocode for the general
algorithm will not surprise you. So we have a main y loop.
In each iteration we pick some man who is not yet engaged to any woman, call that
man u. U then proposes to his favorite woman,
the top ranked woman with the constraint that he will not propose a second time to
any woman who has already rejected him. Each woman then behaves in the obvious
way which is to keep track of all of the suitors, all of the men that have
proposed to her and to retain as a tentative engagement only the proposal
from their favorite, that is highest ranked suitor.
Notice this algorithm maintains the invariant that the current set of
engagements is a matching. Not necessarily a perfect matching, but a
matching. That is, at any given time a man is
engaged tentatively to, at most, one woman.
And every woman is tentatively engaged to, at most, one.
The Gale-shapley theorem states that, not only does this algorithm terminate
quickly, not only does it terminate quickly with a perfect matching.
But in fact, it terminates quickly, namely, in a quadratic number of
iterations at most. With a stable match.
In particular, this theory, this algorithm provides constructive proof
that a stable matching always exists, no matter what the preference of the node
are. A highly non-obvious fact.
The proof of the Gale-Shapley theorem is as elegant as the algorithm.
Let me show it to you now. So first of all, why does the algorithm
converge in a quadratic number of iterations? Well, no man proposes to a
woman twice. Therefore, each man makes at most n
proposals. There are only n men so that's the most
n^2 proposals over all. Secondly, when the Gale-Shapley algorthym
terminates it does show with a perfect matching.
Indeed it's a stable matching, but let's just for the moment prove that it's a
perfect matching. To, to see this let's suppose the
contrary. Let's suppose that when it halts, it does not halt with a perfect
match. That means, in particular, some man is
assigned to know woman. How could that have happened? Well it
must have been that the man fell off of his ranked list.
He proposed to every single one of the n women and was rejected by all of them .
So how could this have happened? Well, notice that for a man to be
rejected by a woman, it must be that the woman has some other offer from some
other man that she likes better. That is, rejections happen only by a
woman who is engaged to somebody else. So by virtue of this man being rejected
by all n women, all n women got engaged at some point in the algorithm.
Moreover, if you inspect the algorithm, you'll notice that once a woman is
engaged to somebody, she will remain engaged forever more.
The only thing that changes, is the woman is engaged to men that she likes better
and better as the alogorithm proceeds. So a man rejected by everybody implies
that all women get engaged at some point in the algorithm which means they are all
engaged at the end of the algorithm. But there's an equal number of men and
women. So there's no way all women are engaged
at the end and some man is not engaged. If all women are engaged, all men must be
engaged. As well.
Finally, why is the perfect matching, computed by the Gale-Shapley proposal
algorithm, not just perfect, but more generally, stable? To see why this is
true, let's prove that there's no blocking pair.
That is, let's consider an arbitrary unmatched man u and woman v.
Now either, the man, u, proposed to the woman, v, at some point in the proposal
algorithm, or he didn't. Let's treat those two cases separately.
So let's first suppose that at no point in the algorithm did the man u, propose
to the woman v. So, what's the behavior of a man in the
proposal algorithm? Well a man simply proposes to the women on his list one at
a time in turn as necessary. And the man, the woman to whom a man
winds up matched at the end of the algorithm is the last woman to whom he
proposed. So if the man u never got around to
proposing to the woman v, that just means that he never searched that far down in
his preference list. And he wound up, at the conclusion of the
algorithm, matched with the woman he prefers to the woman v.
And so that's sufficient to say, to claim that uv is not a blocking pair.
Suppose, on the other hand, that you did propose the woman, v, at some point in
the algorithm. Why did they not wind up matched? Well,
it must be because the woman, v, got a preferred offer, an offer from some man
that she prefers To the man you. Now something we mentioned earlier, is
over the course of the algorithm, a women just winds up being engaged to men that
she prefers more and more. So that any point she winds up engaged to
a man she prefers to you, then the end of the algorithm she will And be engaged,
matched with a man that she prefers to u. And again, that implies that uv is not a
blocking pair. Since uv was arbitrary, this is a stable
matching. That completes the proof of the
Gale-Shapley Theorem.