Gale-Shapley Algorithm: How Stable Matching Works

⏱️ Reading time: 14 min

On September 29, 2026, a thread on X about the Singapore government’s dating app went viral with nearly 500,000 views: FirstDate, the pilot for civil servants aged 21 to 35, runs on the Gale-Shapley algorithm, a mathematical procedure from 1962 that also distributes medical residents among hospitals and organizes kidney exchange chains between strangers.

📑 En este artículo

1. TL;DR
2. What Is the Gale-Shapley Algorithm?
3. Why It Matters
4. How the Gale-Shapley Algorithm Works
5. Practical Code Examples
   1. How to Confirm That a Matching Is Stable
6. Getting Started
7. Real-World Use Cases
8. Comparison with Alternatives
9. Common Mistakes and Best Practices
10. Going Deeper
11. Frequently Asked Questions
    1. Who Invented Gale-Shapley?
    2. Why Did Gale-Shapley Win the 2012 Nobel Prize in Economics?
    3. Is Stable Matching Always Unique?
    4. Can the Deferred Acceptance Algorithm Be Gamed by Lying?
    5. What Does the Rural Hospitals Theorem Guarantee in Stable Matching?
    6. Does Singapore’s FirstDate App Really Use Gale-Shapley?
12. References

The app is just the anecdote: what matters is the mathematical mechanism behind it, awarded the Nobel Prize in Economics in 2012 and still active in decisions that carry far more weight than a date.

TL;DR

• Gale-Shapley matches two groups according to preferences and ensures that no pair would prefer to abandon their assignment.
• The NRMP (National Resident Matching Program) uses a variant of the algorithm to assign doctors to hospitals in the United States.
• Kidney chains use the same stable matching logic between donors and recipients.
• Whoever proposes in each round gets their best possible outcome; whoever receives gets the worst among the stable outcomes.
• At most n² rounds of proposals and rejections are enough to finish without infinite cycles.

What Is the Gale-Shapley Algorithm?

The Gale-Shapley algorithm is a game theory procedure that matches the members of two groups (for example, students and universities) according to their own preference lists, guaranteeing that the outcome is stable: no pair of participants would prefer to abandon their current assignment to pair up with each other instead.

It is also known as deferred acceptance, because no recipient rejects definitively until the end of the process: each one holds onto the best offer received so far and only drops it if a better one arrives. David Gale and Lloyd Shapley devised it to solve college admissions and the stable marriage problem between two groups of equal size. But the mathematical structure doesn’t depend on the context, which is why it now serves for jobs, transplants, and even government-run dating.

Why It Matters

David Gale and Lloyd Shapley published the method in 1962 in College Admissions and the Stability of Marriage, a paper of just eight pages. It proved something no one had formally shown before: that at least one stable matching always exists for two groups with complete preferences, and that a simple procedure of proposals and rejections finds it in a finite number of steps.

Fifty years later, the 2012 Nobel Prize in Economic Sciences recognized that theory, shared between Lloyd Shapley and Alvin Roth. Shapley had built the pure mathematics; Roth spent the following three decades bringing it to real institutions, from doctor assignments to kidney exchanges. The Nobel committee described the work as an example of market design: using theory to build markets, not just describe them.

📌 Note: upon receiving the Nobel, Lloyd Shapley joked that he had never taken an economics course: he considered himself a pure mathematician, and the algorithm that bears his name was born as an exercise in game theory, not public policy.

How the Gale-Shapley Algorithm Works

The procedure runs in rounds. In each round, every proposer who is still free offers to the highest-ranked recipient on their list who hasn’t rejected them yet. Each recipient looks at the offers received so far, including the one already on hold, and keeps the one that suits them best according to their own list, rejecting all the others. A rejected proposer crosses that recipient off their list and, in the next round, tries the next one.

The key is that rejection isn’t final until the end. A recipient can drop whoever they were holding if a better offer arrives, but their situation never worsens round after round. The process ends when no one makes new offers, that is, when every proposer has been accepted or has exhausted their entire list. The following diagram summarizes that cycle:

flowchart TD
    A["Each proposer builds their preference list"] --> B["Free proposer offers to the first non-discarded option on their list"]
    B --> C{"Does the recipient already hold an offer?"}
    C -->|"No"| D["Recipient holds the offer"]
    C -->|"Yes, but prefers the new one"| E["Recipient switches held offer"]
    C -->|"Yes, and prefers the current one"| F["Recipient rejects the new offer"]
    D --> G{"Are there free proposers left?"}
    E --> G
    F --> G
    G -->|"Yes"| B
    G -->|"No"| H["The held offers are the final matching"]

To see it with a concrete case: a doctor can first propose to the hospital they want most, get rejected if that hospital already holds someone ranked higher, and move to the next one on their list in the following round. The sequence diagram shows that negotiation between one proposer and two recipients:

sequenceDiagram
    participant Dr as Dr. Ruiz
    participant A as Hospital A
    participant B as Hospital B
    Dr->>A: proposes in round 1
    A-->>Dr: holds the offer
    Note over Dr,A: Hospital A has no better offer
    Dr->>B: in another simulation, proposes to Hospital B first
    B-->>Dr: rejects, already holding a better offer
    Dr->>A: moves to the next on their list

Practical Code Examples

The algorithm can be coded in under twenty lines. The following Python implementation takes the preference lists from both sides and returns the stable matching that results when the first group proposes:

def gale_shapley(proposer_prefs, receiver_prefs):
    free_proposers = list(proposer_prefs.keys())
    next_proposal = {p: 0 for p in proposer_prefs}
    current_match = {}

    while free_proposers:
        p = free_proposers.pop(0)
        prefs = proposer_prefs[p]
        r = prefs[next_proposal[p]]
        next_proposal[p] += 1

        if r not in current_match:
            current_match[r] = p
        else:
            rival = current_match[r]
            if receiver_prefs[r].index(p) < receiver_prefs[r].index(rival):
                current_match[r] = p
                free_proposers.append(rival)
            else:
                free_proposers.append(p)

    return current_match

proposer_prefs = {"Ana": ["H1", "H2"], "Beto": ["H1", "H2"]}
receiver_prefs = {"H1": ["Beto", "Ana"], "H2": ["Ana", "Beto"]}

print(gale_shapley(proposer_prefs, receiver_prefs))

With just two proposers and two recipients, Beto ends up in H1 and Ana in H2, even though both preferred H1 first. The literal output is:

{'H1': 'Beto', 'H2': 'Ana'}

The same code works for a case with three proposers and three recipients, the minimum size where rejections and chain reassignments already appear:

proposer_prefs = {
    "Dr. Ruiz": ["Hosp A", "Hosp B", "Hosp C"],
    "Dr. Soto": ["Hosp B", "Hosp A", "Hosp C"],
    "Dr. Vega": ["Hosp A", "Hosp C", "Hosp B"],
}
receiver_prefs = {
    "Hosp A": ["Dr. Vega", "Dr. Ruiz", "Dr. Soto"],
    "Hosp B": ["Dr. Ruiz", "Dr. Soto", "Dr. Vega"],
    "Hosp C": ["Dr. Soto", "Dr. Vega", "Dr. Ruiz"],
}

matching = gale_shapley(proposer_prefs, receiver_prefs)
print(matching)

Here Dr. Ruiz first proposes to Hosp A and is accepted, but is then displaced by Dr. Vega, whom Hosp A prefers more. Ruiz relocates to Hosp B, displacing Soto, who ends up at Hosp C. The literal output is:

{'Hosp A': 'Dr. Vega', 'Hosp B': 'Dr. Ruiz', 'Hosp C': 'Dr. Soto'}

How to Confirm That a Matching Is Stable

There’s no need to blindly trust the algorithm: the result can be verified by searching for blocking pairs, two participants who would prefer to be together rather than with their assigned partner. If the function finds none, the matching is stable by definition.

def is_stable(matching, proposer_prefs, receiver_prefs):
    match_of_proposer = {p: r for r, p in matching.items()}
    for p, prefs in proposer_prefs.items():
        r_assigned = match_of_proposer[p]
        rank_assigned = prefs.index(r_assigned)
        for r in prefs[:rank_assigned]:
            rival = matching[r]
            if receiver_prefs[r].index(p) < receiver_prefs[r].index(rival):
                return False
    return True

print(is_stable(matching, proposer_prefs, receiver_prefs))

The literal output is True: there is no doctor who prefers a different hospital whose hospital, in turn, prefers them over who it already has assigned.

Getting Started

You don’t need to install anything beyond Python 3 (any version 3.8 or higher works, no external libraries required).

1. Check the installed version: python3 --version (on Windows, python --version from PowerShell).
2. Save the first code block in a file called gale_shapley.py.
3. Add the is_stable function and the preference dictionaries to the same file.
4. Run it: python3 gale_shapley.py (Windows: python gale_shapley.py).
5. Confirm that the output matches the dictionaries shown above and that is_stable returns True.

Real-World Use Cases

The most cited case is the United States’ National Resident Matching Program (NRMP), which assigns newly graduated doctors to their residency hospitals every year. The original system, from the 1950s, already solved the problem with logic equivalent to Gale-Shapley before anyone had formalized it. Alvin Roth proved it mathematically decades later and helped redesign it in the 1990s so it could also match couples of doctors looking for residencies in the same city, a problem considerably harder than the individual case.

The most dramatic application is kidney exchange. When a donor and a recipient are incompatible with each other but compatible with another pair in the same situation, a stable matching finds chains that allow several simultaneous transplants without anyone giving up an organ without receiving one in return. The National Kidney Registry coordinates chains of this kind, often starting with an altruistic donor who has no specific recipient in mind.

New York and Boston redesigned public school seat allocation with variants of the same mechanism in the early 2000s. They did so after economists showed that the previous system rewarded families who knew how to game their stated preferences, not those who needed a school seat most.

