Stable Marriage Problem (the math bit)

[@RhapsodyAfternoon]

She is so cool and clear in her explanations. I'd love for you to have her on more!

[@martixy2]

So... the conclusion is: Whoever takes the initiative gets the best match :)

[@ugoleftillgorite]

Charlotte and Collins should have just gone their own ways. Sounds like it would be a miserable household! And think of the poor children!

[@LuisAlonzoRivero]

Or cheat... just sayin'

[@RealCadde]

There's nothing saying Charlotte hates Collins or that Collins hates Charlotte, only that they would pick another had they been given the choice. That is, even if you are at the bottom of someones list doesn't mean you won't be appreciated. That said, i am very much against making lists of my preferred mates. It's first come first serve and from that point on my mate is going to have to do something really bad for me to leave her.

[@antivanti]

Remember at the beginning when when the assumption that it was important that everyone was married was stated? It is important to realize how far the analogy goes and when it deviates from the abstract problem we are actually discussing =)

[@lionskull1]

but if there were no other single people, then they would end up alone. It is either each other or no one.

[@ugoleftillgorite]

Lionskull If my choices were either the least desirable person in my community or being alone for the rest of my life, bachelorhood would start to sound pretty good. If it was just a beauty contest, eh, whatever, that fades with time, but if she was a truly deplorable person, who would want to come home to that every night? And yes, Anders Öhlund, I get that this is just a math problem with specified parameters, just having a little bit of fun :)

[@JamesSkemp]

She did an excellent job explaining this, IMO. Hope to see more of her in future videos.

[@cbandle5050]

Wow, that is remarkable. Also, now I'll have something interesting to tell my med school friends when they ask me what abstract math is good for.

[@bunbury4620]

What an eloquent professor. I find it hard to put in words when explaining such complicated situations, with all the men and women, all the dynamics, all the who comes onto whom...

[@johnkesich8696]

The 8 person example below results in different sets of stable marriages depending on which sex does the proposing. In both cases each proposer gets their first choice while the person proposed to ends up with their fourth. In addition, it shows that there are solutions - possibly better - that the algorithm doesn't find. (For brevity, I've used numbers rather than names.) 1: 6, 7, 8, 9 2: 7, 6, 9, 8 3: 8, 9, 6, 7 4: 9, 8, 7, 6 6: 4, 2, 3, 1 7: 3, 1, 4, 2 8: 2, 4, 1, 3 9: 1, 3, 2, 4 The solutions are either 16, 27, 38, 49 or 46, 37, 28, 19 depending on who proposes. However, suppose we are not happy with either of these solutions and decide to see what happens when we consider people's second choices. We get 17, 26, 39, 48 regardless of who proposes. The marriages are stable since no man and woman are more attracted to each other than to their respective spouses. However, all 8 people have ended up with their second choice. Is that better than the solutions found by the algorithm?

[@davtor33]

I'm taking a topology course from her this year! Cool.

[@Brutal_Husky]

Dr. Riehl is so good at explanation!!! Thank you!!! This has so much application potentials.

[@capitalist88]

Again, Brady is so excellent at this. The final question about whether the residents or the hospitals were the "proposers" was exactly what I was wondering at that point. Great vid, and Dr. Riehl explained the concept quite well. Don't think we've seen her before?

[@kokopelli314]

This is one of my favorite Numberphiles. So some questions come to mind. What about alternating proposals at every turn? would the result be sub-optimal? How about three or more classes instead of just two?

[@MegaKaitouKID1412]

I tried switching the proposing-and-proposed-to roles of the example in the video and I got the exact same configuration... so at least in that example the men and women both seem to have got their best possible match. I'd love to see an example that has different results if switched...

[@jonathanmoore6702]

I’m not a mathematician so I could be wrong but I think with four couples there will be only one stable solution, so changing what side asks makes no difference on the result; however if you try with five couples you should easily find an example. The question is is there a proof for only one stable solution for four couples?

[@jonathanmoore6702]

I think I may be wrong, try this setup: 1 ABCD 2 BACD 3 CABD 4 DABC A 2341 B 4312 C 4213 D 1234 I made it so if the “numbers” ask they all get their preferred choice, but that will be the least preferred choice for the “letters”.

