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?
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...
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?
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.
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 =)
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 :)
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...
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?
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”.
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.
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?
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.
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.
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.
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.
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)?
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.
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.
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.
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)
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 TH-cam channels.
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?
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.
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?
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.
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.
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.
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).
+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?
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".
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?
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.
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.
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.
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.
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.
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.
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).
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.
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
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?
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.
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.
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
***** 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.
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.
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?
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?
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
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.
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...
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?
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?
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?
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.
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.
Well, There are algorithms that minimize a function that calculates the fairness of marriage. Some of the criteria used in literature are: egalitarian, regret and sex equality. For the first two criteria, there are polynomial algorithms to find a matching that is egalitarian or has minimum regret. Finding a matching that is sex-fair is NP-hard.
Here's one. Make a list of all of the people in a random order, and repeat the following steps: 1) Chose the first person on the list who has no tentative engagement. 2) Have them propose to others, in order of preference, until they are accepted. A person receiving a proposal accepts when the person is preferable to their previous engagement. These two steps are repeated until everyone has been paired. In this configuration, the people at the top are favored over the people at the bottom.
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)
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.
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. :)
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").
Could a switch between proposing sides every day (you may not propose to someone you rejected or that rejected you, but propose to the best left on your list) produce a stable configuration that has less bias to one side? So First the women propose, next the men who have a better match on their list propose to the best of those, then the women propose and so on? My thoughts were that this might mitigate the problem with matching the passive side with the worst possible matches... But my Math-Fu isn't strong enough to prove this.
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?
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"
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.
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.
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.
The Kirtpole I think that's what the Medical Board problem does. There are more hospitals than there are residents, so each hospital has to choose more than one resident.
Would it be possible to solve this problem with an Hungarian algorithm (with cost of matching inversely proportional to the preference of both woman and man)? I guess the solution might not be stable but it would be produce a matching "more" fair for both women and men, no?
This solution exercises any instability beforehand, obtains an equilibrium, and only then are the marriages final. It's simply working out all the cheating and divorces on paper before the pairings are final. That seems like cheating to me.
Considering when this algorithm is used, this might be a moot point, but what if a man would prefer *not* being married instead of being married to particular women?
By "possible" she means the configurations that are stable. If a man gets his top choice, that means that there are no stable configurations where he gets a lower choice because he must get his worst possible choice.
Because that choice was the only possible choice in this particular configuration of the problem. Obviously, if there's only one possible choice, it's both the best and the worst possible choice.
In the example there is only one possible stable configuration, as many have pointed out. In examples with, say, 100 people, there may be many stable configurations and you would see the difference.
My question exactly. What if my first choice proposes to me on round one? Naturally, we will stick together through the other rounds. So I don't see how that is my worst possibility.
But then you are HER first choice also, and if two people are each others first choice then the ONLY stable situation is when they are together. However, seeing as it is the women who are proposing, you may never get proposed to by your top choice even if being with her would be stable.
She is so cool and clear in her explanations. I'd love for you to have her on more!
So... the conclusion is: Whoever takes the initiative gets the best match :)
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?
She did an excellent job explaining this, IMO. Hope to see more of her in future videos.
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...
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?
Charlotte and Collins should have just gone their own ways. Sounds like it would be a miserable household! And think of the poor children!
Or cheat... just sayin'
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.
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 =)
but if there were no other single people, then they would end up alone. It is either each other or no one.
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 :)
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...
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?
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”.
Jonathan Moore Okay, that works. Makes sense. Different solutions both ways when I checked. :)
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.
we can ask ourselves how small the smallest population is where there are multiple possible stable marriages...
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?
Dr. Riehl is so good at explanation!!! Thank you!!! This has so much application potentials.
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.
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
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.
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.
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.
MadaxeMunkeee check my example above, it is a counter-example to your proof.
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.
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)?
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.
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.
I'm taking a topology course from her this year! Cool.
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.
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)
I'm about to make my preference list for residency programs and I love this video! The math reassures me in my ranking
I love this. As a total novice, she explains it in a non esoteric way I can understand. Thanks.
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 TH-cam channels.
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?
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.
Dr Emily Riehl did a wonderful job explaining something that was once a partially understood algorithm. Thank you!
This is probably one of my favorite recent Brady videos. Yay for logic problems!
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?
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.
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.
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.
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).
no, not every relationship, because this disregards many circumstances and options, but it does what it does.
+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?
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".
This could be applied to employment.
This is such a cool one - definitely one of my favourite numberphiles.
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?
I really like her. More videos with her please! Good job Brady, keep it up!
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?
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.
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.
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.
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.
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.
Collins and Charllote are miserable...
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.
she did not just "I'll leave you to prove as exercises" us
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).
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.
she talks with the cadence of my rabbi. It's not an insult or complement, just a little eerie how close it is.
it works the same if you switch the roles
This is actually the exact system used for college applications in Ireland, I never knew that it was based on anything mathematical.
What about the cases where there at an odd number of people?
0:29 "Something special"?This reminds me of the base case in recursion.Does this algorithm use recursion and this is the base case?
Game theory has a way of representing this problem mathematically. You would, however, have to use game theory notation.
Where can I read about it?
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
Thank you!
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?
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.
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.
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
***** 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.
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.
I don't quite understand Theorem 3. How's the argument the same as Theorem 2?
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?
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!
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?
I think it's not insignificant to mention that the ranking list has some assumptions: completeness and transitivity.
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
... excuse me?
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.
How many stability states are there? Does this algorithm guarantee the most optimized stability state if there is more than one?
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...
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?
Is the same algorithm used in sending military recruits to their selected preferences?
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?
Its just like in chess with white having first moves, all things being equal - white has a slight edge
Is there any algorithm that puzzles together the best possible matches for everyone?
Unstable marriage pairs just need to "party" together and they'll be happier.
Brady, in the dooblydoo the "continues from" link leads to a removed video. The correct link is this: Stable Marriage Problem - Numberphile
Is there an advantage to using this algorithm over a symmetrical (no bias to either group) algorithm such as the Hungarian Algorithm?
Does this also work for pairing three (or more?) people/things together? For example if you want the best working study-groups?
Does that imply that the hospitals can game the system by reverse ranking the residents?
"There is no advantage to lying at all... and that we can prove". What an amazing quote. :D
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?
Is there any way to make the odds the same for both the proposer and the proposed?
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.
Is there a way to map out all possible stable solutions?
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?
en.wikipedia.org/wiki/Stable_roommates_problem
not always
Thanks!
love this problem. Thanks to both of you for sharing :)
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.
I don't understand the proof of 2 and 3. Surely you could have the situation without M' if it's the first round of the algorithm right?
Is there some algorithm that doesn't favour either the men or women?
Tim Anderson Um, randomize all the things? ;)
(It's technically correct because it doesn't really favor anyone.)
It wouldn't create stable marriages then.
en.wikipedia.org/wiki/Hungarian_algorithm
Well, There are algorithms that minimize a function that calculates the fairness of marriage. Some of the criteria used in literature are: egalitarian, regret and sex equality. For the first two criteria, there are polynomial algorithms to find a matching that is egalitarian or has minimum regret. Finding a matching that is sex-fair is NP-hard.
Here's one. Make a list of all of the people in a random order, and repeat the following steps:
1) Chose the first person on the list who has no tentative engagement.
2) Have them propose to others, in order of preference, until they are accepted. A person receiving a proposal accepts when the person is preferable to their previous engagement.
These two steps are repeated until everyone has been paired. In this configuration, the people at the top are favored over the people at the bottom.
In the particular example used in the video, the couples end up being exactly the same regardless of which sex proposes.
Interesting video.
Small problem, the link "Continues from: ..." is broken.
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?
What if someone likes two people equally and they would roll dice to decide whom to reject?
Hey Brady nice to see a new video! :)
Does this mean that job seekers applying to jobs are more likely to get a better job than when they're recruited?
Emily seems like a really cool person! This was a very interesting video :)
Thank you Dr Riehl.
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)
What happen if the groups are different in size? Does it work?
You presented this excellently...thanks!
So Beyoncé's advice was correct:
"If you liked it then you should have put a ring on it".
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.
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.
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. :)
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").
Could a switch between proposing sides every day (you may not propose to someone you rejected or that rejected you, but propose to the best left on your list) produce a stable configuration that has less bias to one side? So First the women propose, next the men who have a better match on their list propose to the best of those, then the women propose and so on?
My thoughts were that this might mitigate the problem with matching the passive side with the worst possible matches... But my Math-Fu isn't strong enough to prove this.
This was fascinating. Thanks for the video!
This was amazing! Thank you!
Numberphile2 i think at 6:19 she said the opposite of what she meant!
oh no maybe not
This was GREAT. Next, please deal with the Stable rooommates problem. And Condorcet voting. And: has anyone connected these two problems in any way?
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?
How is the priority list compiled on the part of the residency program?
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"
she mentioned that, based on interviews.
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.
This could have been on computerphile, no? Still enjoyed it.
for me this problem only shows that not everyone can win
So many properties end up being no-infinite-regression-in-well-ordered-sets...
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.
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.
What if instead of couples you have groups? What if instead of arranging 8 people into four couples I want to arrange 30 people into 2 groups of 15?
The Kirtpole I think that's what the Medical Board problem does. There are more hospitals than there are residents, so each hospital has to choose more than one resident.
u know this would be a fun classroom activity.
Would it be possible to solve this problem with an Hungarian algorithm (with cost of matching inversely proportional to the preference of both woman and man)? I guess the solution might not be stable but it would be produce a matching "more" fair for both women and men, no?
This solution exercises any instability beforehand, obtains an equilibrium, and only then are the marriages final. It's simply working out all the cheating and divorces on paper before the pairings are final. That seems like cheating to me.
Considering when this algorithm is used, this might be a moot point, but what if a man would prefer *not* being married instead of being married to particular women?
How can you say that the men get the worst possible choice when 3 of them got their top choice?
By "possible" she means the configurations that are stable. If a man gets his top choice, that means that there are no stable configurations where he gets a lower choice because he must get his worst possible choice.
Because that choice was the only possible choice in this particular configuration of the problem. Obviously, if there's only one possible choice, it's both the best and the worst possible choice.
In the example there is only one possible stable configuration, as many have pointed out. In examples with, say, 100 people, there may be many stable configurations and you would see the difference.
My question exactly. What if my first choice proposes to me on round one? Naturally, we will stick together through the other rounds. So I don't see how that is my worst possibility.
But then you are HER first choice also, and if two people are each others first choice then the ONLY stable situation is when they are together. However, seeing as it is the women who are proposing, you may never get proposed to by your top choice even if being with her would be stable.