Gale-Shapley Matching Calculator

Stable matchings from preference lists, step by step.

  • Both optimal sides
  • Blocking pairs
  • Step by step
Two short curved rows of soft clay beads on a round clay stool, with some beads touching in pairs, in soft daylight.

The guide

Stable is not fair: who gets their first choice in a matching made by proposals

A matching is stable when nobody has a better offer that wants them back. Deferred acceptance always finds one, and the side that proposes does best.

  • 1962 year Gale and Shapley published the algorithm
  • 4 proposals either side proposing, in the four-pair worked example
  • 3 stable matchings in the three-by-three example found in the sources
  • 7 proposals the most seen over all 46,656 instances of 3 pairs
  • 14 against 7 proposals in the six-pair example, side A then side B proposing
Read the full guide Fold the guide 7 min · 12 sources

Take two groups of equal size, say applicants and employers, and let each member rank everyone on the other side. Now pair them off. The pairing is unstable if one applicant and one employer would each rather have the other than the partner they were given. That single test is the whole idea of stability. It says nothing about who is happy, only about who can walk out of the arrangement with a willing partner. Sometimes a matching can be stable and leave half the room with their last choice.

What stable means, and what it does not

The Wikipedia article on the stable matching problem states it in two lines. A matching is not stable when some element A of the first set prefers an element B of the second set to its own partner, and B also prefers A to its own partner. Stable means no such pair exists.

Notice what the test leaves out. It does not ask for the most total happiness, or for the fewest unlucky people, or for anything equal between the sides. A stable matching can be lopsided, and often is.

The article gives a small instance with three members, A, B and C, on one side and three, X, Y and Z, on the other. A ranks Y, then X, then Z, and so on around the table. That instance has 3 stable matchings: the first side all get their first choice, or everyone gets a second choice, or the other side all get their first choice. All three pass the test, and none is the fair one by any measure other than the test itself.

Deferred acceptance, round by round

David Gale and Lloyd Shapley published their procedure in 1962 in The American Mathematical Monthly. It is also called the deferred acceptance or propose-and-reject algorithm, and according to the Wikipedia article on it, essentially the same method had been used by the National Resident Matching Program since 1952.

One side proposes and the other side decides. In each round every free proposer offers to the next name on its list. A receiver who is free says yes for now. A receiver who already holds an offer compares the two and keeps the one it prefers. The word deferred matters: a yes is only a hold, and the stable matching article describes the right to trade up, dropping the earlier partner for a better one.

The rounds stop when nobody is free. The article proves two things about the result: everyone ends up matched, and no pair is blocking. If a proposer reached a receiver, that receiver only turned it down for someone better. If a proposer never reached a receiver, it had already found a partner it likes at least as much.

Take the four-pair example loaded on the page. Both sides rank the other in a pattern with four stable matchings. With side A proposing, each member proposes once and is accepted. The result pairs A1 with B1, A2 with B2, A3 with B3 and A4 with B4 in 4 proposals. With side B proposing, the result is A1 with B2, A2 with B1, A3 with B4 and A4 with B3, also in 4 proposals. A brute-force search finds exactly four stable matchings, and those two are at its ends.

A busier case is on the page as well: six pairs from seed 58. Side A proposing needs 14 proposals in 6 rounds, with 3 trade-ups and 5 rejections. Side B proposing needs 7, so 14 against 7 on the same lists. A4 alone goes down its list four places before B1 takes it. With side B proposing, the same lists take only 2 rounds. Reproduce either run with the button for six pairs with trade-ups.

Why the proposers win

The Wikipedia article states the result without hedging. The version in which one side proposes always yields the same stable matching, whatever the order of proposals, and that matching is best for every member of the proposing side and worst for every member of the other side among all stable matchings.

Run the algorithm the other way round and you get the opposite end. The article calls the two results the top and the bottom elements of the lattice of stable matchings. The stable matching article adds that the whole family of solutions forms a finite distributive lattice, with the two runs at its ends.

Seed 58 shows the effect. The side A run gives side A a place sum of 14, counting 1 for a first choice, and side B a sum of 13. The side B run gives side A a sum of 22 and side B a sum of 7, which is one above the least possible, 6, the sum when every member has a first choice. Two other stable matchings sit between them.

The Gale-Shapley article notes the incentive side of this. A proposer cannot gain by misreporting its list, while a receiver may be able to. Who proposes is therefore not a detail. It is the choice that decides who gets the better end of every stable outcome.

Counting the work

