Dr Riehl: So I want to tell you about the stable marriage problem. And what I like about it is, it’s completely unlike the kind of mathematics that most people have seen in high school or in college even. There’s no numbers involved, we’re not computing anything. No calculations, no integrals. Brady: No numbers? Dr Riehl: No numbers, no numbers even.
Brady: Aw, I’m going then (both laugh) Let’s, let me pose the problem. So I’m going play the role of a Yente. So let’s say I live in a remote village. And there are a bunch of young men and a bunch of young women. And it’s in the village’s interest that everybody gets married. Everybody pairs off. We’re only talking about heterosexual marriages today. That’s actually really important to the mathematics, but leave that aside for now. And I get to arrange the marriages. I get to choose. I know all the young men and young women very well I know what their preferences are. But it’s really ultimately up to me. And my ultimate goal, my principle goal in arranging these marriages is stability. So I don’t mean stability over time, people might grow apart, their preferences might change. But I mean instead the following scenario. Say I’ve arranged a marriage between this couple here. So this young man and this young woman. And then I’ve arranged another marriage here for another couple. Another man and another woman. But suppose this woman prefers this man to the husband that I’ve assigned her. And this man simultaneously prefers this woman to his wife that I’ve assigned. Brady: That’s not good.
Dr Riehl: That’s not good. That means that these two are going to say “to hell with this arrangement” and run off together. So that’s what we want to avoid. So I’ll say this situation is not stable. And then the question today is “is it always possible to arrange stable marriages?” So I want this instability that I’ve just described to never occur. So it’s quite possible that this woman really dislikes the husband that I’ve assigned her. And so she in particular would prefer this guy, but he’s maybe very happy with his wife. He prefers her to her. So she wants to trade, but he doesn’t want to trade, so this is a stable configuration, even though not everybody is thrilled with the arrangement. Instability is if and only if two people simultaneously prefer each other to their assigned spouses. Any other situation is stable. That’s the one we’re trying to avoid. Brady: how big a group are we talking here?
Dr Riehl: I’m gonna have no bounds on size whatsoever. So there could be the six billion people that are on the planet, if we want. Or, you know, ten men, ten women in a remote village, and people can have any preferences whatsoever, I can’t control what people feel in their own hearts, so it’s a big question. And it’s not at all obvious that the answer is ‘yes’. And furthermore, even if the answer is ‘yes’, there’s a computational question. Is it maybe there is some stable marriage configuration out there in the universe. But I need to be able to find it, so I need a way to actually make the arrangements so that I can tell everybody who they’re gonna be spending the rest of
their lives with. So the answer is ‘yes’ and the proof is constructive. There’s an algorithm due to David Gale and Lloyd Shapley so in the 1962 paper “on college admissions and the stability of marriage” that proves at this can always be done. So I’d like to describe that algorithm to you now. This is an algorithm that you can program a computer to run, but I like to describe it as … via a metaphor where the men and women are playing certain roles. So before we begin each man and each woman rank the members of the opposite sex.
So in other words everybody submits a preference list. You know 1 through the end of how many … who they’d like to be married to. So then on the first day of the algorithm we’ll have each woman proposes to her number one choice. So some of the men will receive multiple proposals, others will receive none whatsoever. So the ones with multiple proposals then make some rejections, so each man rejects all but his top suitor. So at the end of this step we have what we’ll call tentative engagement, so some of the women make proposals that aren’t rejected yet and those those couples are tentatively engaged.
But we’ll see that the algorithm isn’t quite finished just yet. So on day 2 each rejected woman so each woman whose proposal was rejected the day before, proposes to her next best choice. Regardless of whether he’s free or not. So some men will receive new proposals
others won’t receive any and the men now have a chance to trade up. So maybe you had a tentative engagement from the day before but you have a better suitor now so you
can rej… break the previous engagement and make a new match so again each man rejects all but his top suitor. So this is
why we said the engagements are tentative. If at any time a woman that he likes even better proposes to him, he’s free to reject and break the previous engagement and become tentatively engaged to somebody he prefers. Brady: So he can keep waiting for a better offer
Dr Riehl: He can keep waiting for a better offer then on day
Brady: this is terrible for the women Dr Riehl: three, four, well you think that now but wait till the end. So this is day three, four, five, and so on we just repeat this process. So any woman who is rejected the day before proposes to her next choice and the men
again have an opportunity to trade up as they receive better proposals they’ll break the previous engagements and keep going and then the claim is that that this
stops at some point and furthermore once this algorithm
stops and the final engagements are stable in a sense we discussed
previously Let’s see an example how this whole process works. What I’ve done here is I’ve created four hypothetical women
Charlotte, Elizabeth, Jane and Lydia and four hypothetical men, kinda funny names Bingley, Collins, Darcy and Wickham and then for each person I’ve listed preferences so Charlotte prefers Bingley to Darcy to Collins to Wickham similarly for Elizabeth, Jane and Lydia and the men have preferences also Bingley prefers Jane to Elizabeth to
Lydia to Charlotte and so on and so forth. So let’s run the
algorithm and see who ends up married to whom. So remember on the first day each woman proposes to her best choice. So Charlotte proposes to Bingley, Elizabeth to Wickham, Jane to Bingley and Lydia to Bingley. so see Bingley receives three proposals right off the bat from Charlotte, from Jane and from Lydia. and Wickham receives one proposal, from Elizabeth. Bingley right now has a choice. He prefers Jane to Lydia and Charlotte, so he’ll reject these two, that is Lydia and Charlotte are both rejected. and at the end of the first day we have
two tentative engagements Elizabeth to Wickham and Jane to Bingley. On the second day Charlotte and Lydia, which were rejected
the day before make their proposals so Charlotte proposes to Darcy (Darcy is
proposed to by Charlotte) and Lydia proposes to Wickham Wickham receives the proposal from Lydia. Now Wickham was tentatively engaged to Elizabeth but he likes Lydia better so he’s now
going to reject Elizabeth and she’s back on the market. All right so
at the end of the second day we have 3 tentative engagements: Charlotte to
Darcy, Jane to Bingley, Lydia to Wickham, and Elizabeth is unengaged. So on the third day she proposes this time to Darcy. Darcy receives a proposal from Elizabeth who he prefers to Charlotte so she’s rejected, and we have three tentative engagements again Elizabeth to Darcy, Jane to Bingley, and Lydia to Wickham. On the third day Charlotte proposes to
her next choice, which is Collins. You can see that Collins doesn’t actually think very highly of Charlotte he prefers Jane, Elizabeth and Lydia, but he hasn’t received any other proposal he has no better option. So he says ‘yes’. And now the algorithm terminates because everybody is engaged. Brady: That’s fun isn’t it?
Dr Riehl: Yeah! Alright, so now is the time for the mathematics. I’m gonna describe a number of theorems … Now he’s only going to reject her proposal if there’s some other woman alright W prime for some other woman ..