[@MegaKaitouKID1412]

Jonathan Moore Okay, that works. Makes sense. Different solutions both ways when I checked. :)

[@alexthi]

Easy one. Just take Woman A likes best Man B, then MC, MD, MA ; WB likes MC,MD,MA,MB ; WC MD,MA,MB,MC ; and WD MA,MB,MC,MD. So each will propose to the next letter of the alphabet. But they are each the worst in the lists of the ones they propose to : Man A likes WA best, then WB, WC, WD ; MB likes WB,WC,WD,WA and so on. Each man gets proposed to by only the woman he likes the least. However, if the men propose, they each get the woman with the same letter, in whose list they are the last one each.

[@matthiasvancampen3770]

we can ask ourselves how small the smallest population is where there are multiple possible stable marriages...

[@markncl100]

I love this. As a total novice, she explains it in a non esoteric way I can understand. Thanks.

[@DizzyBagel]

This would be a perfect algorithm for allotting classes in schools. The men are the classes, classes' preference list is organized by kids grades, kids are the women, and kids submit their preference lists (they already do that in most schools anyway)

[@lizzy6212]

I'm about to make my preference list for residency programs and I love this video! The math reassures me in my ranking

[@KiloOscarZulu]

This was a great explanation. The closing comment on the real life application was the best bit - that should have been included in the main video! A lot of people say that all of these maths puzzles are useless and waste of time, so by including a real life application, it makes it a far more interesting video to watch.

[@codebeard]

Is there an algorithm which maximises the number of people (both men and women) who are paired with their most preferred possible (stable) partner, rather than just optimising for women (or men)?

[@SCX-scan]

The problem is that even though the result of this process favours women over men (or men over women - if they propose), it is still a stable arrangement and that means you can't improve the situation of any man without making at least one lady worse off.

[@codebeard]

But perhaps there's a way of making two men better off at the expense of making one woman worse off? (Or vice versa if the men are proposing.) That would seem more ideal in my mind because more people would end up with better matches.

[@Swabby88]

Could we see another video on why it's not possible to game this system? She mentions it's provable in the end, I'd like to see exactly how

[@ProfJonatan]

It's no advantage to lie in the proposing side, but the proposed side may lie and benefit. One example: women w1, w2, w3, men m1, m2, m3. w1 prefers 2,1,3; w2 prefers 3,2,1; w3 prefers 2,3,1; m1 prefers 1,3,2; m2 prefers 2,3,1; m3 prefers 3,1,2. With no lying you get m1-w1, m2-w3, m3-w2. If m2 lies and submits a preference 2,1,3 (instead of 2,3,1), the algorithm will generate m1-w1, m2-w2 and m3-w3, which is better for both m2 and m3.

[@robo3007]

Because the students now get the best possible result by giving honest answers, it stands to reason that they can't make themselves do any better by telling lies.

[@MadaxeMunkeee]

This might be confusing or altogether uninteresting, but I felt like trying to figure it out so I wrote a proof that I think will work lol. Proof: Only men have the incentive to lie about their preferences because as was previously established, the women all get their best possible husband. So suppose there is some man M that chooses to lie about his preferences, and we have to show that he can only do worse than the algorithm does for him. So if he lied about his preferences, that means there is some woman W1 that he prefers to another (W2 say) who he interchanged in his preference list. So he told the algorithm he likes W2 more than W1, even though he doesn't. If neither of these women propose to him at any point, then his lie has had no impact on the outcome of the marriage game so he certainly has done no better. If on the other hand W1 proposes first then he will accept her proposal (tentatively) unless W2 proposes to him, in which case he will reject his previous proposal and be tentatively engaged to W2. But he really prefers W1 and just lied when he said that he liked W2 more, so he is now worse off for having rejected W1. If instead, W2 proposes first then he will accept the tentative proposal even if W1 proposes (in which case he would really rather swap, but too bad) and if W1 doesn't propose then he didn't have a chance with her anyway and so the fact that he lied wouldn't have changed the outcome of the game. So lying either has no impact on the game, or makes you worse off than telling the truth.