And going back to the opening hook: in FirstDate, each participant builds their preference and rejection list, the system runs a version of the algorithm, and the result is revealed in cycles of one match at a time, with a 72-hour window to decide and identity verification via Singpass. For now the pilot is limited to civil servants aged 21 to 35. The difference from a commercial app isn’t cosmetic: Tinder needs you to keep swiping, while a well-calculated stable matching aims to get you off the platform as soon as possible.

Comparison with Alternatives

Common Mistakes and Best Practices

The most common mistake is assuming that a stable matching distributes advantages equally. It doesn’t: the algorithm doesn’t distribute advantages at random, but systematically in favor of whoever proposes, who always ends up with their best possible outcome among all available stable matchings. Whoever receives the offers, on the other hand, gets the worst stable outcome they could end up with. That’s why it matters a great deal, in residency matching, whether hospitals or applicants propose: the NRMP switched the proposing side in the 1990s precisely because of this asymmetry.

Another mistake is assuming it pays to lie about preferences to game the system. For the proposing side, telling the truth is the dominant strategy: no false list can improve the outcome. The side receiving offers, however, can sometimes benefit from hiding preferences, although in practice detecting when it’s worth doing so is difficult, and almost no real system allows declaring partial information.

The algorithm as Gale and Shapley originally proposed it assumes complete lists with no ties. In real life that almost never happens: a hospital doesn’t know every applicant, and two candidates can look exactly equal to it. Real implementations, the NRMP included, use variants with partial lists and tie-breaking rules, and there the optimality guarantee for the proposer is no longer as clean as in the original model.

⚠️ Watch out: a stable matching is not the same as a socially optimal matching. There can be another assignment that improves outcomes for every participant at once without being stable; the algorithm will never find it because that’s not what it’s looking for.

Going Deeper

Computationally, the Gale-Shapley algorithm runs in O(n²) time in the worst case, where n is the size of each group. Each proposer can make at most n proposals before exhausting their list, and there are n proposers in total, so the number of proposals is bounded by n². It’s a tight bound: instances exist where close to n² proposals are actually needed to reach a stable matching.

The set of all stable matchings for a given problem forms a mathematical structure called a lattice. It has an element optimal for proposers, which is the one the algorithm finds, and an element optimal for recipients, which is the one that results if the roles are reversed. In large problems there can be very many intermediate stable matchings between those two extremes.

A lesser-known but widely used result is the Rural Hospitals Theorem. In any stable matching, the set of recipients left with empty slots is exactly the same, and every recipient with unfilled slots receives the same set of proposers regardless of which stable matching is chosen. This explains why certain hospitals in less attractive locations systematically end up with vacancies, no matter which variant of the algorithm the NRMP uses.

The hardest extension to solve in practice is that of couples applying together and requesting compatible cities. That problem, unlike the individual case, may have no stable matching at all, and finding one when it exists is computationally hard in the worst case. The NRMP still solves it with heuristics that work well in practice, even though they offer no theoretical guarantee for the worst possible case.

Your next step: take the code from this article, build a case with five proposers and five recipients using your own preference lists, and confirm with the is_stable function that the result has no blocking pairs.

Frequently Asked Questions

Who Invented Gale-Shapley?

David Gale and Lloyd Shapley, who published it in 1962 in a paper on college admissions and stable marriage, without yet thinking about its real economic applications.

Why Did Gale-Shapley Win the 2012 Nobel Prize in Economics?

The Nobel recognized matching theory and market design, shared between Lloyd Shapley, who built the mathematics, and Alvin Roth, who applied it to medical residencies and kidney transplants.

Is Stable Matching Always Unique?

No. For the same set of preferences there can be several stable matchings; the algorithm specifically finds the one that’s optimal for the proposing side.

Can the Deferred Acceptance Algorithm Be Gamed by Lying?

The proposing side gains nothing by misrepresenting its preferences, telling the truth is its best strategy. The side receiving offers, however, can sometimes benefit from hiding information.

What Does the Rural Hospitals Theorem Guarantee in Stable Matching?

That the set of recipients with empty slots, and the set of proposers assigned to each of them, is the same in any possible stable matching for that problem.

Does Singapore’s FirstDate App Really Use Gale-Shapley?

According to the thread that originated this story, yes: the government app for civil servants aged 21 to 35 runs a version of the algorithm, with identity verification via Singpass and a 72-hour window per match.

References

• Original thread on X: the description of how FirstDate uses Gale-Shapley.
• Wikipedia: Gale-Shapley algorithm: history and mathematical formalization of the method.
• Nobel Prize 2012 press release: official announcement of the award to Shapley and Roth.
• National Resident Matching Program: the institution that applies the algorithm to medical residencies in the United States.
• National Kidney Registry: coordination of matching-based kidney exchange chains.

📱 Enjoying this content? Follow @programacion on Telegram for daily tech content in Spanish: quick summaries, fresh content every day.

Featured image: Foto de GuerrillaBuzz en Unsplash