Mating Ritual

Flash and JavaScript are required for this feature.

Download the video from iTunes U or the Internet Archive.

PROFESSOR: OK. So how do we find these stable marriages? Well there's out procedure for doing it, which is kind of elegantly described as a day by day mating ritual that the boys and girls cooperate in. So let's see what happens on the first day. On the morning of the first day, each boy looks at his list of girls and picks the one that he likes the best, at the top of this list, and he goes off and serenades her or proposes to her. So here we have Billy Bob and Brad proposing to Angelina.

That means that on the first day Angelina was at the top of both Brad's list and Billy Bob's list. And they're both going to be proposing and asking if she's willing to marry them. Well in the afternoon, each girl rejects all but her favorite suitor. So in this case, Angelina likes Brad best of all. So she says to everybody else, if you're not Brad take a hike. And that's what happens at that stage. And then in the evening, here we look at rejected boy, Billy Bob. A boy who's rejected crosses off the girl who rejected him. So Billy Bob is going to cross Angelina off his list. And then the whole ritual is going to repeat starting the next morning.

Except now Billy Bob will have a different woman at the top of his list because Angelina's gone forever. This mating ritual continues until nothing changes. And that's going to happen exactly when each girl has at most one suitor. Because if she has more than one suitor, she's going to reject the less favorite ones. So that is the definition of the stopping condition. And on that day, by definition, no girl can have more than one suitor. So she will marry the one suitor she has. And that's the definition of the marriages that result, if and when, the mating ritual stops.

And we claim that they are going to be stable marriages. Now if we think about this process, it's really a state machine. In fact, if you think about it, what the states are is the set of girls on the boys list on any given morning. And then those states evolve to a new list after the crossing out happens on the next morning. So this is kind of a memorable way to tell a story about the transitions of a state machine. And we can bring our state machine concepts to bear. So the first thing we want to prove is that this state machine terminates. That is to say, there exists a wedding day.

Then we want to prove that this state machine is partially correct. And what that means that when the machine stops, everyone is married and that the marriages are stable. So that's our task. Well termination's easy. Because if you look at the state, the state is the boys lists on a given morning. And things evolve because boys get rejected and they cross girls off the list. So what that means, if we take the total number of names remaining on the boys lists on any given morning, that is a strictly decreasing and non-negative integer valued variable.

So by the well-ordering principle, that's strictly decreasing. Well-ordered derived variable will reach a minimum value. And by definition, that's when the algorithm has to stop because it's strictly increasing. So it can't move once it's reached its minimum. So there's a wedding day. All right. So now let's examine correctness of this procedure and figure out what's supposed to happen on the wedding day. We want to show that everybody's married and that the marriages are stable. And in order to do that, we're going to look at some more derived variables and an invariant that explains why the mating ritual works.

So the first remark is that the girls improve day by day, or at least they don't get any worse. Namely, a girl's favorite tomorrow will be at least as desirable to her as her favorite today. That's for any given day. If you look at a girl's favorite on this day, and if there is a tomorrow, then her favorite tomorrow is going to be at least as good as the one she has. And why is that? Well because today's favorite will keep serenading her until he gets rejected. And he only gets rejected when the girl that he's serenading gets yet a better suitor.

And so the girls are always going to improve. We could reformulate this in state machine language by saying that the rank of a girl's favorite, where she rates the boy that's serenading her on her own list of preferences, is a weekly increasing variable. It never gets any worse from one day to the next. By the same reasoning or similar reasoning, a boy's favorite tomorrow is going to be no better than today's. It might be worse. And so it's no more-- the woman that he's going to say, tomorrow is no more desirable to him than today's, is basically because he works straight down his list. If he hasn't been rejected, he'll keep serenading the same woman tomorrow. If he has been rejected, then he's going to be working on somebody lower on his list that's less desirable.

So again, the rank of a girl on a boy, that a boy serenades, is a weekly decreasing derived variable of this process. And these observations lead us to an invariant that holds for the mating ritual. And the invariant is that if you look at any girl G, and if there's a boy B and G is not on B's list, that is G must've been crossed off by B at some point, then the invariant is that the girl G has a favorite that is better than B. And the reason is that again, when G rejected B, she had a better suitor than B. And her suitors keep getting better by the weekly increasing property of her suitors. And therefore, she's going to have a suitor that she likes better than B, whose list she's not on.

This holds for all G's and B's. And that is an invariant from one day to the next. So let's look at what happens on the wedding day and use the invariant to prove that everybody's married and that stability holds. So the first remark is that each girl has at most one suitor, and we've observed that's by definition of a wedding day. And now what we want to prove is that each boy gets married. Well what's going on with a boy, a boy is either married because he's serenading the top woman on his list, or maybe all the women on his list have been crossed off, then he's not serenading anybody. So that's the only way he could be not married.

Now the reason that this is the case is that there's no bigamy here. So boys serenade only one girl at a time. So if a boy is married, there's only one possible woman that he can be married to. And a woman's married to one possible boy. So let's now put these facts together and argue that everybody is married on the wedding day. And the proof is by contradiction. Suppose there's some boy B that's not married. Well that happens exactly when his list is empty. Otherwise, he'd be serenading somebody and be married to her. But if his list is empty by the invariant, every girl has a suitor that she likes better than B, which means she's going to be married to somebody that she likes better than B.

Every girl's married. But there are the same number of boys and girls. So in fact, given that there's no bigamy, all the boys have to be married too. And that settles that one. So the next crucial property that we're interested in is stability. That in fact this set of marriages, which must come into being on the wedding day, are all stable. And the argument for stability has two cases, both of them trivial that follow immediately from the invariant. First of all, let's look at an arbitrary boy, Bob. I claim that he won't be in a rogue couple with case one, any girl G that's on his final list. Because if a girl is on his final list, then he's already married to the best of them.

He marries the girl at the top of his list. So he's not going to be tempted to switch-- to be part of a rogue couple with some girl that's still on his list. Case two is, he's not going to be in a rogue couple with a girl that's not on his list. Because, by the invariant, she's married to somebody she likes better than him. So there's no available girl either way for Bob to be in a rogue couple with. Bob, of course, is an arbitrary boy. And therefore, no boy is in a rogue couple. And indeed, there are no rogue couples.

Free Downloads

Video


Caption

  • English-US (SRT)