[@ProfJonatan]

MadaxeMunkeee check my example above, it is a counter-example to your proof.

[@MadaxeMunkeee]

Jonatan Schroeder Oh, you're right lol. That was interesting. Maybe then the argument that lying doesn't improve your circumstance relies on not knowing what the other people's preferences are? I'm less sure now.

[@Euler13]

Thank you very much, Brady, for continuing to provide these excellent videos: inspirational expositors sharing beautiful ideas. Numberphile and Numberphile 2 are by far my favourite KZbin channels.

[@AlexChambersXYZ]

Dr Emily Riehl did a wonderful job explaining something that was once a partially understood algorithm. Thank you!

[@QuibblesTheMooKitten]

This is probably one of my favorite recent Brady videos. Yay for logic problems!

[@Cyberial]

I really like her. More videos with her please! Good job Brady, keep it up!

[@nick.raptis]

Brady, I feel that the part of how this algorithm is actually used in the real world should have been in the first video as a reveal. Judging from the comments, to many thought that this was about actual marriages.

[@allanrempel437]

She mentions that it's impossible for the residents/proposers to game the system (presumably because they'll always get the best possible pairing from their list, so why make it anything other than your preference list). But what's not addressed is whether the hospitals/propose-es can do better by lying. Indeed I think they can since, of all possible stable pairings, they are getting the worst one, so giving any other preference list can't do worse, won't do the same, therefore it must do better. Giving a random preference list would be better than giving your real preferences! The question the becomes, what is the ideal preference list they should present, and how does that compare to their actual preference list? How many propose-es can lie before this all falls apart in a miserable tragedy of the commons?

[@TechyBen]

"There is no advantage to lying at all... and that we can prove". What an amazing quote. :D

[@shnnichols]

+Numberphile2 +Numberphile At the end she says that it is impossible to get better choice for a hospital because the algorithm favors the graduate so they'll always get their favorite. However, since the the Hospital always gets their worse possible match isn't that a different question. I.E. Shouldn't a hospital submit their preference list in reverse order therefore their "Worst" possible match would actually be their best possible match?

[@Pillowcase]

This is such a cool one - definitely one of my favourite numberphiles.

[@Eylrid]

This could be applied to employment.

[@zxb995511]

Collins and Charllote are miserable...

[@saber1epee0]

Absolutely brilliant. And 100% approval for the Pride & Prejudice situation. Hmm... Now I'm compelled to figure out who ends up together if the same one was worked out in the Men's favor...

[@saber1epee0]

Hmm, I'm getting the same Couples as when the Women propose. By theorems 3 and 4, does that mean it's the only stable system possible (since everyone apparently does both as well and as poorly as possible?

[@ABitOfTheUniverse]

Could every relationship between things work in this algorithm? Do the objects/subjects need agency? Could this work for seeds to farms? Metal to factories? Electricity to consumers? etc. You mentioned people to people and people to hospitals, are people even needed?

[@Smonsequenses]

It only works for situations where stability is a factor. Electricity to consumers for example is something where you wouldn't want to use an algoritm like this, as one supplier can have multiple consumers. So it is unneccesary to pair a consumer with a supplier that is worse than whatever they prefer. This is why competition between companies is a good thing, they have to provide the best they can to keep the consumer and create a stable relation basically by making themselves prefered. As mentioned in the first video, this algorithm only works if the people never change. That's why it does work in situations where you have a degree (which is a static thing) and a hospital wants you (hospitals by definition require docters). So the preference needs to be static, that's why it doesn't work with people to people in real life either.

[@ABitOfTheUniverse]

Smonsequenses If electricity was distributed via computers, programs and algorithms, there wouldn't need to be companies if it was as efficient as it could be, no? Computers don't have greed.

[@EibaProductions]

No, people aren't necessary. For example, if you're a farmer: You have a list of fields, who have a "preference" for their seed. (Meaning some sort of seed flourishes best due to biological capacities, resources, nutrients etc.) And then the seeds have favourite grounds, so you also put up two lists with different preferrences and you can run the algorythm.

[@ricardoamendoeira3800]

I was thinking the same thing. Maybe if you can figure out what the object would "prefer", for example if you know enough about the seeds, how much rain/water they need, how much space they would take up, what plants shouldn't live nearby, etc... you can make their list of preferences yourself and let the farm owners decide what they want to grow (or use the same process as for the seeds).

[@SangoProductions213]

no, not every relationship, because this disregards many circumstances and options, but it does what it does.

[@TheSqueak788]

As a new medical resident who just went through Match, I knew immediately that this problem represented the Match algorithm....at least it now favors us as individuals.

[@sneak2attack]

what if x ( man) top choice is y and y top choice is x. They will end up choosing each other, doesn't that contradicts with Theorem 3?

[@ElevatingMoment]

You can extend this problem slightly to allow for the possibility of single people (e.g. some women may prefer to be matched with nobody than to be matched with certain men, and vice versa). Then, it turns out that the set of unmatched people is the same in every stable matching. I've seen this referred to as "The Singles Theorem".

[@chamcham123]

Unstable marriage pairs just need to "party" together and they'll be happier.

[@sloandaddyslim]

love this problem. Thanks to both of you for sharing :)

