The Gale–Shapley Algorithm — Why Deferring Acceptance Produces Stable Matchings, Shown by Running It

Every autumn, final-year medical students in Japan submit a list of the hospital training programs they want, in order of preference, and the hospitals submit lists of the students they want to hire. A computer decides who goes where, and everyone learns the result on the same day. This is the Japan Residency Matching Program (JRMP). At the heart of the procedure is deferred acceptance — the Gale–Shapley algorithm that David Gale and Lloyd Shapley described in a seven-page paper in 1962.

The algorithm fits in about twenty lines, and the following properties have been proved about it.

• A stable matching always exists, and one can be found in $O(n^2)$ time.
• The result does not depend on the order of proposals, and it is the best stable outcome for the side that proposes and the worst for the side that receives.
• Proposers cannot gain by misreporting their preferences. Receivers sometimes can.
• With random preferences, proposers end up with an average rank of about $\ln n$ and receivers with about $n / \ln n$ — a big gap. Yet adding a single agent to one side makes it almost irrelevant who proposes: the short side gets an average rank of about $\ln n$ either way.

The original paper and many textbooks describe the algorithm with the metaphor of men proposing marriage to women. This article uses the gender-neutral terms proposers and receivers. The agents on the left are A, B, C, D and those on the right are W, X, Y, Z. It may help to read the left side as residents, students or applicants, and the right side as hospitals, schools or employers.

For just the algorithm and its implementation, read sections 1.1–1.2, 3, 4.5 and 10. Sections 4–5 explain why it works and which stable matching it returns, section 6 covers misreporting, section 7 random markets, section 8 real market design, and section 9 variants and hardness. Collapsed proofs and deep dives can be skipped without losing the thread. Key terms and the sections that define them: blocking pair (1.2), deferred acceptance (section 3), valid partner (5.2), rotation (5.4–5.5), truncation (6.2), individual rationality (8.1) and cutoff (8.4).

1. The problem: matching when both sides have preferences

1.1 Setting

There is a set $L$ on the left and a set $R$ on the right; for now both have $n$ members. Every agent ranks everyone on the other side strictly, with no ties. We write $a \succ_x b$ when $x$ prefers $a$ to $b$.

A matching $\mu$ is a set of left–right pairs in which each agent appears in at most one pair. We write $\mu(x)$ for $x$'s partner.

Throughout the article we use the following 4-by-4 «running example».

B, C and D all list Z first, so in this example they compete for Z.

1.2 Blocking pairs and stability

Given a matching $\mu$, two agents $(a, w)$ from opposite sides who are not matched to each other form a blocking pair if

Both of them prefer each other to their current partners. An agent without a partner is assumed to prefer any partner to none (we drop this assumption for truncated reports in section 6 and in general in section 8).

A matching with no blocking pair is called stable.

Take, for example, the matching A–W, B–X, C–Y, D–Z (written «AW BX CY DZ» from now on). B prefers W (its 2nd choice) to its partner X (4th), and W prefers B (2nd) to its partner A (4th). So $(B, W)$ is a blocking pair, and this matching is not stable.

1.3 Why ask for stability?

The two agents of a blocking pair have a reason to ignore the assignment and make a deal on their own. Once one such side deal happens, the rest of the assignment can unravel. Stability is the condition under which nobody has an incentive to trade outside the system — the condition under which an assignment is actually honored.

In the 1940s, US hospitals competing for good students kept moving their offers earlier, until appointments were being made nearly two years before graduation. When the medical schools agreed in 1945 to hold back transcripts and letters until a fixed date, the competition simply moved to deadlines: offers were supposed to stay open for 10 days in 1945, and the interval shrank every year until, by 1949, even a 12-hour grace period was rejected as too long (Roth, 1984). These were «exploding offers» that had to be answered before hanging up the phone. A centralized match (today's NRMP) was introduced in 1952, the chaos subsided, and participants voluntarily stayed with it.

Alvin Roth (1984) pointed out that the procedure in use since 1952 produced stable matchings, and argued that this was why it succeeded. Roth (1991) then compared the regional residency matches of the United Kingdom and found that the schemes producing stable matchings survived, while most of those that did not were abandoned.

1.4 Why not maximize total satisfaction?

One could convert preferences into scores and maximize «total satisfaction» — solve an assignment problem with the Hungarian method, say. That solution need not be stable. In the running example, minimizing just the left side's total rank gives AW BZ CY DX (total 6), but $(C, Z)$ and $(D, Z)$ are blocking pairs. Minimizing the total rank of both sides happens to pick two of the stable matchings in the running example (AZ BW CY DX and AZ BY CW DX, the «egalitarian» ones of section 5.5), but that is not guaranteed either: on randomly generated 4-by-4 instances, roughly one time in four every matching with the minimum two-sided total rank is unstable. Stability is a condition about each participant's incentives — nobody wants to defect — rather than about a sum, and it is defined from rankings alone, without assuming numeric utilities. Both properties make it practical.

2. The naive approach: fix unhappy pairs one at a time

The most naive way to build a stable matching is to start from any matching and, while a blocking pair exists, let those two pair up. If we also pair up the two partners they abandoned, everybody keeps a partner.

This procedure does not always end. Try it in the demo below. It starts with a 3-by-3 example. Click a preference chip to rearrange the matching by hand; blocking pairs show up as red dashed lines.

Press «Cycle scenario» four times. It resolves $(C, X) \to (C, Y) \to (A, Y) \to (A, X)$, each a genuine blocking pair at that moment, and yet it arrives back at the starting matching AX BY CZ. As long as pairs are chosen this way, the procedure never ends. Knuth (1976) pointed out that resolving blocking pairs can cycle.

If instead $(C, Y)$ is chosen at the start, a single step reaches the stable matching AX BZ CY. Roth and Vande Vate (1990) showed that from any matching, a well-chosen finite sequence of resolutions reaches a stable matching, and that choosing blocking pairs at random reaches one with probability 1 (in their model, abandoned partners become single). The random approach can, however, need exponential expected time on some instances (Ackermann et al., 2011).

Switch the demo to «Running example (4×4)» and it starts from AW BX CY DZ, the matching of section 1.2, with two blocking pairs, $(B, W)$ and $(B, Y)$. Resolving $(B, W)$ pairs up the abandoned A and X and reaches AX BW CY DZ in one step — exactly the stable matching Gale–Shapley returns in the next section.

So fixing blocking pairs one at a time may never finish, depending on which pairs are chosen. The Gale–Shapley algorithm of the next section is a procedure that always stops and returns a stable matching, whatever order it runs in.

3. The Gale–Shapley algorithm (deferred acceptance)

3.1 The procedure

Call one side (here the left) the proposers and the other side the receivers.

start with everyone free (unmatched)
while some proposer p is free and still has someone left to propose to:
    r ← the receiver p likes best among those p has not proposed to yet
    p proposes to r
    if r holds nobody:
        r holds p «tentatively»
    else if r prefers p to the proposer p' it currently holds:
        r holds p and lets go of p' (p' becomes free)
    else:
        r rejects p
finalize the pairs currently held and stop

Two rules drive the procedure. Proposers propose one at a time, in order of preference, moving on when rejected. Receivers hold only the best proposal received so far and reject the rest. Holding is not a commitment: if a better proposal arrives later, the receiver trades up.

3.2 Running it

