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.

Â