[@otocinclus]

she did not just "I'll leave you to prove as exercises" us

[@nickamador277]

it works the same if you switch the roles

[@recklessroges]

Thank you Dr Riehl.

[@SylvEdu]

Game theory has a way of representing this problem mathematically. You would, however, have to use game theory notation.

[@anindyab]

Where can I read about it?

[@SylvEdu]

I haven't seen this particular problem illustrated as a Game Theory game, but I know what I know of it from college. I suppose you can find some online videos explaining it. I think I saw a good Game Theory course on AcademicEarth.com

[@anindyab]

Thank you!

[@paddywilliams95]

This is actually the exact system used for college applications in Ireland, I never knew that it was based on anything mathematical.

[@hitchikerspie]

Hey Brady nice to see a new video! :)

[@SocksWithSandals]

So Beyoncé's advice was correct: "If you liked it then you should have put a ring on it".

[@sarayusarayu832]

This was amazing! Thank you!

[@wernerruch6218]

You presented this excellently...thanks!

[@Samados99]

This was fascinating. Thanks for the video!

[@kered13]

Another theorem that was hinted at in the first video but never stated explicitly here is that the theorem does not work for gay (or bisexual) matching, or in general, any matching system where people must be matched from a single pool (such as matching partners for a project or game).

[@KuniMuto]

For a method that doesn't have bias to neither men nor women, I suggest the following: Rank each person, regardless of gender, in the order of most desired to least desired. This is done by tallying up the position a person is placed on each list. From there you can either start the proposal process from the person who is most desired or the person who is least desired. If a person who already proposed gets replaced, this person proposes again. This method might not necessarily lead to the overall happiest marriages but I believe it will create a stable state that is not bias towards either side.

[@WhovianMinecrafter]

she talks with the cadence of my rabbi. It's not an insult or complement, just a little eerie how close it is.

[@Socrates...]

Its just like in chess with white having first moves, all things being equal - white has a slight edge

[@Kram1032]

This is interesting. I never before considered voting algorithms where the people you vote on vote back on you like this. Are there compromising algorithms that, overally, given some reasonable metric (I do not know what that metric would be), would actually do better? Like, instead of assigning extremes going with best and worst possible match-ups respectively, it'd go with more of a compromise which, nevertheless, if you, like, sum over mutual satisfaction (how ever that might be definied) of all involved parties, it would actually do better than this?

[@MadaxeMunkeee]