Step through the running example in the demo below. The tables on both sides show each agent's preferences; a chip's look tells you whether it is part of the current proposal (amber), next to be proposed to (dashed amber), tentatively held (gray), rejected or turned away (struck through) or in the final result (green). The «#k» at the end of each row is the position of that agent's current partner in its own list (a proposer without a partner shows «→#k», the position of its next proposal). Before pressing play, try to predict whom B ends up with.

In the running example (A–D propose, one at a time) the algorithm stops after these seven proposals.

1. A → W (1st choice). W is free and holds A tentatively.
2. B → Z. Z is free and holds B tentatively.
3. C → Z. Z ranks A > D > C > B, so it lets B go and trades up to C. B is free again.
4. D → Z. Z prefers D to C, so it lets C go and trades up to D. C is free again.
5. B → W (2nd choice). W ranks C > B > D > A, so it lets A go and trades up to B. A is free again.
6. C → Y (2nd choice). Y is free and holds C.
7. A → X (2nd choice). X is free and holds A. Everyone has a partner, so the algorithm stops.

The result is AX BW CY DZ, with no blocking pair. In steps 3–5, B, pushed out of the contest for Z, proposes to W and in turn pushes out A, whom W had been holding. Each time a receiver trades up, the proposer it drops proposes to its next choice, and the chain continues.

3.3 What if acceptance is not deferred?

Switch the demo's «Acceptance» setting to «Immediate (Boston)». Under immediate acceptance, in round $k$ every unassigned proposer applies to their $k$-th choice, and receivers make their acceptance final on the spot. A better proposal arriving later cannot change it.

The running example now ends in AW BX CY DZ, leaving $(B, W)$ and $(B, Y)$ as blocking pairs. In round 1, B applied to the popular Z and was rejected — and meanwhile W permanently accepted A, whom W ranks last. W prefers B to A but no longer has a seat.

Because Boston's public schools once used this rule, it is called the «Boston mechanism». The «deferred» in deferred acceptance refers exactly to this: postponing commitment until the very end. The difference also decides whether truthful reporting is the best strategy (section 6.4).

3.4 The order of proposals does not matter

Now switch the demo's «Proposal order». «All at once (rounds)» is how Gale and Shapley wrote it: in each round every free proposer proposes simultaneously and each receiver keeps only its best offer. The running example finishes in three rounds. «Queue», «Stack» and «Random» all pick one free proposer at a time, the version common in algorithms textbooks; the stack version, in which a proposer who becomes free proposes again immediately, corresponds to the chain-reaction formulation of McVitie and Wilson (1971).

Whatever the order, the final result stays AX BW CY DZ and the number of proposals stays 7. Section 5 proves that this always holds.

4. Why it works

4.1 Two monotonicity properties

The proofs need only two facts that are visible directly in how the algorithm behaves.

• Receivers only get better: once a receiver has received a proposal, it holds someone for the rest of the run, and every trade-up gives it someone it likes more.
• Proposers only get worse: each proposer works down its own list. It never proposes to the same receiver twice, and each proposal goes to someone it likes less than the last.

The «#k» at the end of each row in the demo of section 3.2 shows this directly: proposers' numbers only grow and receivers' numbers only shrink.

4.2 Termination: at most $n^2 - n + 1$ proposals

Each proposer proposes to each receiver at most once, so there are at most $n^2$ proposals and the algorithm always stops. We can count more precisely.

Everyone is matched exactly when the last receiver receives its first proposal (by monotonicity, a receiver that has been proposed to keeps holding someone, so once every receiver has been proposed to, everyone has a partner). Until just before that moment, at least one receiver $r^*$ has not been proposed to by anyone. So each proposer has made at most $n - 1$ proposals so far, for at most $n(n-1)$ in total. Adding the final proposal,

This bound is attained exactly. The «Worst case» preset of the demo in section 3.2 is a 4-by-4 instance that needs 13 proposals. «Identical lists» (every proposer ranks W > X > Y > Z), the most competitive case, still falls short of the worst case: everybody proposes to W, one of them stays, the rest propose to X, and so on, so it takes only $4 + 3 + 2 + 1 = 10$ proposals whatever the receivers' preferences. The minimum is $n = 4$, reached whenever all first choices differ (for example when W–Z propose in section 5.1). Since the demo lets you edit any list by clicking its chips, try starting from the running example and see how high you can push the number of proposals.

4.3 Everyone gets a partner

Suppose some proposer $p$ is still free at the end. A proposer stops free only after proposing to everyone on its list. Then every receiver has been proposed to at least once, so every receiver holds someone. If the $n$ receivers each hold a different proposer, all $n$ proposers are held — contradicting the fact that $p$ is free.

4.4 Stability

Suppose the output $\mu$ had a blocking pair $(p, r)$. Since $r \succ_p \mu(p)$ and $p$ proposes in order of preference, $p$ proposed to $r$ before $\mu(p)$. They did not end up together, so at some point $r$ rejected $p$ (immediately, or later by trading up). At that point $r$ held someone it liked more than $p$, and since receivers only get better, its final partner $\mu(r)$ is also someone it likes more than $p$. That contradicts $p \succ_r \mu(r)$.

4.5 Running time and implementation essentials

If each proposal is processed in $O(1)$ time, the whole run takes $O(n^2)$. The key is to convert the receivers' preferences into a rank table first.

• rank[r][p]: the position of $p$ in receiver $r$'s list. «Does $r$ prefer $p$ or $p'$?» takes two array lookups.
• next[p]: the position in $p$'s list of the next receiver to propose to.
• Keep the free proposers in a queue or a stack.

Without a rank table, finding «where is $p$ in this list?» by linear search makes each comparison $O(n)$ and the whole algorithm $O(n^3)$.

The input itself ($2n$ lists of length $n$) has size $\Theta(n^2)$, so $O(n^2)$ is linear in the size of the input. And it cannot be done faster: measured by the number of queries to the preference lists, finding a stable matching needs $\Omega(n^2)$ queries in the worst case (Ng and Hirschberg, 1990). Similar lower bounds hold for randomized algorithms and for communication (Gonczarowski et al., 2019). A Python implementation and tests are in section 10.

5. Which stable matching, and good for whom?

5.1 There can be more than one stable matching

Let the receivers (W–Z) propose in the running example. The run ends after four proposals — W→C, X→D, Y→B, Z→A — and the result is AZ BY CW DX. Every receiver gets its first choice, while A, B and C get their 3rd choice and D its 2nd. This matching is stable too. So the result depends on which side proposes. Which of the stable matchings, then, does Gale–Shapley return?

5.2 Proposer-optimality

If a proposer $p$ and a receiver $r$ are paired in at least one stable matching, call $r$ a valid partner of $p$. Write $\mathrm{best}(p)$ for $p$'s favorite valid partner.

The running example has four stable matchings (section 5.4), and the proposers' valid partners are as follows ($\mathrm{best}(p)$ in bold).

Collecting everyone's $\mathrm{best}$ gives AX BW CY DZ — exactly the output of section 3.2. Each proposer takes its own favorite, and yet no two of them want the same partner. That is what the next theorem says.

Theorem (Gale–Shapley, 1962). In the output of proposer-proposing Gale–Shapley, every proposer $p$ is matched to $\mathrm{best}(p)$.

Proof. Suppose that during the run some proposer is rejected by a valid partner, and consider the first time this happens. Receiver $r$ rejects $p$, of whom it is a valid partner, in favor of $p'$ (so $p' \succ_r p$). Since $r$ is a valid partner of $p$, there is a stable matching $S$ that pairs $p$ with $r$. Let $r'$ be $p'$'s partner in $S$.

