Can the Gale‑Shapley Algorithm Ensure Stable Couples? A Step‑by‑Step Guide

We imagine a TV dating show with n male and n female participants, each having a ranked preference list for the opposite gender. The question is whether we can find a matching where no two people would rather abandon their current partners to be together, i.e., a stable marriage matching model.

1 Stable Matching Model

The stable matching model is a mathematical framework for pairing problems, widely used in economics, sociology, and computer science. Its key requirement is “stability,” meaning that within the set of pairings there is no pair of individuals who would both prefer to leave their current partners and match with each other.

In other words, each person has an ordered list of preferred partners. The model ensures that each person ends up with a partner as high as possible on their list, and that no two people would both prefer each other over their assigned partners. One‑sided wishes, such as a person preferring someone who does not reciprocate, do not violate stability.

Below is an illustration of an unstable matching:

2 Algorithm

How can we find a stable matching? The Gale‑Shapley algorithm provides a solution through a series of proposals and selections.

Initially, all unpaired “proposers” (e.g., all men) propose to their highest‑ranked “proposees” (e.g., all women) according to their preference lists. Each proposee reviews all received proposals and temporarily accepts the one she prefers most. If she already has a tentative match, she keeps the more preferred of the two. Rejected proposers continue to propose to the next person on their list. This process repeats until every proposer is matched, and no one wishes to change, at which point the matching is stable.

3 Example

Consider a simplified case with three men (A, B, C) and three women (X, Y, Z) with the following preferences:

Men’s preferences:

A: Y > X > Z

B: X > Y > Z

C: Y > Z > X

Women’s preferences:

X: B > A > C

Y: A > B > C

Z: C > B > A

Following the Gale‑Shapley steps, the matching proceeds as follows:

Round 1 : A proposes to Y, Y accepts (Y’s top choice). B proposes to X, X accepts (X’s top choice). C proposes to Y, but Y is already matched with A and prefers A, so she rejects C.

Round 2 : C, still unmatched, proposes to his next choice Z, and Z accepts (Z’s top choice).

Round 3 : All participants are now matched. Checking for instability shows that each pair (A‑Y, B‑X, C‑Z) is stable because each partner is each other’s highest available choice given the current matches.

Final stable matches:

A‑Y

B‑X

C‑Z

The algorithm guarantees that, given the preference lists, the resulting matching is stable—no individual can improve their outcome by switching partners.

Thus, this method ensures that everyone finds a partner as close as possible to their preferences while maintaining overall harmony and stability.

4 Why Might Real Marriages Be Unstable?

In reality, many marriages are unstable or discordant. The stable matching model assumes that participants’ preferences are fixed and fully known. In practice, preferences, needs, and expectations evolve over time, which can turn an initially stable match into an unstable one.

Moreover, the model presumes complete information about all potential partners, which is rarely the case. New information about a partner’s behavior or habits can affect marital satisfaction.

If the initial match is based on limited information or immature decisions, it may appear stable in the model but contain hidden instability.

The stable matching model provides a useful theoretical framework for understanding partner selection, but it does not capture all complexities of real marriages. Beyond dating, the model is applied to labor markets, school assignments, organ donation, and other allocation problems.