You know, this is just my opinion (as a mathematician, but still an opinion) but I would suspect not. That's kinda why this algorithm is so remarkable, because generally speaking it is notoriously difficult to come up with a way to decide how to allocate resources among groups of people, keeping individual preferences in mind. It's not always possible to make everyone happy, even in maths :( I reckon if everyone is paired up and they're happy to stay where they are then that is a pretty big victory.

[@Kram1032]

MadaxeMunkeee oh I know: Voting-systems in general seem to have this problem of imperfect satisfaction in principle, with various voting-systems having equivalent mutually exclusive axioms if you want to avoid dictatorship, etc. In the end you can only decide which things are least important to you and thus not /really/ necessary for your favourite voting scheme to have. (That being said, unrelatedly, we can most definitely do better than First Past The Post Voting...) Anyway, yeah, if math dictates that this is the best we can do with preference orderings, it's of little use to seek for something better, at least when involving such orderings.

[@edskev7696]

How about taking the ranking that each party ends up with, squaring it, and adding them all up? That would give a measure of 'dissatisfaction' to minimise

[@Kram1032]

***** the good old euclidean metric. Always a good first choice. It'd be worth a try, certainly. I think what you are suggesting would be roughly equivalent to a Borda-count voting-systems (rather than machup systems) Btw, since all those numbers are positive, you do not need a square. Just sum them up directly and minimize that.

[@edskev7696]

Sure, but if you just sum them then you are saying that its fine to move someone from 9th to 10th choice if someone else gets moved from 2nd to first choice, which I don't think is right. The square metric would ensure none gets too far down there list just to benefit others.

[@googolplexbyte]

This leads on to a bunch of questions: Firstly why preference list rather than a scored list? Reducing the amount information you have to model with reduces the chance of finding the best answer. Also it ignores the possibility of equal preference, and if you don't deal with equal preference it completely destroys the whole stability thing. Does the algorithm provide optimal happiness? Something like a condorcet criterion, though it being ranked preference rather than a scored list makes it ridiculously uneasy to determine the optimal happiness. Can the optimally happy outcome be stable and vice versa? Are the two stable solutions created by the algorithm the only stable solutions?

[@bonesmalin]

Emily seems like a really cool person! This was a very interesting video :)

[@mmatt314]

How comfy do those lecture hall chairs look?! Never had them in my day. Would have had a much more comfortable sleep in one of those!

[@brotalnia]

Interesting video. Also Emily is beautiful.

[@sophiar.2310]

I don't quite understand Theorem 3. How's the argument the same as Theorem 2?

[@RENCIOL]

What about the cases where there at an odd number of people?

[@user-ke3wp7cn1i]

u know this would be a fun classroom activity.

This was GREAT. Next, please deal with the Stable rooommates problem. And Condorcet voting. And: has anyone connected these two problems in any way?

[@Jerome...]

We should do it IRL with everyone in my city. -Bachelor

[@maitland1007]

This was a great video. thanks. Such a useful concept and algorithm. It does leave me thinking about the standard cultural 'proposal system' in the world - men proposing to women- and the fact that this makes the women get their worst possible match.

[@patrickwienhoft7987]

I have a problem with the prrof of theorem 2: It only proofs, that the women who gets rejected first can't find a better man. Can't it be that the first woman W1 got rejected first and proposes to another man who then decides to take W1 and let fall his earlier assigned Woman W2. W2 now has not got her favorised man, so there might be a stable solution where W2 finds a better man as the proof doesn't apply to her as she was the second one to be rejected. Also: Is there a thing in between? So that not ALL men get the worst women for them and not ALL women get the best man for them (or vice versa) but some get the best, some get the worst, some maybe something in between (like there are 3 stable solutions [can there even be 3?] and woman x gets a different man in each solution, then one is the best for her, one the worst, and the third is what i mean by "in beteen").

[@MorRobots]

Emily, is this only possible with a single value assigned to the possible match list? IE if the preference list had more than one quality tracked by ranking dose this stable marriage problem fall apart?

[@toast_recon]

I don't think it matters *why* someone prefers someone to someone else. Just sorting partners by, say, brains and beauty, does not tell you which you would prefer. You'd have to quantify the brains and beauty values and form a combined score that you can sort. The algorithm only cares what the people want. They have to decide that for themselves.

[@vlogerhood]

I don't know the mathematics answer to this, but I do know that the residency match program allows for pair matching, where two people submit lists with the caveat that they want the top matches which place both people within geographic proximity. So I suspect there is a solution with two variables, and that is what is used there.

[@allanrempel437]

