Depending on the which gender does the initiation; the result is either male optimal (males get the best he can get, females gets the worst among those she would tolerate) or female optimal. I wonder which version this one is.
Imagine you are the proposer. You will start at the top of your list and work your way down only if rejected. So you are guaranteed to the best you could possibly do.
Imagine
A ranks X,Y,Z in that order
B ranks Y,X,Z in that order
C ranks X,Y,Z
X, Y, Z rank A,B,C in that order.
A will propose to X and match.
B will propose to Y and match.
C will propose to X and get rejected.
C will propose to Y and get rejected.
C will propose to Z and match.
Y will never get a proposal from A. Z will never get a proposal from A or B.
(A,X),(B,Y) as the proposals is fine for the point being made. The issue is if we reverse which group is the proposer, we still end up with the same matching, because (A,X) strictly prefer each other.
The minimal example with 4 participants is if each person P has unique preferences and P's 1st choice has P as 2nd choice. So in this case just flip X:
A:XY
B:YX
X:BA
Y:AB
If A,B propose you get AX,BY. If X,Y propose you get BX,AY. Both are stable because the proposers are getting their first choice.
Not sure if you're referring to the actual definition. It's basically "no two participants from different pairs in the matching would prefer each other to their current matches." It seems an elegant definition to me.
This obviously doesn't factor in most of the complexity of romantic relationships: not knowing your own preferences, evolving preferences, incomplete/imperfect information in general, etc. Plus it assumes a global 1:1 matching across two categories, and people can of course be LGBT or choose to be single.
I left another comment with the minimal example, but intuitively:
- proposers descend from their 1st choice, while recipients ascend according to their offers; the outcome can't be recipient-biased, because recipients ascend only when proposers are forced to descend
- a matching is stable if each pair contains at least one party that cannot find a strictly better match
- in particular there are multiple distinct matchings, and if proposer-biased, recipients have no recourse to break the proposer-favored pairs
I think it can be a bit easier to think of the algorithm in terms of job applicants (who receive job offers) and employers (who propose job offers). And then due to the algorithm, it must be the case that the number of applicants is equal to the number of employers, and each employer is only trying to fill one position.
An applicant (the receiver) will end up with a "worst" match in the sense that if you look at all "stable" pairings (there can be multiple configurations), the applicant is going to have the least favorable one among the different pairings.
There's an important concept of a "blocking pair", and the Gale-Shapley algorithm is trying to eliminate all blocking pairs, and you could say that pairings are stable when no blocking pairs exist. A blocking pair is a job applicant and employer who aren't matched together, but both prefer each other over their current match.
Suppose that after the algorithm is done with its work, Alice doesn't end up with a job offer from her top choice, Google. This must mean that Google never offered her a job because Alice was just too far down on their list, and Google made a deal with someone else they like better than Alice.
If Google’s top choice is Alice, and Alice’s top choice is Google, then what will happen in the algorithm is that Alice will see an offer from Google and lock it down. Alice could get multiple offers but she will take the best one which is Google.
When Alice and Google are not paired up, then they will always form a “blocking pair” in any matching where they aren’t together so that means any matching that doesn’t have Alice and Google paired is not stable.
I think the confusion is that Alice only has one possible stable employer and thus her worst one happens to be her best one.
If Alice’s top choice wasn’t Google, but some other company, then there might be multiple employers she could be matched with to form a stable pairing.
This algorithm is definitely weird too though because it’s possible for some candidates to be paired with a company they don’t really like, but it’s considered a stable situation because the other companies don’t want them more than their current employees.
I guess in real life, you could try improving yourself and then the matching becomes unstable again if preferences change.
> it’s possible for some candidates to be paired with a company they don’t really like, but it’s considered a stable situation
Thus extrapolating to a dating app, it’s possible for someone in the matched pair to not really like the other person. Sounds like a rousingly success.
The article also mentioned that, but I don’t understand it. Receivers are also making choices, so why do they end up with the worst match?
You have to accept the best offer you get, if there's someone that you would like, you only match with them if all their better options are exhausted.
Imagine you are the proposer. You will start at the top of your list and work your way down only if rejected. So you are guaranteed to the best you could possibly do.
Imagine A ranks X,Y,Z in that order B ranks Y,X,Z in that order C ranks X,Y,Z
X, Y, Z rank A,B,C in that order.
A will propose to X and match. B will propose to Y and match. C will propose to X and get rejected. C will propose to Y and get rejected. C will propose to Z and match.
Y will never get a proposal from A. Z will never get a proposal from A or B.
Edit: I think I fixed it.
Why will B propose to X first if their first choice is Y?
You’re absolutely right. I’m on my phone trying to imagine the scenarios in my head and trying to find the simplest possible example.
Maybe 4 participants is too few to clearly see what happens.
(A,X),(B,Y) as the proposals is fine for the point being made. The issue is if we reverse which group is the proposer, we still end up with the same matching, because (A,X) strictly prefer each other.
The minimal example with 4 participants is if each person P has unique preferences and P's 1st choice has P as 2nd choice. So in this case just flip X:
A:XY B:YX X:BA Y:AB
If A,B propose you get AX,BY. If X,Y propose you get BX,AY. Both are stable because the proposers are getting their first choice.
I find this algorithm to have a curious definition of the word "stable."
Not sure if you're referring to the actual definition. It's basically "no two participants from different pairs in the matching would prefer each other to their current matches." It seems an elegant definition to me.
This obviously doesn't factor in most of the complexity of romantic relationships: not knowing your own preferences, evolving preferences, incomplete/imperfect information in general, etc. Plus it assumes a global 1:1 matching across two categories, and people can of course be LGBT or choose to be single.
The big assumption here is that people are either proposers or receivers and never switch roles.
Which may be largely true for many people but it's definitely not a fixed thing!
When I was dating, I initiated with a lot of women, but the woman I wound up marrying messaged me first.
This assumption is built-in for Gale-Shapley algorithm.
I left another comment with the minimal example, but intuitively:
- proposers descend from their 1st choice, while recipients ascend according to their offers; the outcome can't be recipient-biased, because recipients ascend only when proposers are forced to descend
- a matching is stable if each pair contains at least one party that cannot find a strictly better match
- in particular there are multiple distinct matchings, and if proposer-biased, recipients have no recourse to break the proposer-favored pairs
I think it can be a bit easier to think of the algorithm in terms of job applicants (who receive job offers) and employers (who propose job offers). And then due to the algorithm, it must be the case that the number of applicants is equal to the number of employers, and each employer is only trying to fill one position.
An applicant (the receiver) will end up with a "worst" match in the sense that if you look at all "stable" pairings (there can be multiple configurations), the applicant is going to have the least favorable one among the different pairings.
There's an important concept of a "blocking pair", and the Gale-Shapley algorithm is trying to eliminate all blocking pairs, and you could say that pairings are stable when no blocking pairs exist. A blocking pair is a job applicant and employer who aren't matched together, but both prefer each other over their current match.
Suppose that after the algorithm is done with its work, Alice doesn't end up with a job offer from her top choice, Google. This must mean that Google never offered her a job because Alice was just too far down on their list, and Google made a deal with someone else they like better than Alice.
> configurations), the applicant is going to have the least favorable one among the different pairings.
I don’t understand why this would always be true. In your example, Google may indeed like Alice, so they both get their top choice.
If Google’s top choice is Alice, and Alice’s top choice is Google, then what will happen in the algorithm is that Alice will see an offer from Google and lock it down. Alice could get multiple offers but she will take the best one which is Google.
When Alice and Google are not paired up, then they will always form a “blocking pair” in any matching where they aren’t together so that means any matching that doesn’t have Alice and Google paired is not stable.
I think the confusion is that Alice only has one possible stable employer and thus her worst one happens to be her best one.
If Alice’s top choice wasn’t Google, but some other company, then there might be multiple employers she could be matched with to form a stable pairing.
This algorithm is definitely weird too though because it’s possible for some candidates to be paired with a company they don’t really like, but it’s considered a stable situation because the other companies don’t want them more than their current employees.
I guess in real life, you could try improving yourself and then the matching becomes unstable again if preferences change.
> it’s possible for some candidates to be paired with a company they don’t really like, but it’s considered a stable situation
Thus extrapolating to a dating app, it’s possible for someone in the matched pair to not really like the other person. Sounds like a rousingly success.
Is it necessarily so?
And doesn't something of the same kind happen in real-life, in some societies or countries or cities male-optimal and in others female-optimal ?
It is necessarily so if you're using Gale-Shapley for heterosexual matching, yes.
they could just swap the direction for each matching
it's proposer-optimal but the receivers gets the best of those who haven't already found a better match