liveBook · Manning

Gale-Shapley algorithm

As explained in Algorithms Every Programmer Should Know

The Gale-Shapley algorithm, also called deferred acceptance, constructs a stable matching through proposals that can be tentatively accepted and later displaced.

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

How Algorithms Every Programmer Should Know covers it

How deep it goes
Traces proposals, rejection, and rematching, then discusses stability, termination, proposer bias, and complexity.
Examples
Works through student–university proposals, including a contested university and repeated rejection, and names dating and residency matching.
What it assumes
Assumes ranked preference lists for two groups and introduces stability through a student–university example.
What you can do after
Understand how to trace proposals, check for stability, and recognize how the proposer side affects outcomes.
How it connects
Connects stable matching to deferred acceptance, preference rankings, and proposer optimality.

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.