0:00

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.

6:21

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.

10:04

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.