The Gale-Shapley algorithm, also called deferred acceptance, matches two groups using ranked preferences. It aims for stability: no unmatched pair would both prefer each other to their current matches. section 2.0 section 2.4
The proposal process works like this:
- Choose one side as proposers. Each free proposer approaches their highest-ranked option they have not yet proposed to. section 2.1.2
- A receiver with no match accepts; one with a match keeps the preferred option and rejects the other proposer. section 2.1.2
- An acceptance is temporary: a rejected proposer can try their next choice, and a receiver can later replace a current match. section 2.3.3
When preferences collide
Suppose students propose to universities. Bob and Carol both propose to X; X prefers Bob, so Carol is rejected. She then proposes to Y, which prefers its current match, Alice, and rejects Carol again. Carol moves on to Z, which accepts her. The example illustrates how rejection and further proposals resolve conflicts. section 2.1.2 section 2.1.2
Listing 2.1 Pseudocode for Gale-Shapley algorithm
Start with all students marked as free.
Keep an empty matching of universities to students.
Repeat while any students remain free:
Take a free student and go through their universities in order of preference.
For the next university the student hasn't proposed to:
If the university has no match:
Match the student with this university and mark them as matched.
If the university already has a match:
Check if the university prefers this new student over their current match.
If yes, replace the current match with this student and mark the old match as free.
If no, keep the current match and leave this student free.
When all students have been matched or exhausted their options, return the final matching.
Pseudocode lays out the free-proposer loop and how a receiver replaces a less-preferred current match. section 2.1.2
The result depends on which side proposes: the algorithm favors proposers among stable matchings. The treatment also gives a worst-case time complexity of O(N²) and names college admissions, online dating, and residency matching as applications. section 2.0 section 2.4
