Stable Marriage Problem – Numberphile

Stable Marriage Problem – Numberphile


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 ..

100 Comments

  • Teppo Jarvinen

    May 5, 2017

    I am unable to follow the plethora of different names. I'd be more comfortable with this problem being done with numbers.

    Reply
  • mythology2467

    May 15, 2017

    So in our '6 billion' people planet, that will take 6 billion days? Are time zones a factor? You haven't thought this though. I got places to be, things to do, weddings to have. 😛

    Reply
  • Alex Evans

    May 16, 2017

    But if this is weighted against men and pro women it is game-able. If the men voted tactically amoungst themselves before the real vote they could do better. I guess that's game theory.

    Reply
  • TruncateCar3

    May 20, 2017

    This video triggers the SJW

    Reply
  • MrTeknotronic

    June 5, 2017

    I saw a number!

    Reply
  • RF1204

    June 9, 2017

    The goal to marriage is find one person of your compatibility group and have RESPECT for the relationship. Okcupido algorithm explained in youtube shows that group percentage. The fault of respect , wich to me is criminal, is if one inside the relation do not finish is liberty when starts the other liberty and try to be 50℅ to each. The Respect is also what can balance Professional and Neighbour relations with Incompability groups, because is oposite to one evil think have the 99% and the others 1% liberty in that relation.

    Reply
  • Luke F

    June 12, 2017

    Well if Collins wasn't such a bumbling fool with a geriatrics's fetish more girls would be interested in him.

    Reply
  • Diesel Zero

    June 27, 2017

    MARRY PERCY AND PIERRE

    Reply
  • Sebastian Malton

    June 30, 2017

    What is the music at the beginning? I think it is mozart but cannot recall specifically

    Reply
  • B Mich

    July 10, 2017

    So Collins ended up with the grenade

    Reply
  • Camilo Toro

    July 11, 2017

    Assuming all heterosexual marriages is hate speech in 2017

    Reply
  • Free Ride

    July 11, 2017

    what we need right now is a Strong and stable marrage

    Reply
  • len 114602

    July 21, 2017

    The art could've been better

    Reply
  • TankingShaman

    August 1, 2017

    So, can we, in 2017 actually test this in practice in the form of a reality show? Say, 10 men, 10 women (all heterosexual) and see what happens over a course of all 20 living together for X months.

    Reply
  • sharksdoe

    August 20, 2017

    "how to explan Pride and Prejudice with maths"

    Reply
  • Caitlin Y

    September 4, 2017

    low-key pride and prejudice reference made this whole video for me

    Reply
  • Denoredo

    September 17, 2017

    Doesn't this happen already in real life?

    Reply
  • Eric Lecarde

    September 26, 2017

    I solved this without knowing it was a math problem at all, i'm the next Faraday lol

    Reply
  • Oliver Keely

    October 1, 2017

    Can someone tell me the gender of the person in the video?

    Reply
  • A Corn

    October 7, 2017

    8:10, in the book the roles are exactly the opposite.

    Reply
  • oOLunaFoxOo

    October 9, 2017

    πumberphile?
    So…
    Pumberphile?

    Reply
  • lawofparsimony

    October 18, 2017

    this is mechanism design

    Reply
  • Bryan xx dxenca xx Thomas

    October 23, 2017

    This is NUMBERphile and NO NUMBERS WHATTTTT

    Reply
  • crangor

    November 1, 2017

    How cool would an algorithm be that Computes on top of that changing preferences.

    Reply
  • micger

    November 3, 2017

    Surely this doesn't make people happy because majority of people did not get their first choices

    Reply
  • Gara Teaser

    November 10, 2017

    You are attractive person ^^

    Reply
  • Jam Kon

    November 14, 2017

    Hahahaha “odd names”. More like a Pride and Prejudice character list

    Reply
  • Carlos Rios

    November 15, 2017

    Since when did Numberphile turn unto TedED?

    Reply
  • Sehr Geheim

    November 16, 2017

    The drawings are… horrifying

    Reply
  • Dito

    November 17, 2017

    The reverse should be done for elections. So all votes get counted.

    Reply
  • Zaman Saheb

    November 17, 2017

    bal hoise

    Reply
  • Petr Mazak

    November 19, 2017

    Does this generate the "optimal" solution (best aggregate value of ranked spouses by everyone) or are there more possible outcomes of the algorithm with different outcomes? Collins doesn't seem happy with the result… (yes, I'm from business studies 😀 )

    Reply
  • Sri Harsha

    November 23, 2017

    Adding the titanic music sure made this video romantic

    Reply
  • 42ndCole

    November 27, 2017

    in real life, it's men that deal with rejection more you have to start all over and make a new algorithm

    Reply
  • Victoria M

    November 28, 2017

    Sounds like a chemistry problem, actually, but with far less polygamy.

    Reply
  • TurboCMinusMinus

    December 1, 2017

    "It's not at all obvious that the answer is yes" – it was obvious to me. Why? Because any "unstable" state would tend toward more stability by these mutually desired pairings, until finally you'd have a stable state which was what should have been chosen to begin with.

    Reply
  • The Leftist Who Cried Racist

    December 1, 2017

    Boy I'm actually shocked that they/hiz/them/zie was capable of doing this problem without being offended to death by heterosexual marriages or calling the problem itself "homophobic". Lets put it this way, objectivity isn't usually their strong suit.

    Reply
  • Bel-Shamharoth

    December 14, 2017

    Maybe I'm missing something, but as described, I fail to see how the answer could even conceivably be "no, there are situations where this isn't possible", because you've given it an infinite number of iterations and a base condition at which it stops working. Given those conditions, ANYTHING will terminate at the most stable state, and considering the rigidity of conditions here, of course it will end up being stable every time. That is pretty much the whole basis of sorting algorithms in computer science; just keep shuffling things around until it's stable, and give it clear and simple instructions that make it impossible for it not to come up with a correct solution.

    Reply
  • TheThreatenedSwan

    December 18, 2017

    There's only one things men need to know, no hymen, no diamond

    Reply
  • AnteConfig

    January 1, 2018

    You know that in the real world some of them will end up cheating and when they're caught there will be a divorce and so eventually there will be many single people and a few cheaters still married.

    Reply
  • schuelermine

    January 6, 2018

    Didn't you already cover this?

    Reply
  • Kyle Clare

    January 10, 2018

    Nice pride and prejudice reference

    Reply
  • José E. Ramírez

    January 10, 2018

    The math behind Pride and Prejudice <3

    Reply
  • Lindsay Clay

    January 10, 2018

    Those are far from funny names for men and love the girls names too. Thank you for mixing math and classic literature to make it all the more fun to watch.

    You must be a true fan because everyone was paired correctly.

    Reply
  • Alan Armstrong

    January 15, 2018

    What if two people have the same list?

    Reply
  • Stormorbiter

    January 24, 2018

    This is a reality show in the making

    Reply
  • Microsoft Word Technical Support

    January 25, 2018

    Bingley, Collins, Darey and Wickham, huh?… I think I'm also detecting a preference..

    Reply
  • Lon Johnson

    January 25, 2018

    On the surface, this seems like a pure math game, but I can see that it could have practical applications in chemistry. At the very least, it reminds me of electronegativity, which can be thought of as a way of saying which atoms prefer to be with what other atoms. The big difference is that atoms are neither heterosexual nor monogamous. (Did you see Oxygen? He married two Hydrogens! Scandalous!)

    Reply
  • Manar Zrekat

    February 3, 2018

    That's the question my professor asked at my first day in university, we all looked at him with blank faces, how does that have anything to do with computer science. I spent the whole semester trying to understand it and I did in the end, and now after a year I find a video that explains it very easily!

    Reply
  • Retro Gaming - Clash Of Clans

    February 26, 2018

    is that a NP problem

    Reply
  • Boyd Seabiscuit

    March 3, 2018

    what if they dont propose?

    Reply
  • AstroTibs

    March 21, 2018

    Wouldn't the answer be "yes" because if there exists an instability, you can just assign them that way to begin with? And then if the re-arrangement causes new instabilities, just stabilize those? It can't be cyclical—you can't infinitely come back to the same person and have them be an unstable relationship every time you come back round.

    There can't be an infinite loop: a person can't constantly find a more fitting partner without end, given a finite set of options.

    Reply
  • Ayush Arora

    March 26, 2018

    Awesome explaination

    Reply
  • Mark Milne

    March 31, 2018

    triggered!!!

    Reply
  • Jamal Amir

    April 1, 2018

    There are 7 billion people on the planet

    Reply
  • PartScavenger

    May 13, 2018

    Haha this only ensures that the matheticians only get married.

    Reply
  • Emma Zaia

    June 18, 2018

    This is literally the plot of love island.

    Reply
  • Ural Damasis

    June 23, 2018

    This would have made way more sense with the genders reversed.

    Reply
  • Rajsekhar Kolla

    July 9, 2018

    Just watched both the videos about this problem.
    A quick Google search revealed that Dr Riehl is 68 years old! 68 years!!

    Reply
  • Trent Carroll

    July 20, 2018

    Funny enough, if the men were proposing in this example, the results would've been the same.

    Reply
  • K1naku5ana3R1ka

    August 26, 2018

    Also, as for the “heterosexual marriages only” bit, there’s another problem called the stable roommates problem, which is the same except anyone can be paired with anyone else. It’s known that this problem cannot always be solved; for example, imagine four roommates, A, B, C, and D, and their preferences and as follows: A is BCD, B is CAD, C is ABD, and D can be anything. No matter who is paired with D, they prefer the other two to D, and one of them will reciprocate that feeling; for example, pair AD and BC, and A and C will not be happy.

    Reply
  • K1naku5ana3R1ka

    August 26, 2018

    Incidentally, what if you just paired off people randomly and then let repeatedly let unstable pairs run off and pair the leftover people (ie, if AB and CD are paired, and B and C are unstable, let them run off so that you get BC and AD)? I doubt that would be very efficient for computation (might be more practical for pairing actual people), but is this guaranteed to reach a solution, no matter what order you remix pairs?

    Reply
  • SM64 Guy

    September 12, 2018

    What if somebody doesn’t like anyone and nobody likes him?

    Reply
  • daniel sousa

    September 16, 2018

    These videos are awesome but do they have to write on paper with Sharpie's? Ouch

    Reply
  • Jessica

    September 17, 2018

    If only college applications worked this way

    Reply
  • Literally Hitler

    September 22, 2018

    Tinder should really work that way

    Reply
  • Mashrur Wahid

    October 9, 2018

    In the end of the day I'll be collins in real life

    Reply
  • Joanna Kwan

    October 27, 2018

    Essentially, Jane Austen was the one who came up with the algorithm!

    Reply
  • Sorren Averia

    October 28, 2018

    Will you get the same result if you run the algorithm the other way around where the men proposes to the women?

    Reply
  • Iffat Sarfraz

    October 28, 2018

    Hello Dr. Riehl,

    I attending your talk at the University of Virginia at the Women's Intellectual Network Research Symposium. You are truly an amazing mathematician!

    -Iffat Sarfraz

    Reply
  • Guillem

    November 6, 2018

    I just notice, there could be more than one set of stable arrengments.
    Lets see a simple case: Ana prefers Carlos to David, Beaty prefers David to Carlos, Carlos prefers Beaty to Ana and David prefers Ana to David. So if the men propose first, the arrengements will be Ana-David and Beaty-Carlos. If the women propose first it will be Ana-Carlos and Beaty-David.
    Its easy to see if that structure repeats in a bigger list with more couples it could happen again and with more participants.

    Reply
  • Julien Bongars

    November 25, 2018

    I'd like to report a serious mistake in this proof. You mixed up the men and the women.

    Reply
  • Thinking Vertices

    December 4, 2018

    I want that brown paper.

    Reply
  • Rish Kum

    January 11, 2019

    Thanks

    Reply
  • Joshua Vogel

    January 30, 2019

    Ahhh…If only I would have known this equation earlier in life. I wonder if there's another algorithm for happily single? Perhaps Collins and Charlotte could benefit from this and either wait for their better choices to get bored with theirs or join another group or wait for another to join theirs. Haha now that would be closer to real life. Now off to the bar….

    Reply
  • oh my gosh ponies

    February 6, 2019

    Is this how Tinder swiping works?

    Reply
  • Excellence Ilesanmi

    February 7, 2019

    Characters from Pride and Prejudice 🙂
    Plus "Emma" being a matchmaker.
    Jane Austen would be proud

    Reply
  • Sehr Geheim

    February 13, 2019

    Some cultleader probably saw this video and applied it in his cult

    Reply
  • Rosie Fay

    February 13, 2019

    Who's watching shortly before St Valentine's Day?
    0:59 stabilly

    2:51 Aw, there's computation. But you promised no calculation!

    3:13 Hey, who you calling shapely?

    5:06 Man: "This is terrible for the women." But the women are being proactive here, and the men have to wait to be proposed to. Looks worse for the men here.

    Reply
  • Schumii

    February 14, 2019

    If you've liked the video you should definitely read the original game theory paper by Shapley and Gale, 1962. In my opinion, it was the easiest to understand math paper I've ever read, and it really shows how math doesn't need to be about numbers.

    Reply
  • aron hegedus

    March 1, 2019

    I'm writing my dissertation on this haha (Oxford 4th year Maths and Stats)

    Reply
  • Privat

    March 12, 2019

    Divorce Lawyers hate this simple trick!

    Reply
  • Aiden Potter

    March 15, 2019

    No numbers, but this is numberphile, I feel so betrayed.

    Reply
  • Askformoreinfo whichyouwontget

    March 16, 2019

    Its chemistry, materials have preferences.

    Reply
  • Dan Collins

    April 6, 2019

    As a Collins, I appreciate that I got the dregs! Thank you!

    Reply
  • Strofi Kornego

    April 6, 2019

    In real life women change their preferred choices list everyday.

    Reply
  • Warren Guinn

    April 6, 2019

    I don't quite get how Charlotte and Collins have stable marriage; they both want to be with someone else more. Does it work because Charlotte had already been declined? Or is it just because they don't hate each other the most?

    Reply
  • Ryan Piotr

    April 8, 2019

    Maybe with data-driven artificial intelligence becoming more powerful and prominent and suggesting our partners, this will be practically relevant soon?

    Reply
  • Farcraft2

    April 20, 2019

    Or Bingley bangs all the chicks and the others get nothing.

    Reply
  • Rishikesh

    May 1, 2019

    Canon in D…..

    Reply
  • Mareks Ozols

    May 4, 2019

    All this is based on assumption that rating list is final and constant.we have to add prefference change function for every member. Or at least approximation that top preference if proposed to and accepted will become third and now initialy second will be first …..

    Reply
  • The Gamegineers

    May 9, 2019

    Is this possible with only one group of people?

    Reply
  • KnifeLightning

    May 27, 2019

    Is there an equivalent problem for a fully bisexual population, where everyone ranks everyone else, and any pairing is possible? If so is there an optimal solution/algorithm?

    Reply
  • Arpita Ria

    July 3, 2019

    You are so brilliant 😍😍😍😍…

    Reply
  • Tina White

    July 7, 2019

    Can you think of this as a complete weighted bipartite graph?

    Reply
  • Taco-Tanner

    July 13, 2019

    No numbers? Bah! 1 and 2 which 2 prefers which 1 and vice versa. Easy.

    Reply
  • Riyan Syafi'i

    July 14, 2019

    Jane Austen

    Reply
  • Aritro Banerjee

    August 2, 2019

    Background music is Canon in D by pachelbel you're welcome.

    Reply
  • james real last name

    August 20, 2019

    Impossible with the world population, because nobody would be able to rank everyone before dying.

    Reply
  • hovnous1

    August 27, 2019

    Would the result be the same if the men were proposing?

    Reply

Leave a Reply