Because $p'$ is now proposing to $r$ (or being held by it), every receiver above $r$ on $p'$'s list has already rejected $p'$. Since we are looking at the first rejection by a valid partner, none of those rejections came from a valid partner of $p'$. But $r'$ is a valid partner of $p'$ (they are paired in $S$), so $r'$ is not above $r$: we have $r \succ_{p'} r'$.

Now in $S$, $p'$ prefers $r$ to its partner $r'$, and $r$ prefers $p'$ to its partner $p$. So $(p', r)$ blocks $S$, contradicting the stability of $S$. Hence no proposer is ever rejected by a valid partner. In particular $p$ is never rejected by $\mathrm{best}(p)$, so it ends with someone at least as good as $\mathrm{best}(p)$. On the other hand, the output is stable (section 4.4), so that final partner is a valid partner and cannot be better than $\mathrm{best}(p)$. Hence $p$ is matched with $\mathrm{best}(p)$. $\blacksquare$

This theorem explains every observation in section 3.4.

• The output is exactly «everyone matched with $\mathrm{best}(p)$», so it does not depend on the order of proposals.
• Each $p$ proposes exactly once to each receiver it ranks at or above $\mathrm{best}(p)$, so the set of proposals does not depend on the order either, and their number equals the sum of the proposers' final ranks: $2 + 2 + 2 + 1 = 7$ in the running example.

Roth (1982) also showed that no matching at all — stable or not — makes every proposer strictly better off than the proposer-optimal stable matching.

5.3 Receiver-pessimality

Theorem. In the same output, every receiver is matched to the valid partner it likes least.

Proof. Suppose that in the output $\mu_0$ receiver $r$ is matched with $p$, while in some stable matching $S$ it is matched with $p''$, whom it likes less ($p \succ_r p''$). In $S$, $p$'s partner is a valid partner other than $r$, so proposer-optimality gives $r = \mathrm{best}(p) \succ_p S(p)$. Then $(p, r)$ blocks $S$, a contradiction. $\blacksquare$

So being on the proposing side is an advantage in itself.

Intuitively, proposers start at the top and give up on a receiver only once it is out of reach in every stable matching — exactly what the proof in section 5.2 shows. Receivers can only choose among the offers that arrive; they have no way to court someone who never proposes. It is the logic of an ascending auction: bidders raise their bids only when outbid, so the auction stops at the lowest market-clearing prices — the outcome best for the buyers (Demange, Gale and Sotomayor, 1986).

In the US residency match it later came to light that the procedure used since 1952 produced the same result as a hospital-proposing algorithm; together with students' dissatisfaction, this led to the 1998 switch to an applicant-proposing design (the Roth–Peranson algorithm).

5.4 The lattice of stable matchings

The set of all stable matchings has the following structure.

Opposition of interests. For two stable matchings $\mu$ and $\mu'$, if every proposer likes $\mu$ at least as much as $\mu'$, then every receiver likes $\mu'$ at least as much as $\mu$.

A lattice. Given two stable matchings $\mu$ and $\mu'$, give each proposer the better of its two partners: the result is again a matching, and a stable one. Giving each proposer the worse of the two also yields a stable matching. With these two operations as join and meet, the stable matchings form a distributive lattice. Knuth (1976) credits this result to John Conway. The top of the lattice is proposer-optimal (the output of Gale–Shapley with the left proposing) and the bottom is receiver-optimal (the output with the right proposing).

The demo below checks all $4! = 24$ perfect matchings by brute force, keeps the stable ones and draws them ordered by «every left agent weakly prefers» (a Hasse diagram).

The running example has four stable matchings forming a diamond.

• Top: AX BW CY DZ (left rank sum 7, right 9)
• Middle: AX BY CW DZ (9 / 7) and AZ BW CY DX (9 / 6)
• Bottom: AZ BY CW DX (11 / 4)

The edge labels $\rho_1, \rho_2$ are operations called rotations. $\rho_1$ has B and C swap partners (B: W→Y, C: Y→W) and $\rho_2$ has A and D swap partners (A: X→Z, D: Z→X). The two are independent, so applying them in either order reaches the bottom, which is why the diagram is a diamond.

Set the demo's «Click to» control to «Pick two for join / meet» and click the two middle matchings one after the other. From AX BY CW DZ and AZ BW CY DX, giving each left agent the better of its two partners produces the top AX BW CY DZ, and giving it the worse produces the bottom AZ BY CW DX. Both are genuine one-to-one matchings, and both are stable.

Switch to «4×4 maximum (10)» to see a more complex lattice with 10 stable matchings and 12 edges. It is three diamonds stacked on top of each other. There are six rotations in three layers of two. The two rotations in a layer are independent, and both must be applied before the next layer becomes available. Exactly 10 sets of «already applied» rotations are allowed, and they correspond to the 10 stable matchings.

Ten is known to be the maximum for 4-by-4 instances (see the table in Thurber, 2002). In general the number of stable matchings can grow exponentially in $n$ (Irving and Leather (1986) construct instances with about $2.28^n$ stable matchings when $n$ is a power of 2), while it is also bounded above by $c^n$ (Karlin, Oveis Gharan and Weber, 2018). With uniformly random preferences, on the other hand, the expected number of stable matchings is only about $e^{-1} n \ln n$ (Pittel, 1989) — plugging $n = 100$ into the asymptotic formula gives about 170.

5.5 Rotations and «fair» stable matchings

A rotation, applied to a stable matching $\mu$, shifts a few proposers around a cycle, each moving to the partner of the next one. Every proposer that moves loses a little, and every receiver involved gains a little.

Irving and Leather (1986) showed that

• there are only $O(n^2)$ rotations in total, and every path from the top to the bottom applies each rotation exactly once (which is why opposite edges of the diamond carry the same $\rho$), and
• stable matchings correspond one-to-one with the sets of rotations applied (the closed subsets of a partial order on rotations).

This correspondence represents a possibly exponential number of stable matchings with a polynomial-size «graph of rotations». All rotations can be listed in $O(n^2)$ time (Gusfield, 1987), and the correspondence is a concrete instance of Birkhoff's representation theorem: every finite distributive lattice is the lattice of closed subsets of some partially ordered set.

With this representation one can also look for stable matchings other than the two extremes — though how hard that is depends heavily on the goal.

• Egalitarian: minimize the total rank over everyone. Polynomial time (Irving, Leather, Gusfield, 1987).
• Minimum regret: minimize the worst rank anybody gets. $O(n^2)$ (Gusfield, 1987).
• Sex-equal: minimize the difference between the two sides' rank sums. NP-hard (Kato, 1993).

The demo's panel shows which criteria the selected stable matching is best for. In the running example, the minimum total rank (15) is attained by AZ BW CY DX and the bottom AZ BY CW DX, while the smallest difference between the sides' rank sums (2) is attained by the top AX BW CY DZ and by AX BY CW DZ. All four tie on minimum regret (the worst rank anybody gets is 3), so that badge appears whichever node you select. Which matching to choose depends on «good for whom».

Section 1.4 showed that minimizing total rank does not guarantee stability, but total rank can still be minimized with stability as a constraint. The convex hull of the stable matchings (the stable marriage polytope) is described exactly by polynomially many linear inequalities — the assignment constraints plus one stability inequality per pair (Vande Vate, 1989). Every vertex of this polytope is a stable matching, so «minimize total rank among stable matchings» can also be solved by linear programming.

6. Can lying pay?

