PROFESSOR: So stability has some value, but it doesn't mean that everybody's happy. In fact, it just means that nobody can find anybody else who's equally unhappy that they would want to run off with. So let's examine the question of how well people do using the mating ritual, or in other possible ways of finding stable marriages.
So basically, we want to begin with the question of who does better, the boys or the girls? Maybe it's a mixture. Maybe the boys do better, the girls do better, or maybe some boys do better than others, and some girls do better than others. One thing to notice is we know that the girl's suitors are getting better day by day, and that sounds like the mating ritual might be slanted towards them.
Likewise the boy's sweethearts, the ones that they're serenading, are getting worse day by day, and that sounds like it might be an argument for the girls to do better, but that's not true. And the reason it's not is that, if you think about it, the boys are starting off with their first choice. They begin by serenading the girl at the top of their list, and it's true that day by day they keep going down, or staying the same or going down, but they're only sinking to, in fact, the best possible woman that they could be married to. Let's examine that.
So I need a definition, which is that we'll say that a woman, Nicole, is called optimal for Keith when she is the highest ranked girl he can stably marry. So let's think about that for a minute. So Keith has his preference for different girls that he likes, to different degrees, and there may be some that he likes.
Like Keith thinks that Angelina is terrific, but there's just no way that she's going to wind up with him, because she just ranks him very lowly, so there's no stable set of marriages in which Keith can wind up with this very desirable woman, Angelina. But if you look at all of the sets of marriages that are stable, that Keith can be involved in, among them Nicole is the woman that he most likes, so that's what we mean by Nicole is optimal for Keith. She's optimal among the feasible women that he could stably be married to.
The claim that we're making is that the mating ritual yields a set of stable marriages, which is simultaneously optimal for Keith and all the other boys at once. Now, that's a kind of unusual thing. Usually when you're optimizing, you figure you're optimized for one boy, and it sacrifices the optimality for the other boys, but that's not what happens in the mating ritual. All of the boys get their absolutely optimal spouse in the mating ritual, and dually it turns out that all of the girls get the worst possible spouse that they can get, a pessimal spouse, among all possible stable marriages.
Well, with that claim understood, let's go about proving it, and we're going to prove that the mating ritual leads to boy-optimal marriages by contradiction. So let's suppose that Nicole is optimal for Keith among all the women that Keith could possibly be married to in a stable way. Nicole is the best. Suppose that Keith does not wind up marrying Nicole in the mating ritual. So he doesn't marry Nicole in the mating ritual. That means that since the Nicole is optimal for Keith, he must be married to somebody that's less desirable to him than Nicole, so he must have crossed Nicole off on some day. Let's call that his bad day. So on his bad day, Keith is rejected by his optimal spouse. OK
If this ever happens, there's going to be some boy who has the earliest bad day-- we may as well assume that it's Keith. So let's assume that Keith was the earliest among the boys to have a bad day, that is, a day on which he crosses off his optimal spouse, because he was rejected by her. Well, on this bad day when Keith crosses off Nicole, it's because Nicole rejected him, which meant that Nicole had a suitor that she liked better than Keith. Let's call that suitor Tom.
So what we know is that Nicole prefers this guy Tom to Keith on the day that she rejected Keith, and he crossed her off, and we also know since this is the earliest bad day that anybody has, Tom has not yet crossed off his optimal girl. So what that means is that since he's serenading Nicole, and she's going to wind up rejecting Keith in favor of Tom, it must be the case that Nicole is at least as desirable to Tom as his optimal spouse, because he hasn't gotten to his optimal spouse yet. He's working his way down the list, and he hasn't had a bad day yet.
So let's put these two pieces together. Nicole is at least as desirable to Tom as Tom's optimal spouse, and Nicole prefers Tom to Keith, but what that tells us is that if I had a set of stable marriages, with Nicole married to Keith, then in the stable set of marriages, of course, Tom is going to be married to somebody that's, at best, optimal for him, so he's married to somebody that he likes less than Nicole.
And Nicole is married to Keith, and she likes Tom better than who she's married to. What that tells us is that Nicole and Tom are a rogue couple in any stable set of marriages where Nicole was married to Keith, but that contradicts the fact that Nicole is supposed to be optimal for Keith. There's supposed to be a stable set of marriages where Nicole is married to Keith. So a similar argument-- it's actually slightly easier-- is that the mating ritual yields a set of stable marriages in which all of the girls get the worst possible spouse that they can have in any set of stable marriages.
So this leads to a whole bunch of questions, and it turns out that there's a very rich theory of stable marriages, as I mentioned. First question to ask is, well, are there other possible stable marriages? Well, one thing that you can obviously do is you could switch the roles of the boys and the girls. So if you switch the roles of the boys and the girls, you'll get a set of stable marriages that are optimal for the girls and pessimal for the boys. Maybe that's fair or you rather do that.
So that's at least a possibility of using the mating ritual to get two different stable sets of marriages, unless the two happen to be the same. And the question arises, are there others that could exist that the mating ritual doesn't find, either by choosing the boys to act as boys or the boys to act as girls, and the answer is that, in general, there can be many. As a matter of fact, if there are N boys and girls, it's possible that there could be an exponential number of stable marriages in N, and that leads to the question of, well, which is one that might be a better one to choose compared to the one that completely favors the boys or completely favors girls.
Another interesting question that comes up that's an issue that comes up with general protocols of negotiation and optimization among multiple parties is, does it serve anybody to lie? That is, instead of following the protocol and always going to the-- and the boys always serenading the girls that they like best, and the girls always rejecting anybody that's less desirable than their favorite suitor, suppose they violate the convention and lie. Can they do better?
Well, it turns out that, of course, the boys in the mating ritual aren't doing optimal, so they don't gain anything by trying to lie, but the girls it turns out-- it's almost the case-- that girls can do better by lying. If they conspire together to lie, they can actually force the mating ritual to wind up turning into a stable set of marriages that's girl optimal.
So that raises another issue about, are there protocols which are resistant to lying? We're not going to go into these questions. We mainly wanted to understand the stable marriage problem and its applications and how to find them. Again, if you want to learn more about this, you can look at the book by Gusfield and Irving that I mentioned in a previous video.