I want to tell you about the stable
marriage problem and what I really 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 no numbers no numbers even
let me let me pose the problem so I'm
gonna play the role of a Yenta 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 villages
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 I get to arrange the marriages
I get to choose I know 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 my
ultimate goal my principal 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 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 that's not good
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 possible 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 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
spouses any other situation is stable
that's the one we're trying to avoid
how big a group are we talking here I'm
going to have no bounds on size
whatsoever so there could be you know
the six billion people that are on the
planet if we want or you know 10 men 10
women in a remote village and they
people can have any preferences
whatsoever I'm I can't control what
people feel in their own hearts so 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 too I
need a way to actually make the
arrangement so that I can tell everybody
who they're going to 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 Gail and Lloyd shapely in the 1962
paper on college admissions and the
stability of marriage that proves that
this can always be done and 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 one through
the end of how many of who 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 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
two
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 rate 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 so he can
keep waiting for a better office he can
keep waiting for a better offer then on
day this is terrible for the women 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 proposal
her next choice and the men again have
an opportunity to trade up if they
receive better proposals there break the
previous engagements and keep going and
then the claim is that is that this
stops at some point and furthermore once
this algorithm stops and the final
engagements are stable in the sense we
discussed previously
let's see an example of how this whole
process work so what I've done here is
I've created for hypothetical women
Charlotte Elizabeth Jane and Lydia and
for hypothetical men kind of 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
- Lydia to Charlotte and so on and so
forth so let's run the algorithm and see
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 ok 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 proposals
to Darcy Darcy is proposed to by
Charlotte and Lydia proposes to Wickham
Whitcomb receives a 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 three
tentative engagements Charlotte - Darcy
Jane - Bingley
Lydia - Wickham and Elizabeth is
unengaged so on the third day she
proposes this time - Darcy Darcy
receives a proposal from Elizabeth who
he prefers - Charlotte so she's rejected
and we have three tentative engagements
again Elizabeth - Darcy Jane - Bingley
Lydia - Wickham now on the third day
Charlotte proposes to her next
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 proposals he has no
better option so he says yes and now the
algorithm terminates because everybody
is engaged yeah
all right so now is the time for the
mathematics I'm going to describe a
number of theorems now he's only going
to reject her proposal if there's some
other woman all right W prime for some
other woman