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.