6.1 For proposers, honesty is best

Gale–Shapley runs on reported preferences, so the question is whether reporting false preferences can pay. A «report» here may reorder the list, and it may also be truncated: everyone below the cut is declared unacceptable — «I would rather stay unmatched than be matched with them». Stability then also requires that nobody be matched with someone they declared unacceptable (individual rationality, section 8.1).

Theorem (Dubins and Freedman, 1981; Roth, 1982). In proposer-proposing Gale–Shapley, reporting one's true preferences is optimal for every proposer no matter what the others report (a dominant strategy).

Dubins and Freedman also showed that no coalition of proposers, however large, can misreport so that every member strictly gains (their paper is titled «Machiavelli and the Gale–Shapley Algorithm»).

6.2 Receivers can gain by truncating

Receivers have no such guarantee. Try the next demo. It starts with a 3-by-3 example with receiver X selected.

In this example, when A–C propose, the result is AX BY CZ and X is matched with A, its 2nd choice. But if X shortens its list and reports «only B is acceptable», this happens:

1. A is rejected by X and proposes to Y; Y lets go of B and trades up to A.
2. B, now free, proposes to X, and X holds B.

The result is AY BX CZ, and X gets its true first choice, B (in the demo, set the length to 1). The exhaustive table shows that 3 of the 16 reports X could make produce this outcome. Cutting off the bottom of one's list without reordering it is called a truncation strategy. In «Ms. Machiavelli and the Stable Matching Problem» (1985), Gale and Sotomayor showed that if all receivers truncate just below their receiver-optimal partners, even proposer-proposing Gale–Shapley returns the receiver-optimal stable matching.

AY BX CZ, reached through X's lie, is the receiver-optimal stable matching under the true preferences. A receiver's truncation pushes the outcome toward the receivers' end of the lattice; here proposers A and B lose.

Whether a receiver can gain by lying depends only on how many valid partners it has. Combining this truncation argument with the result of Demange, Gale and Sotomayor (1987) — no lie gets you a partner better than your best valid partner under the true preferences — gives: with everyone else truthful, a receiver can gain by lying if and only if it has two or more valid partners. Truncating just below the best valid partner is enough, and nothing does better. The demo's «Outcome» panel lists the selected agent's valid partners and where to cut.

Switch «Who lies» to a proposer (A–C) in the demo: an exhaustive search finds no report that beats the truth (section 6.1).

Truncation is a gamble, though. Switch the demo to «Truncation backfires (3×3)». The only difference from the previous example is Y's preferences (B > A > C), and this market has a single stable matching, AX BY CZ. If X again reports «only B», A is rejected by Y as well and moves to Z, the result is AZ BY, and X, like C, ends up unmatched (set the length to 1 to see it). Truncation pays only if you know everyone else's preferences correctly.

6.3 No stable mechanism makes honesty best for everyone

The receivers' room to manipulate is less a flaw of Gale–Shapley than a property of stability itself.

Theorem (Roth, 1982). There is no mechanism that always returns a stable matching and makes truthful reporting a dominant strategy for all participants.

A 2-by-2 example is enough for the proof. Let A: Y > Z, B: Z > Y, Y: B > A, Z: A > B. There are two stable matchings, AY BZ (best for the left) and AZ BY (best for the right).

• If the mechanism picks AY BZ, let Y report «only B». Then AY becomes unacceptable to Y, AZ BY is the only stable matching, the mechanism has to pick it, and Y gets its true first choice B.
• If the mechanism picks AZ BY, let A report «only Y». By the same reasoning AY BZ becomes the only stable matching, and A gains.

Either way, somebody gains by lying. Check it with the demo's «Impossibility (2×2)» preset: it starts with A–B proposing and Y as the liar. After switching to «Y–Z propose», set «Who lies» to A (reporting «only Y» pays). The intuition: when there are several stable matchings, whichever one is chosen, the side that wanted the other end retains an incentive to lie. In real markets, though, this room to lie is usually small (section 7.4).

6.4 Under the Boston mechanism, honest reporting can backfire

Under the immediate acceptance of section 3.3 (the Boston mechanism), honesty is no longer safe, even for proposers. In the running example, B lost its 2nd choice W to A while being rejected by its 1st choice Z. Had B reported W as its first choice, W would have picked B over A in round 1. So under the Boston mechanism, truthfully listing a popular first choice can hurt you, and participants have to think about strategies such as «put a safe option first». Choose «Running example (4×4)» in the demo of section 6.2: it selects B under immediate acceptance, and a report with W first improves B from its true 4th choice to its 2nd. Switch the acceptance rule to DA and no report beats the truth for the same B.

Abdulkadiroğlu and Sönmez (2003) pointed out this problem and proposed deferred acceptance for school choice. Boston decided in 2005 to switch to deferred acceptance.

Japan's JRMP likewise tells participants to «enter every program you wish to train at, in the order you prefer them» and that «changing your first choice because a program is popular does not raise your chances of being matched». The same notes describe the matching as «checking first whether you can match with your first-choice program» — that is, applicants are the proposing side. The advice is the theorem of section 6.1 translated into operating instructions.

7. What happens in a random market

With uniformly random preferences, Gale–Shapley follows simple asymptotic laws. Check them in the next demo (for «100 trials» or «n ≤ 200», press «Run simulation»).

7.1 About $n \ln n$ proposals

With random preferences, the expected number of proposals is at most $n H_n$, where $H_n = 1 + 1/2 + \cdots + 1/n \approx \ln n$ (Wilson, 1972). That is far fewer than the worst case $n^2 - n + 1$: about 500 for $n = 100$. Since the number of proposals equals the sum of the proposers' final ranks, this also means the proposers' average rank is at most about $H_n \approx \ln n$.

Why $n H_n$? As section 4.2 showed, the run ends the moment the last receiver gets its first proposal. If proposers «forgot» who had rejected them and each time proposed to a uniformly random receiver, this would be exactly the coupon collector's problem — keep collecting random coupons until you have all $n$ kinds — whose expected number of draws is exactly $n H_n$. Real proposers never propose to the same receiver twice, so they need no more proposals than that.

7.2 Average ranks: about $\ln n$ for proposers, $n / \ln n$ for receivers

Pittel (1989) showed that in the proposer-optimal stable matching, the proposers' average rank is about $\ln n$ and the receivers' about $n / \ln n$. In the demo's «balanced (n vs n)» setting with $n = 100$, the left side's average rank is about 5 when the left proposes and about 21 when the right proposes (for reference, $\ln 100 \approx 4.6$ and $100 / \ln 100 \approx 21.7$). The wide gap between the two lines quantifies section 5.3's «proposing is an advantage». The line below the table shows that nearly 80% of the left side have different partners in the two extreme stable matchings: depending on which stable matching is chosen, most people's partners change. By section 6.2, this is also «the share of left agents who could gain by lying when the right side proposes».

7.3 One extra agent outweighs who proposes

Now switch to «right side +1». The two lines nearly coincide: even when the right side proposes, the left side's average rank stays around 5. The share of left agents with different partners drops to about 10%.

Ashlagi, Kanoria and Leshno (2017) showed that in a market that is even slightly unbalanced, in every stable matching the short side (here the left) gets an average rank of about $\ln n$ and the long side about $n / \ln n$, and the set of stable matchings effectively collapses to one. Which side is larger matters far more than which side proposes. Switch to «right side −1» and the left side does poorly whichever side proposes. The number of proposals also jumps when the (now longer) left side proposes.

