Gale and Shapely asked, “Given a set of preferences among employers and applicants, can we assign applicants to employers so that for every employer E and every applicant A who is not scheduled to work for E, at least one of the following two things is the case?
If this holds, the outcome is stable - individual self-interest will prevent anything from changing. Interestingly, Gale and Shapely were not the first people to work on this algorithm. A decade earlier, there had been similar work dealing with matching residents to hospitals.
*There is a stable matching for every set of preference lists.
To simplify the problem, we do things such as ignore the facts that companies are most likely looking for multiple applicants, that there are most likely more applicants than open jobs and that not every applicant will apply to every company. A simpler problem to face is: each of n applicants applies to each of n companies and every company will only accept one applicant. G&S then use a set of men and a set of women getting engaged as their example. A perfect matching set is a matching set with the property that each man and each woman appear in exactly one pair. Each man and each woman creates a preference list of the members of the opposite gender and these preference lists are used to ensure the matching set is stable. If a pair (m, w') does not belong to S, but both m and w' prefer the other to their current partner, the set is unstable.
Description of the algorithm:
Initially all m ∈ M and w ∈ W are free
While there is a man m who is free and hasn't proposed to every woman
Choose such a man m
Let w be the highest-ranked woman in m's preference list to whom m has not yet proposed
If w is free then
(m, w) become engaged
Else w is currently engaged to m'
If w prefers m' to m then
m remains free
Else w prefers m to m;
(m, w) become engaged
m' becomes free
Endif
Endif
Endwhile
Return the set S of engaged pairs
From looking into the algorithm, we can prove the following things.
The algorithm shows a certain degree of “unfairness” where one side always ends up happier overall. If the men propose, then their preferences are more likely to be matched; the same goes if we change it so that the women propose.
All executions yield the same matching. First, we will say that a woman is a valid partner of a man if there is a stable matching that contains the pair (m,w). w is the best valid partner of m if w is a valid partner of m and no woman whom m ranks higher than w is a valid partner of his. We will use best(m) to denote this.
If we let S* denote the set of pairs {(m, best(m)) : m ∈ M}, we can prove that every execution of the G-S algorithm results in the set S*.
So, for men, the G-S algorithm is ideal (but not ideal for women!). We say that m is a valid partner for a woman w if there is a stable matching that contains the pair (m,w) and that m is the worst valid partner of w/ if m is a valid partner of w and no man whom w ranks lower than m is a valid partner of hers. So, we can then prove that in the stable matching S*, each woman is paired with her worst valid partner. I give this a 10 for level of interest. I think the Stable Matching Problem was very cool and also applicable to real-life situations, such as the residents in the hospitals or students looking for internships. There definitely is a very real need for stable matchings to occur. I also realized that an extension of this is most likely what is used by W&L's formal rush process. We've always been told there's a computer program developed by someone at MIT that is used to decide who goes back to what house each night. I can see how this algorithm would be extremely likely to be related because you take into account both the sororities' and the girls' preferences and see how they match with each other. Haley and I talked about this after class one day.