Even if multiple qualities are being tracking, once you assign a weighting to which are the most important qualities for you, it can be reduced down into a ranked list. That is, for each individual i, x(i) = weight*quality summed over each quality. Then sort by x.

[@jeffirwin7862]

I think the question needs to be more specific. For example, if two partners would like to swap based on Quality A, but are happy in their current arrangements based on Quality B, would they switch? If everyone agrees on a way to average Qualities A and B, then the list of qualities could be replaced by their norm or average. However, if each individual assigns different weights to each quality, then I'm not sure if the theorem holds.

[@MadaxeMunkeee]

I would say yes, that's true. So at the outset if there are multiple criteria women are using to establish their preferred choice among the male candidates, you would hope that they can average everything out and present their preferences as an ordinary list from most preferred to least.

[@Pe0ads]

"As long as the women can't do any better, it doesn't matter what the men think" ahaha

[@jbrowsingj]

Really interesting video! It got me thinking about how applicable this problem is to real life courtship (in modern times or historically), and I definitely didn't see the resident matching application coming. Totally fascinating. I really like this presenter, will she be appearing in other videos? I'd like to see more formal proof work written down on the paper, too. (I mean in proper notation, whatever that is)

[@Noovil25]

Is there any way to make the odds the same for both the proposer and the proposed?

[@josevillegas5243]

Li Voon Loke I wonder what would happen if in general, the free women and free men took turns in proposing? I wonder if it would actually produce a stable matching.

[@TheSentientCloud]

"leave that up to you to prove." *must... resist... being... nerd-sniped...* *grabs out a sheet of paper and starts scribbling some set theory stuff down* Crap. Yet I can't concentrate on what my actual homework is. Granted, it's not math, so I have much less interest in doing that other homework. xD

[@YogiliciousP]

Is the same algorithm used in sending military recruits to their selected preferences?

[@Dexerinos]

My brain just had a unhandled exception :DD

[@Sorenzo]

I think I recognize some of the names from "Pride and Prejudice... And Zombies". Wasn't a very good book.

[@siprus]

this channel should be called mathphile :P

[@Markus9705]

Is there any algorithm that puzzles together the best possible matches for everyone?

[@Missfoxmdtu]

This is very interesting. Thanks for uploading. :)

[@TrappedInAlaska]

This could have been on computerphile, no? Still enjoyed it.

[@oOCaeZaROo]

Am I correct in guessing solutions exist to certain pools that are different than the two found by the GS algorithm (male suitors and female suitors). If that is the case, do methods exist to probe all possible stable solutions and can additional conditions be added to rank between all possible sets in order to minimize the proposer bias?

[@MadcowDeity]

How many stability states are there? Does this algorithm guarantee the most optimized stability state if there is more than one?

[@pennicuik]