This agrees with what was observed in practice. When the NRMP switched from hospital-proposing to applicant-proposing, the analysis of Roth and Peranson (1999) found that the effect on actual outcomes was very small. In a market filling about 20,000 positions a year, both the set of stable matchings and the room for strategic manipulation turned out to be «surprisingly small», and they point to a key reason: each applicant interviews for only a small fraction of the available positions (so rank-order lists are short). Real markets are not balanced, rank-order lists are short, and preferences are correlated, so the «width» of the set of stable matchings is narrow to begin with.

7.4 Short lists and unbalanced markets leave little room to manipulate

Receivers do have room to lie, as section 6 showed, but one reason Gale–Shapley remains in use regardless is that in many real markets there is almost no room to manipulate. Immorlica and Mahdian (2005) showed that when the proposers' lists are short (a constant number of randomly chosen entries), even with arbitrary preferences on the receiving side, the fraction of receivers who can gain by lying tends to 0 as $n \to \infty$. Kojima and Pathak (2009) extended this to many-to-one markets such as hospitals and residents.

The underlying reason is the fact from section 6.2 for one-to-one markets: only agents with two or more valid partners can gain by lying. In markets with short lists — or, as section 7.3 showed, in markets that are even slightly unbalanced — most agents have at most one valid partner. In the balanced market of section 7.2, where everyone ranks everyone, most agents have several valid partners, so size alone does not remove the room to manipulate.

8. The many-to-one extension and real institutions

8.1 Capacities

The title of Gale and Shapley's paper is «College Admissions and the Stability of Marriage»: its main subject was really college admissions. College $h$ has a quota $q_h$; each student attends one college, and a college admits at most $q_h$ students. More generally,

• lists may be incomplete: leaving someone off one's list means «I would rather stay unmatched than be matched with them» (unacceptable);
• the numbers of agents and seats need not match.

Stability is then defined by two conditions.

1. Nobody is matched with someone they find unacceptable (individual rationality).
2. There is no student $s$ and college $h$ such that $s$ prefers $h$ to its current assignment and $h$ either «has an empty seat and finds $s$ acceptable» or «prefers $s$ to one of its current students».

The algorithm hardly changes. Each college keeps the best applications it has received on a «waiting list», up to its quota, and rejects the rest. One can also reduce the problem to the one-to-one case by splitting college $h$ into $q_h$ single «seats».

8.2 Running a residency match

The next demo has residents A–F and hospitals X, Y, Z with two positions each. Lists are incomplete on both sides. Z plays the rural hospital: of the residents who list it (A, C, E), only C is on Z's own rank list.

The four rounds go as follows.

• In round 1, A applies to Z and D applies to Y, but neither appears on that hospital's rank list, so both are turned away at once.
• In round 2, A applies to Y, and Y bumps E, whom it had been holding, to take A.
• In round 3, the bumped E applies to its second choice Z and is turned away at once: E is not on Z's rank list.
• In round 4, E applies to X, and X bumps D. D has exhausted its list and ends up unmatched.

The result is AY BX CZ EX FY, with D unmatched.

8.3 The rural hospitals theorem

The demo's final panel also shows, in the «Hospitals propose (hospital-optimal)» row, the result when hospitals propose: AY BY CZ EX FX, in which B and F trade places. Yet D is unmatched in both, and the under-filled Z gets only C in both. The next theorem shows that this always holds.

Rural Hospitals Theorem (Roth, 1986). Across all stable matchings,

• the set of residents who are matched is the same,
• each hospital fills the same number of positions, and
• a hospital that does not fill its quota receives exactly the same set of residents.

The name comes from a US policy question: can residents be steered toward rural hospitals that struggle to fill positions, while keeping the match stable? The answer is no. Whichever stable matching is chosen, an under-filled hospital receives the same residents.

8.4 Hospitals' manipulation, and explaining outcomes with cutoffs

Many-to-one also introduces an asymmetry in strategy-proofness, the property that truthful reporting is optimal. When residents propose, honesty is still optimal for residents; but Roth (1985) showed that in many-to-one problems no stable mechanism makes honesty optimal for hospitals. Even when hospitals propose, a hospital may gain by manipulating its rank list.

A stable many-to-one matching can be explained by «cutoffs». For each hospital that is full, take as its cutoff the lowest-ranked resident it admitted (a hospital with a free seat has none). Then every resident is assigned to their favorite among the hospitals where they rank at or above the cutoff (or that have a free seat and find them acceptable) — otherwise there would be a blocking pair. «You did not get into X because X's last admitted resident ranks above you on X's list» — being able to explain outcomes this way matters for the transparency of an institution. Azevedo and Leshno (2016) developed this view into a supply-and-demand framework. The demo also shows each hospital's cutoff at every round. While a seat is free there is no cutoff; once a hospital is full, its cutoff rises only when more acceptable applications arrive than it has seats — excess demand — much as a price rises under excess demand.

The demo's final panel lists each hospital's cutoff and «why each resident missed the hospitals they prefer». D, for instance, is not on the list of its first choice Y, and at its second choice X it ranks 6th, below the cutoff B (5th), so it gets nothing. E ranks 5th at its first choice Y, below the cutoff F (4th), is not on the list of its second choice Z, and so lands at its third choice X.

8.5 Real institutions

