Stable Marriage Problem (the math bit)

all right so now is the time for the mathematics I'm going to describe a number of theorems some of which will prove together and some of which I'll leave you to prove as exercises so the first theorem we might call it theorem 0/0 is that this algorithm always stops so this is a big problem for a computer you need to make sure that the process always terminates no matter what the Preferences no matter how big the marriage market this this I'm going to leave as an exercise for you to prove but you'll notice that something special happened on the last day of the algorithm in this example and that's that's characteristic of when the algorithm will stop leave that is a little hint but but it seems reasonable there's only finitely many preferences that's this is probably going to stop theorem one is the big one which is that the algorithm finds stable marriages ok and this is something that we can prove so to show that the algorithm arranges stable marriages will show that no girl can do any better that no woman can trade for anyone that's better than her assigned mat so the husband that is assigned by the algorithm is the best that she can do ok well so how do we see this so each man a given woman prefers so a fixed woman prefers rejected her along the way yeah because of the design of the algorithm she starts with her first choice and and is only rejected if that man that she likes best is proposed to by somebody he likes even better so every woman or every every man that she prefers rejected her because he traded up because he's with a better match so even though she might like to be with him we see that any way that we see that there yeah absolutely so Charlotte prefers Bingley but Bingley is with someone he likes better than Charlotte she also prefers Darcy but Darcy's with someone he likes better than Charlotte and that's why even though Collins isn't one of her top choices and in fact she is not one of Collins's top choices neither of them can do any better so I think that's proof so we'll end it QED quod erat demonstrandum so that this is great we have we've just solved the problem remember I said that I've never specified how many men or women are in the villages I've not put any restrictions on the preference lists we've just shown that the stable marriage problem can always be solved that's really really really cool happily we've shown that every woman has done as well as she can do have we shown all the men have done right remember for an instability to arise both the men and women have to prefer it so as long as the women can't do any better you know it doesn't matter so much what the men think it is regardless no woman's gonna know Harmon he's gonna leave her man yeah yeah totally okay okay so so we've solved the problem but as mathematicians we're curious so a solution to one problem leads to new questions and the first question would be are there different ways to solve the problem so so we have found using this algorithm one way to arrange stable marriages for everyone in the village but you can imagine that there might be multiple ways and you can imagine also that well so this is so then you might ask how they compare and I'm going to state a remarkable theorem about this but first I should make a definition let's say I'm one of the women in the dating pool let's say I am Charlotte I'm going to say a best or a possible husband for Charlotte is any person that she is matched to in some stable marriage configuration so we've proven that she that Collins is possible for her but there might be some other men that are that she would be assigned to she would be married to and some one of these other solutions to the stable marriage problem so you saying there could be a stable set of pairings where she could have got Darcy or Bingley Yeah right it's possible a priori so so so here now we can state the second theorem this algorithm so the algorithm due to Gale and Shapley that I just described this algorithm assigns every single woman every woman simultaneously best possible husband so what I mean by this is that in any solution to the stable marriage problem every single woman does no better than the assignment that I've described here then the assignment from this algorithm and maybe I should say the girl proposing algorithm because remember the way it works is the the women propose to the men this is a really really remarkable result that says that the solution to the stable marriage problem found by this algorithm is simultaneously optimal for all the women so you're making an even bolder claim about yourself absolutely it has an even more remarkable property than described previously firstly it solved the stable marriage problem it arranged stable marriages for everyone in the village but even more than that it did it in such a way that every woman simultaneously does the best that she possibly can so so that that's that's crazy okay um we don't commenting on the men no or the recipient of the well so that brings me the theorem number three which is that this algorithm so the algorithm in which the women propose to the men the signs every man his worst possible wife so the women all do the best that they can in any solution to the stable marriage problem and the men all simultaneously do the worst that they can in any solution to the stable marriage problem so it's much better to propose than to be proposed to so it turns out that these two theorems have the same proof you can interpret the argument for this one as proving this theorem as well that actually wasn't noticed for about ten years so the original I mean the original statement of the algorithm had the men proposing this was the 60s after all and they noticed right away that every man gets his best possible wife interestingly it wasn't until about ten years later that they noticed that every woman gets her worst possible husband even though the argument is exactly the same so this might be a commentary on the sexism of the language in which this problem is couched but but anyway the women are proposing today so they're they're going to do the best and let's see how this works so I'm going to prove this using something called proof by contradiction in particular I'm going to assume that this statement is false that there is some woman who is not assigned her best possible husband by the algorithm I just described and then I'm going to find something wrong with that supposition so therefore this theorem must be true and even more precisely the way we describe the algorithm is a series of proposals that happen over time so I'm going to consider the first woman who is rejected by a possible husband I'm going to show that there's a problem with the situation this woman can't exist but let's let's suppose right now that woman w is the first that is rejected by a possible husband so what does this mean that means that there's the man that she's assigned to by the algorithm I'll write em some algorithm as a way to think about the man that she's assigned to by the algorithm we just described but there is some other man that she likes better who rejects her okay so how does this happen well because this woman prefers this man at some point she would have proposed to him now he is only going to reject her proposal if there's some other woman all right W prime for some other woman who he likes better and who also proposes to him so if this man receives two proposals but he likes this woman better then he will reject her so remember this woman is is meant to be the first woman who is rejected by somebody she likes better than the person she ends up with in the algorithm okay but in order for this man to be possible this man that she likes better to be one of her possible husbands that means there's some stable marriage configuration that pairs these two two together that in which these two end up being married but we already know that this man likes this woman even better than this woman so this arrangement this may marriage is only stable if in that stable assignment she is with somebody that she likes even better this is an even better man but that means that she would have previously proposed to him because this is somebody she prefers and he would have previously rejected her in order for her to propose to this guy and that's the contradiction we said this woman was the very first one who's rejected by somebody she likes better but we saw that that meant that there was somebody else who had been rejected even previously and so that's the document it's a little subtle it's not it's not maybe an easy proof but I'd claim if you think about it really slowly it can make sense in fact the so the mathematicians wrote this paper it's a beautiful paper in the 1960s but in the 1950s the Medical Board in the u.s. faced a problem in that the graduating medical students had to be matched to residency programs for further training so these are doctors who've just received their degree but have not yet had experience working in hospitals there was a lot of backroom dealing as the the residents and the hospitals trying to try to find the best the best matches and the problem was the way that this had been done was in stable so a group of doctors got together and came up with what's called now called the National resident matching program where all the medical students the medical graduates submit preference lists of hospitals and the hospitals who have interviewed these medical students submit preference lists for residents and then the computer does exactly this algorithm to assign graduating medical students to residency programs this happens every March in the US and in Canada at least Emily we've seen that this algorithm favors one camp more than the others that favors the proposer the women in our example when it was done with when it is done with hospitals and residents who does a favor right so it originally favored the hospitals but in the mid-1990s people sort of figured this out switched it over so now it favors the residents so there's an important corollary to this which I haven't mentioned this is maybe theorem for is that it's not possible to game this algorithm at all so the the residents do not do any better by lying on their preference list if they really prefer mercy to general to state they should rank them those hospitals in that order there's no advantage to lyon at all and that's again a mathematical theorem that you can prove

Channel: Numberphile2

Views: 261,041

Keywords: Stable Marriage Problem, Mathematics (Field Of Study)

Id: LtTV6rIxhdo

Length: 11min 36sec (696 seconds)

Published: Thu Sep 04 2014