How long can the algorithm run? Each proposer goes down its list at most once, and a list has n names, so there can be at most n squared proposals. The Wikipedia article says the whole procedure runs in time quadratic in the number of participants.

The count of proposals has a tidy form. A proposer proposes down its list exactly as far as its final partner, so the total is the sum of the places of the final partners of the proposing side. The page checks that identity on every run, and so does the independent program.

What about the worst case? Over every one of the 46,656 instances of 3 pairs, the largest count is 7 proposals. The same exhaustive search over 2 pairs gives 3. Both equal n squared minus n plus 1, but that is two measurements, not a proven formula, and this page does not claim it.

Random instances sit well below the bound. On 200 seeded instances of 50 pairs the mean is 202.07 proposals with this page’s generator and 210.32 with Python’s own, against a bound of 2,500. The product of n and the harmonic number, 224.96, is only a point of comparison. A different random generator gives a different sample, so these numbers drift by a few percent.

The number of stable matchings also grows slowly on average. The stable matching article says that for a uniformly random instance it is asymptotically e to the minus one times n natural log n, and that counting the stable matchings of a given instance is #P-complete. For 6 pairs, 24 of 40 seeded instances have more than one stable matching with this page’s generator, and 21 of 40 with Python’s.

What the page checks, and what it leaves out

The page tests every pair for blocking. For up to 9 pairs it also tries every permutation, 362,880 at most, and keeps the stable ones, so the best-for-proposers and worst-for-receivers statements are checked against the full list instead of being repeated from a source.

That search runs in a web worker, which MDN describes as a background thread that lets laborious processing happen while the main thread stays free. The independent reference is a Python 3.13 program that rebuilds the seeded instances, runs its own queue-based version of the algorithm in a different order, and lists stable matchings with itertools.permutations. It agrees on every instance.

A negative control keeps the checker honest. A routine in which a receiver keeps its first proposer and never trades up is run on 200 seeded instances of 5 pairs. This page’s checker names a blocking pair in 175 of them, and Python’s generator gives 158. Without trade-ups, the algorithm stops being an algorithm for stability.

The rest is care with the browser. The board is painted with rounded rectangles through roundRect, the picture is encoded on demand with toBlob, the 3D view skips work while it is off screen or the tab is hidden, using the Intersection Observer and Page Visibility APIs, and each step is timed with performance measures. The settings link lives in the hash of the address and the copy button writes text to the clipboard. The CSV follows the quoting of RFC 4180, with a leading apostrophe on any cell that starts like a formula.

Some things are left out on purpose. The page does not handle many-to-one matching such as colleges with quotas, ties in a list, incomplete lists, or couples who must be placed together. The Wikipedia article notes that Gale and Shapley treated quotas and incomplete lists in their original work, and the stable matching article says adding couples makes the problem NP-complete. Those cases need other tools.

One last caution about the language. The stable marriage story is a metaphor, and the Wikipedia article reports that it has been criticised as sexist and unrealistic. This page calls the groups side A and side B, and the same method places graduates in hospitals and applicants in schools.

Sources

Every source consulted for this guide. Links checked November 11, 2026.

  1. Gale-Shapley algorithm - Wikipedia Wikipedia (CC BY-SA 4.0)
  2. Stable matching problem - Wikipedia Wikipedia (CC BY-SA 4.0)
  3. Web Workers API - Web APIs | MDN MDN Web Docs (CC BY-SA 2.5 or later)
  4. Intersection Observer API - Web APIs | MDN MDN Web Docs (CC BY-SA 2.5 or later)
  5. Page Visibility API - Web APIs | MDN MDN Web Docs (CC BY-SA 2.5 or later)
  6. CanvasRenderingContext2D: roundRect() method - Web APIs | MDN MDN Web Docs (CC BY-SA 2.5 or later)
  7. HTMLCanvasElement: toBlob() method - Web APIs | MDN MDN Web Docs (CC BY-SA 2.5 or later)
  8. Performance: measure() method - Web APIs | MDN MDN Web Docs (CC BY-SA 2.5 or later)
  9. Location: hash property - Web APIs | MDN MDN Web Docs (CC BY-SA 2.5 or later)
  10. Clipboard: writeText() method - Web APIs | MDN MDN Web Docs (CC BY-SA 2.5 or later)
  11. itertools - Functions creating iterators for efficient looping - Python 3.13 documentation Python Software Foundation (PSF License)
  12. RFC 4180: Common Format and MIME Type for Comma-Separated Values (CSV) Files IETF (Internet Society)