Could there be someway of adding a weighting to the system so as to even out the bias? i.e. if A1 wish to change from D2 to B2 calculate difference between preference scores as determined by the stabilization chain (A1 & B2 paired compared to next best A1 & D2 pairing 4 (A1 & D2) - 2 (A1 & B2)= 2 compared againest D2's preference scores 4 (D2 & D1) - 1 (D2 & A1) = 3). Compare the scores and favour the highest score which in this case is would be D2's preference as this would negatively impact D2 (with a score of 3) more the A1 (with a score of 2). Or would as this algorithm would occasionally create unstable relationships (as it has in this case) would this be an ineffective way of evening out bias?

[@PascalD87]

does this work with only one group? I mean, like a class full of children that need to make team-work. so that there are only stable teams?

[@jakx2ob]

en.wikipedia.org/wiki/Stable_roommates_problem not always

[@PascalD87]

Thanks!

[@unnamed_account663]

Kinda funny because you spoke about that maybe without realizing it in a sixty symbol video I think it was... the one about how to get into a university.

[@TheAdriyaman]

0:29 "Something special"?This reminds me of the base case in recursion.Does this algorithm use recursion and this is the base case?

[@R15YZF]

Very nice video. I really liked the example and wish the men proposing woman version had been shown too and the difference in the results then discussed.

[@FranciscoSilva84]

for me this problem only shows that not everyone can win

[@ronaldwangdra9675]

I think it's not insignificant to mention that the ranking list has some assumptions: completeness and transitivity.

[@BenjaminAlexander]

Each individual list appears to be a simple ranking with no ties. I *think* but have not proved that ties would not cause a problem. My thinking is that solutions are stable even if two unmatched mates prefer the other equally to the mate they have now; only a *better* mate is a problem. Hope that's clear. It does not seem necessary for two preference lists to combine in any sensible way. Disclaimer: I am a lay person, only a oldBA in math to fall back on

[@ronaldwangdra9675]

... excuse me?

[@BenjaminAlexander]

Sorry, I think I misread your intention. Yes, the 'list of preferences' is transitive and complete. Or, in plain English, a list. I thought you had some other, more nuanced, insight into how two *different* preference lists had to relate to each other. But to repeat the only interesting thing I said: I think that a single person's preference list could include ties, so long as 'stability' requires a *better* match be available.

[@marc5278]

What happen if the groups are different in size? Does it work?

[@gg.3812]

Awesome video, beautiful mathematician... what more?!

[@anon8109]

Love these proofs. Is there a game-theoretic version of the problem that uses utility functions rather than rankings? I'd like to know what are the ways to define an optimal solution in that case, what algorithms exist, and what their computational complexity is.

[@anon8109]

tabbris I guess what I am asking is how do you choose a best solution among the stable ones if players can assign utilities. We can also allow players to assign the same utility to two or more potential partners, i.e. to allow ties in the rankings.

[@ehrnsp]

Do theorems 2 and 3 hold if each of the women has the same preference list and each of the men has the same preference list?

[@milanvdz]

Does this also work for pairing three (or more?) people/things together? For example if you want the best working study-groups?

[@Hecatonicosachoron]

Is there a way to map out all possible stable solutions?

[@Cpt.Phenom]

How is the priority list compiled on the part of the residency program?

[@wafelsen]

Someone at the hospital running the residency says "Here's who we are interested in accepting from those we interviewed, and this is our order of preference"

[@cbernier3]

she mentioned that, based on interviews.

[@Cpt.Phenom]

scarabbi That makes sense, however, I was wondering along the lines of: whether further math is considered in prioritizing a list since, this time it's the product of group's input rather than the individual that is a groom.

[@SillyPutty125]

I think comments are broken on this video. I am getting email notifications that people are responding to comments, but they don't show up.

[@withmuchrespect]

This was so interesting! well done! well explained! thank you

[@wobblycogsyt]

Great video, do you know of any other uses for this algorithm? I can't help feeling that while it's very elegant it's of limited use because one party will always end up with their worst option.

[@Patashu]

Their worst STABLE option. It could be even worse - it could be instable! This is strictly better than all algorithms that can result in instable configurations. :)

[@vukeidge]

Is there an advantage to using this algorithm over a symmetrical (no bias to either group) algorithm such as the Hungarian Algorithm?

[@fghsinging]

Aaaw... I was expecting her to propose.

[@bpdav1]

"It's a little subtle, its maybe not an easy proof, but I promise if you think about it slowly it'll make sense"... Ok I'm going to think about it reaaaally slowly now cause I'm having trouble getting it!! Such a fascinating concept though

[@hopkinsb4]

Does that imply that the hospitals can game the system by reverse ranking the residents?

[@blackdusken2mb]

If you run through the algorithm assuming the lists in the video but the men proposing you get the same set of marrages. Does this mean the groups are paired with the best and the worst matches? I tried this, rearranging the odd preferance here and there, and no matter which group proposed the result was the same. Does this make sense? Is there a name for this?

[@nicosmind3]

I wonder how many people here subscribe to Numberphile1 but not Numberphile2, but choose to come here with videos they find interesting?

[@zacharycates5485]

Perhaps I'm just misunderstanding, so please correct me where I'm wrong. If the proposers supposedly get the better end of the stick, and in the example the women are the proposers, why is it that 3/4 men got their first choice while only 1/4 women got her first choice? Does that even out or flip the larger the sample group is?