• NRMP (the US residency match): started in 1952. In 1998 it switched to the applicant-proposing Roth–Peranson algorithm, which was designed to handle real-world complications such as «couples» — pairs of applicants (often spouses) who want positions in the same area. With couples a stable matching may not exist and deciding whether one does is NP-complete (Ronn, 1990), but in large markets with a small fraction of couples a stable matching exists with high probability (Kojima, Pathak and Roth, 2013).
• JRMP (Japan's residency match): introduced together with the new postgraduate clinical training system that began in 2004. The council lists among its features that «the matching algorithm is theoretically established and is made public» and that «no pairing arises that is not on the rank lists». Today the number of positions in each prefecture is also capped, to keep residents from concentrating in big cities. Yuichiro Kamada and Fuhito Kojima (2015) showed that running deferred acceptance after cutting each hospital's capacity in advance to respect such «regional caps» can produce inefficient and unstable outcomes, and proposed «flexible deferred acceptance», which shifts capacity flexibly within each cap.
• School choice: New York City high schools (from 2003) and Boston public schools (decided in 2005 to move away from the Boston mechanism). Schools have «priorities» (catchment area, siblings and so on) rather than preferences, and students with equal priority have to be ordered by lottery.
• Parcoursup (French university admissions): since 2018 it has run a form of deferred acceptance «executed by people». Students keep one of the offers they have received and trade up when a better one arrives.
• Systems design: Maggs and Sitaraman (2015) of Akamai describe formulating global load balancing — assigning groups of clients to server clusters — as a stable matching with capacities.

The 2012 Nobel Memorial Prize in Economic Sciences went to Shapley and Roth «for the theory of stable allocations and the practice of market design». Gale had died in 2008 and so was not among the laureates.

8.6 What stability costs: efficiency

In the marriage model with strict preferences, where both sides' preferences count, every stable matching is Pareto efficient: if some reassignment gave someone a partner they like better while hurting nobody, those two would form a blocking pair of the original matching. The problem arises when one side's «preferences» do not count as welfare.

In school choice, a school's «priorities» are not the school's own preferences but rules such as catchment areas or siblings. That raises a question: if some reassignment makes some students better off and no student worse off, shouldn't it take precedence? Consider the following example. Schools a, b and c each have one seat.

Student-proposing deferred acceptance gives «1a 2b 3c», so students 1 and 2 both get their second choice. If 1 and 2 swapped schools (1b 2a 3c), both would get their first choice and 3 would lose nothing. After the swap, however, 3 wants a more than c, and a ranks 3 above 2, so $(3, a)$ is a blocking pair (in school-choice language, «justified envy»). As long as stability is required, this improvement that hurts nobody cannot be made.

This does not contradict Roth (1982) in section 5.2: student 3 does not strictly gain. The proposer-optimal stable matching rules out improvements that make every proposer strictly better off, not improvements that help some and hurt nobody.

Switch to «DA, then 1 and 2 swap» and $(3, a)$ appears as a red dashed line (justified envy).

Abdulkadiroğlu and Sönmez (2003) also proposed another mechanism for school choice, «top trading cycles» (TTC) — David Gale's procedure, as reported by Shapley and Scarf (1974), carried over to school choice. Each student points to her favorite school with a free seat, each school points to its highest-priority remaining student, and seats are traded around the resulting cycles. It keeps strategy-proofness for students but trades stability for (student-side) Pareto efficiency; in this example it picks 1b 2a 3c. Step through the rounds in the demo's «TTC» view to watch seats trade around the cycle 1 → b → 2 → a → 1.

Kesten (2010) proposed efficiency-adjusted deferred acceptance (EADA). Starting from the DA outcome, it asks each student whose priority at some school does not help her own assignment — it only pushes others out — to consent to waiving it, and uses those waivers to improve other students' assignments. Consenting does not change the consenter's own assignment, and with full consent the outcome is Pareto efficient (at the cost of strategy-proofness for students). Which of stability, efficiency and strategy-proofness to put first is a value judgment each institution has to make.

9. Generalizations and hardness

Small changes to the basic problem can remove the guarantee that a stable matching exists, or make the problem computationally hard.

With ties, the three notions of stability differ in which pairs count as blocking. A matching is weakly stable if no pair strictly prefers each other, strongly stable if there is not even a pair where one strictly prefers and the other weakly prefers, and super-stable if there is not even a pair who both weakly prefer each other. The stricter the notion, the less existence is guaranteed.

An instance of the roommates problem with no stable matching appears in the original paper. Four people $\{a, b, c, d\}$: $a$ ranks $b > c > d$, $b$ ranks $c > a > d$, $c$ ranks $a > b > d$, so all three rank $d$ last. Whoever is paired with $d$ is the first choice of someone who is not paired with their own first choice, and those two block (for example, with $a$–$d$ and $b$–$c$, $c$ prefers $a$ to $b$ and $a$ prefers $c$ to $d$). Having two sides is the structure that guarantees a stable matching exists.

Existence can still be decided — and a stable matching found — quickly. Irving's (1985) algorithm has two phases. In phase 1 everyone both proposes and receives, deferred-acceptance style; whoever holds a proposal deletes everyone it likes less from its list (and itself from theirs). If someone's list becomes empty, there is no stable matching. In phase 2 it repeatedly finds a rotation in the shortened lists — a cycle in which each person shifts one place, much as in section 5.5 — and eliminates it, until every list has a single entry (a stable matching) or some list becomes empty (none exists). The whole run takes $O(n^2)$ time.

The same language of «structure» explains why couples break existence. The key to the many-to-one theory is that hospitals' preferences are «substitutable»: a hospital that wants a resident still wants her when some of the other candidates become unavailable. Under this condition deferred acceptance generalizes all the way to «matching with contracts», which can include terms such as wages, and existence and the lattice structure survive (Kelso and Crawford, 1982; Hatfield and Milgrom, 2005). A couple, however, brings a «complementary» preference onto the applicant side — two positions are worth something only together. The theory assumes that every agent who takes more than one position has substitutable preferences, so couples break that assumption, and with it the guarantee of existence.

Ties matter in practice. School priorities contain huge numbers of ties, and how ties are broken (one lottery for all schools or a separate lottery per school) affects efficiency and fairness. Simulations with New York City data, and the theory, favor a single common lottery (single tie-breaking) (Abdulkadiroğlu, Pathak and Roth, 2009). «Stable improvement cycles» have been proposed to win back, without giving up stability, the efficiency lost by breaking ties with a lottery (Erdil and Ergin, 2008) — but, as Abdulkadiroğlu and colleagues showed in 2009, that improvement cannot be made without harming students' incentives to report truthfully. Work by Japanese researchers in this area includes the studies by Kazuo Iwama, Shuichi Miyazaki and colleagues on the complexity and approximability of stable marriage with ties and incomplete lists (SMTI), and Kato's (1993) proof that sex-equal stable matching is NP-hard.

10. Implementing it

10.1 A Python implementation

Here is proposer-proposing Gale–Shapley, including support for incomplete lists.

from collections import deque
 
 
def gale_shapley(proposer_prefs, receiver_prefs):
    """Deferred acceptance with the proposers proposing.
 
    proposer_prefs[p]: receivers acceptable to p, best first
    receiver_prefs[r]: proposers acceptable to r, best first
    Returns match[p] = p's partner (or None).
    """
    n_p, n_r = len(proposer_prefs), len(receiver_prefs)
    # rank[r][p]: position of p in r's list (smaller is better); None if unacceptable
    rank = [[None] * n_p for _ in range(n_r)]
    for r, prefs in enumerate(receiver_prefs):
        for k, p in enumerate(prefs):
            rank[r][p] = k
 
    next_choice = [0] * n_p   # index of the next receiver p will propose to
    holding = [None] * n_r    # proposer that r is holding «tentatively»
    free = deque(range(n_p))  # proposers without a partner
 
    while free:
        p = free.popleft()
        if next_choice[p] == len(proposer_prefs[p]):
            continue  # list exhausted: p stays unmatched
        r = proposer_prefs[p][next_choice[p]]
        next_choice[p] += 1
        if rank[r][p] is None:
            free.append(p)  # r does not accept p
        elif holding[r] is None:
            holding[r] = p  # r is free: hold p tentatively
        elif rank[r][p] < rank[r][holding[r]]:
            free.append(holding[r])  # trade up: the old partner becomes free
            holding[r] = p
        else:
            free.append(p)  # r prefers its current partner: reject
 
    match = [None] * n_p
    for r, p in enumerate(holding):
        if p is not None:
            match[p] = r
    return match
 
 
# A..D = 0..3, W..Z = 0..3 (the running example)
P = [[0, 1, 3, 2], [3, 0, 2, 1], [3, 2, 0, 1], [3, 1, 2, 0]]
R = [[2, 1, 3, 0], [3, 1, 0, 2], [1, 2, 3, 0], [0, 3, 2, 1]]
print(gale_shapley(P, R))  # [1, 0, 2, 3] → AX BW CY DZ
print(gale_shapley(R, P))  # [2, 3, 1, 0] → WC XD YB ZA

Each iteration is $O(1)$ and the number of proposals never exceeds the total length of the proposers' lists. Because the rank table is a full $n_p \times n_r$ grid, though, the running time is linear in the input size only for complete lists. For short lists, keep each receiver's ranks in a dictionary, as blocking_pairs does in section 10.2, and the time is proportional to the total length of the lists.

10.2 How to test it

Matching algorithms are a natural fit for tests against a brute-force oracle. For $n \le 6$ or so, all $n!$ matchings can be examined, so with random inputs we can check, many times over, that

1. the output has no blocking pair (stability), and
2. the output is proposer-optimal among all stable matchings found by brute force.

import itertools
import random
 
 
def blocking_pairs(proposer_prefs, receiver_prefs, match):
    """Blocking pairs of match[p] = r (or None)."""
    partner_of = {r: p for p, r in enumerate(match) if r is not None}
    rank_r = [{p: k for k, p in enumerate(prefs)} for prefs in receiver_prefs]
    pairs = []
    for p, prefs in enumerate(proposer_prefs):
        for r in prefs:  # from p's favorite downwards
            if match[p] == r:
                break  # anything below the current partner cannot block
            if p not in rank_r[r]:
                continue  # r does not accept p
            q = partner_of.get(r)
            if q is None or rank_r[r][p] < rank_r[r][q]:
                pairs.append((p, r))
    return pairs
 
 
def stable_matchings(proposer_prefs, receiver_prefs):
    n = len(proposer_prefs)
    for perm in itertools.permutations(range(n)):
        if not blocking_pairs(proposer_prefs, receiver_prefs, list(perm)):
            yield list(perm)
 
 
def check(trials=300, n=5, seed=0):
    rng = random.Random(seed)
    for _ in range(trials):
        P = [rng.sample(range(n), n) for _ in range(n)]
        R = [rng.sample(range(n), n) for _ in range(n)]
        gs = gale_shapley(P, R)
        assert not blocking_pairs(P, R, gs)  # stable
        for m in stable_matchings(P, R):  # proposer-optimal
            assert all(P[p].index(gs[p]) <= P[p].index(m[p]) for p in range(n))
 
 
check()  # silence means every check passed

The TypeScript implementation behind the demos on this page (src/lib/stable-matching.ts) is tested the same way — against brute force or against the two extreme stable matchings — for properties such as «the result and the set of proposals do not depend on the order», «proposer-optimal and receiver-pessimal», «at most $n^2 - n + 1$ proposals», «no proposer gains from any report», «joins and meets are stable matchings» and «the rural hospitals theorem».

10.3 Practical notes

• How to break ties is a major design decision. The tie-breaking rule changes both the outcome and its efficiency, and the rule itself becomes a subject of fairness debates.
• Handle unacceptability explicitly. Never matching someone with a partner absent from their list (individual rationality) is part of stability.
• The result does not depend on the order of proposals, so implementation details (queue or stack, parallel or not) do not change the output. That is a big advantage for reproducibility, and for processing each round in parallel per receiver.
• Explainability. The cutoffs of section 8.4 explain to each individual «why this was the result».
• Choose deliberately which side proposes. The proposing side is favored, and only the proposing side gets the «honesty is best» guarantee — and in many-to-one markets only when the single-seat side (residents, students) proposes (section 8.4). Decide, in light of the institution's goals, whom it should protect.
• Do not cap the length of rank lists. With a cap, even deferred acceptance stops being strategy-proof: applicants must decide which options to include (Haeringer and Klijn, 2009). For years New York City's high-school match let students rank at most 12 programs (Abdulkadiroğlu, Pathak and Roth, 2005), counting each program within a school separately; the cap has since been lifted.
• Run it once from each side. If the results coincide, the stable matching is unique, and in a one-to-one market nobody can gain by lying while everyone else is truthful. If they differ, the agents whose partners change are exactly those with two or more valid partners, and those among them on the receiving side have room to truncate (section 6.2).
• Check the output and make it reproducible. blocking_pairs from section 10.2 runs in time proportional to the total length of the lists, so it can be used as a production assertion for one-to-one output. It assumes that nobody is matched to someone unacceptable, so check that first. For many-to-one output, rewrite it to test whether the institution «has a free seat» or the applicant «ranks above the lowest admitted». If ties are broken by lottery, record the random seed so that a third party can reproduce and verify the result.

• «It maximizes total happiness» — no; a total-maximizing matching can be unstable (section 1.4).
• «Processing order or parallelism changes the result» — no (sections 3.4 and 5.2).
• «The receiving side, which gets to choose, is better off» — the reverse: proposing is the advantage (section 5.3).
• «Under deferred acceptance nobody has a reason to lie» — only proposers are guaranteed that (sections 6.1–6.2).
• «Stable means efficient» — with strict preferences and both sides' welfare counted, a stable matching is Pareto efficient; but when only one side's welfare counts, as with students in school choice, an improvement that hurts no student can remain (section 8.6).
• «Stable means as many pairs as possible» — not with incomplete lists. Two mutually acceptable agents who are both unmatched would form a blocking pair, so a stable matching is maximal (no pair can be added) and therefore has at least half the maximum number of pairs. Moreover, every stable matching has the same number (section 8.3).

Summary

• Stability means having no blocking pair (two agents who prefer each other to their current partners); it is the condition under which nobody has an incentive to trade outside the system.
• The naive approach of fixing blocking pairs one at a time can cycle.
• Gale–Shapley (deferred acceptance) has proposers propose in order of preference while receivers hold the best proposal so far; it always returns a stable matching after at most $n^2 - n + 1$ proposals.
• The output does not depend on the order of proposals and is the best stable matching for proposers and the worst for receivers. The stable matchings form a distributive lattice that rotations represent compactly.
• Truthful reporting is a dominant strategy for proposers (and a coalition cannot make all its members gain). Receivers can gain by truncation, but only when they have two or more valid partners, and no stable mechanism makes honesty best for everyone. In markets with short lists or unequal sides, though, the room to manipulate almost disappears.
• In random markets proposers get an average rank of about $\ln n$ and receivers about $n / \ln n$ — but with just one extra agent on one side, the result is nearly the same whichever side proposes.
• The many-to-one extension is used in residency matches and school choice, and an under-filled hospital receives the same residents in every stable matching (the rural hospitals theorem). Outcomes can be explained to each individual with «cutoffs».
• When only one side's welfare counts (students in school choice), stability can conflict with efficiency, and alternatives such as TTC and EADA are also on the table.
• Generalizations such as ties, couples, roommates and three-sided matching can lose existence or become NP-hard.

References

Further reading. For a general audience, Roth's own Who Gets What — and Why: The New Economics of Matchmaking and Market Design (Houghton Mifflin Harcourt, 2015) is the natural entry point. The standard texts are Roth and Sotomayor (1990) for the theory, Gusfield and Irving (1989) for the structure of stable matchings and its algorithms, and D. F. Manlove's Algorithmics of Matching Under Preferences (World Scientific, 2013) for the variants and their complexity. Among algorithms textbooks, J. Kleinberg and É. Tardos's Algorithm Design (Addison-Wesley, 2005) opens its first chapter with this very problem.

• D. Gale, L. S. Shapley. College Admissions and the Stability of Marriage. The American Mathematical Monthly, 69(1):9–15, 1962.
• D. G. McVitie, L. B. Wilson. The stable marriage problem. Communications of the ACM, 14(7):486–490, 1971.
• L. B. Wilson. An analysis of the stable marriage assignment algorithm. BIT, 12(4):569–575, 1972.
• L. Shapley, H. Scarf. On cores and indivisibility. Journal of Mathematical Economics, 1(1):23–37, 1974.
• D. E. Knuth. Mariages stables et leurs relations avec d'autres problèmes combinatoires. Les Presses de l'Université de Montréal, 1976. (English translation: Stable Marriage and Its Relation to Other Combinatorial Problems, AMS, 1997.)
• L. E. Dubins, D. A. Freedman. Machiavelli and the Gale-Shapley Algorithm. The American Mathematical Monthly, 88(7):485–494, 1981.
• A. E. Roth. The Economics of Matching: Stability and Incentives. Mathematics of Operations Research, 7(4):617–628, 1982.
• A. S. Kelso, V. P. Crawford. Job Matching, Coalition Formation, and Gross Substitutes. Econometrica, 50(6):1483–1504, 1982.
• A. E. Roth. The Evolution of the Labor Market for Medical Interns and Residents: A Case Study in Game Theory. Journal of Political Economy, 92(6):991–1016, 1984.
• A. E. Roth. The college admissions problem is not equivalent to the marriage problem. Journal of Economic Theory, 36(2):277–288, 1985.
• D. Gale, M. Sotomayor. Ms. Machiavelli and the Stable Matching Problem. The American Mathematical Monthly, 92(4):261–268, 1985.
• D. Gale, M. Sotomayor. Some remarks on the stable matching problem. Discrete Applied Mathematics, 11(3):223–232, 1985.
• R. W. Irving. An efficient algorithm for the "stable roommates" problem. Journal of Algorithms, 6(4):577–595, 1985.
• A. E. Roth. On the Allocation of Residents to Rural Hospitals: A General Property of Two-Sided Matching Markets. Econometrica, 54(2):425–427, 1986.
• R. W. Irving, P. Leather. The Complexity of Counting Stable Marriages. SIAM Journal on Computing, 15(3):655–667, 1986.
• G. Demange, D. Gale, M. Sotomayor. Multi-Item Auctions. Journal of Political Economy, 94(4):863–872, 1986.
• R. W. Irving, P. Leather, D. Gusfield. An efficient algorithm for the "optimal" stable marriage. Journal of the ACM, 34(3):532–543, 1987.
• D. Gusfield. Three Fast Algorithms for Four Problems in Stable Marriage. SIAM Journal on Computing, 16(1):111–128, 1987.
• G. Demange, D. Gale, M. Sotomayor. A further note on the stable matching problem. Discrete Applied Mathematics, 16(3):217–222, 1987.
• B. Pittel. The Average Number of Stable Matchings. SIAM Journal on Discrete Mathematics, 2(4):530–549, 1989.
• J. H. Vande Vate. Linear programming brings marital bliss. Operations Research Letters, 8(3):147–153, 1989.
• D. Gusfield, R. W. Irving. The Stable Marriage Problem: Structure and Algorithms. MIT Press, 1989.
• A. E. Roth, J. H. Vande Vate. Random Paths to Stability in Two-Sided Matching. Econometrica, 58(6):1475–1480, 1990.
• A. E. Roth, M. Sotomayor. Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis. Cambridge University Press, 1990.
• C. Ng, D. S. Hirschberg. Lower Bounds for the Stable Marriage Problem and Its Variants. SIAM Journal on Computing, 19(1):71–77, 1990.
• E. Ronn. NP-complete stable matching problems. Journal of Algorithms, 11(2):285–304, 1990.
• A. E. Roth. A Natural Experiment in the Organization of Entry-Level Labor Markets: Regional Markets for New Physicians and Surgeons in the United Kingdom. American Economic Review, 81(3):415–440, 1991.
• C. Ng, D. S. Hirschberg. Three-Dimensional Stable Matching Problems. SIAM Journal on Discrete Mathematics, 4(2):245–252, 1991.
• A. Kato. Complexity of the sex-equal stable marriage problem. Japan Journal of Industrial and Applied Mathematics, 10(1):1–19, 1993.
• R. W. Irving. Stable marriage and indifference. Discrete Applied Mathematics, 48(3):261–272, 1994.
• A. E. Roth, E. Peranson. The Redesign of the Matching Market for American Physicians: Some Engineering Aspects of Economic Design. American Economic Review, 89(4):748–780, 1999.
• K. Iwama, D. F. Manlove, S. Miyazaki, Y. Morita. Stable Marriage with Incomplete Lists and Ties. ICALP 1999, LNCS 1644, 443–452, 1999.
• D. F. Manlove, R. W. Irving, K. Iwama, S. Miyazaki, Y. Morita. Hard variants of stable marriage. Theoretical Computer Science, 276(1–2):261–279, 2002.
• E. G. Thurber. Concerning the maximum number of stable matchings in the stable marriage problem. Discrete Mathematics, 248(1–3):195–219, 2002.
• A. Abdulkadiroğlu, T. Sönmez. School Choice: A Mechanism Design Approach. American Economic Review, 93(3):729–747, 2003.
• A. Abdulkadiroğlu, P. A. Pathak, A. E. Roth. The New York City High School Match. American Economic Review, 95(2):364–367, 2005.
• A. Abdulkadiroğlu, P. A. Pathak, A. E. Roth, T. Sönmez. The Boston Public School Match. American Economic Review, 95(2):368–371, 2005.
• N. Immorlica, M. Mahdian. Marriage, Honesty, and Stability. Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 53–62, 2005.
• J. W. Hatfield, P. R. Milgrom. Matching with Contracts. American Economic Review, 95(4):913–935, 2005.
• A. Erdil, H. Ergin. What's the Matter with Tie-Breaking? Improving Efficiency in School Choice. American Economic Review, 98(3):669–689, 2008.
• F. Kojima, P. A. Pathak. Incentives and Stability in Large Two-Sided Matching Markets. American Economic Review, 99(3):608–627, 2009.
• A. Abdulkadiroğlu, P. A. Pathak, A. E. Roth. Strategy-Proofness versus Efficiency in Matching with Indifferences: Redesigning the NYC High School Match. American Economic Review, 99(5):1954–1978, 2009.
• G. Haeringer, F. Klijn. Constrained school choice. Journal of Economic Theory, 144(5):1921–1947, 2009.
• O. Kesten. School Choice with Consent. The Quarterly Journal of Economics, 125(3):1297–1348, 2010.
• H. Ackermann, P. W. Goldberg, V. S. Mirrokni, H. Röglin, B. Vöcking. Uncoordinated Two-Sided Matching Markets. SIAM Journal on Computing, 40(1):92–106, 2011.
• F. Kojima, P. A. Pathak, A. E. Roth. Matching with Couples: Stability and Incentives in Large Markets. The Quarterly Journal of Economics, 128(4):1585–1632, 2013.
• B. M. Maggs, R. K. Sitaraman. Algorithmic Nuggets in Content Delivery. ACM SIGCOMM Computer Communication Review, 45(3):52–66, 2015.
• Y. Kamada, F. Kojima. Efficient Matching under Distributional Constraints: Theory and Applications. American Economic Review, 105(1):67–99, 2015.
• E. M. Azevedo, J. D. Leshno. A Supply and Demand Framework for Two-Sided Matching Markets. Journal of Political Economy, 124(5):1235–1268, 2016.
• I. Ashlagi, Y. Kanoria, J. D. Leshno. Unbalanced Random Matching Markets: The Stark Effect of Competition. Journal of Political Economy, 125(1):69–98, 2017.
• A. R. Karlin, S. Oveis Gharan, R. Weber. A simply exponential upper bound on the maximum number of stable matchings. Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC), 920–925, 2018.
• Y. A. Gonczarowski, N. Nisan, R. Ostrovsky, W. Rosenbaum. A stable marriage requires communication. Games and Economic Behavior, 118:626–647, 2019.
• Japan Residency Matching Program. Features of the match and notes for participants (in Japanese).
• Wikipedia. Gale–Shapley algorithm (on Parcoursup).