Chapter 1

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?

• E prefers everyone of its accepted applicants to A;
• A prefers her current situation over working for employer E

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.

1. w remains engaged from the point at which she receives her first proposal; and the sequence of partners to which she is engaged gets better and better (in terms of her preference list)
2. The sequence of women to whom m proposes gets worse and worse (in terms of his preference list)
3. The G-S algorithm terminates after at most n^2 iterations of the While loop.
   1. There are only n^2 possible pairs of men and women in total
4. If m is free at some point in the execution of the algorithm, then there is a woman to whom he has not yet proposed.
5. The set S returned at termination is a perfect matching.
6. A set of pairs S returned at termination is a stable matching.

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.