STABLE MATCHING · GALE-SHAPLEY · DEFERRED ACCEPTANCE · CAPACITIES · EVERY STABLE MATCHING · BLOCKING PAIRS · RUNS IN YOUR BROWSER · NOTHING UPLOADED

Who should be matched with whom, so nobody wants to swap?

Residents and hospitals, students and schools, mentees and mentors, volunteers and shifts, reviewers and papers: both sides rank each other, and you need a matching that holds. This tool runs deferred acceptance (Gale & Shapley 1962) with capacities and either side proposing, lists every stable matching (McVitie & Wilson 1971) with the fairest compromises between the two sides, and finds the blocking pairs in a matching you already have.

Nothing you enter leaves this browser tab. Arithmetic on the lists you give, not legal or professional advice.

Both sides' lists

Example: the cyclic 3 x 3, where the side that proposes wins

Three men and three women whose lists go round in a circle: x likes A best, A likes y best, y likes B best, and so on. Gale and Shapley (1962) used an instance of this kind to show a market can have more than one stable matching. Load it: there are three. When the men propose each gets his first choice and each woman her third; when the women propose it is the reverse; and the middle one gives everyone their second choice. All three are stable, so stability alone does not say which is fair. That choice, between the two sides, is what the egalitarian, minimum-regret and balanced picks make explicit.

Questions

What is a stable matching?

A matching of applicants to places is stable when no applicant and place would both rather have each other than what they got. If such a pair exists (a blocking pair), they have a reason to break the match and go round it, which is how matching markets unravel. Gale and Shapley (1962) proved a stable matching always exists and gave deferred acceptance, the algorithm that finds one.

Which side should propose?

The proposing side gets its best stable outcome: when applicants propose, every applicant gets the best partner it has in any stable matching, and every programme gets its worst. The proposing side can also never gain by ranking dishonestly (Roth 1982; Dubins and Freedman 1981), but the receiving side sometimes can, and no stable rule protects both. So choose the proposing side for whoever most needs to be able to rank honestly, usually the applicants.

Is this how the medical residency match works?

The US National Resident Matching Program has used an applicant-proposing version of deferred acceptance since 1998, designed by Roth and Peranson (1999), with extra rules for couples who must match near each other. This tool does not handle couples or those extra rules, and it is not affiliated with any matching programme. Use it to understand, teach or run a small match of your own.

Why are the same people left out in every stable matching?

The rural hospitals theorem (Roth 1986) says every stable matching places the same applicants, fills each programme to the same number, and gives an under-filled programme exactly the same people. So no stable rule can help an applicant left out or a programme left short; only changing the lists (or the number of places) can. The tool checks this on every result.

What do egalitarian, minimum regret and balanced mean?

When there are several stable matchings the tool lists them all and picks three compromises between the two sides. Egalitarian has the smallest total rank over everyone on both sides (Irving, Leather and Gusfield 1987). Minimum regret makes the worst-off person as well off as possible (Gusfield 1987). Balanced makes the two sides' total ranks as close as possible. Rank 1 means first choice.

Can I check a matching I already made by hand?

Yes. Paste it in the check box as one line per applicant, such as ana: city, with a dash for no place. The tool lists every blocking pair and says why each pair would rather be together, plus any placement the lists do not allow or any programme given more people than it has places.

Is my data uploaded anywhere?

No. Every matching is computed by JavaScript in this browser tab. There are no accounts, cookies or analytics vendors.

Method and citation

Deferred acceptance (Gale & Shapley 1962). Each free member of the proposing side asks the next one on its list; each receiver holds its best offers up to its capacity and turns down the rest. Nothing is final until nobody free has anyone left to ask. A pair can match only if each lists the other; a one-sided listing is dropped with a note.

Every stable matching (McVitie & Wilson 1971). Each programme with c places becomes c seats that every applicant ranks one after another, which has the same stable matchings (Gusfield & Irving 1989). From the applicant-optimal matching, the search frees one applicant at a time, lets its partner accept only someone she prefers, and continues the proposals; when that chain ends with the partner taking a better offer, the result is another stable matching and the search continues from it. A chain that would displace an earlier applicant, run someone off their list, or fill a seat that was empty is abandoned. The listing stops at the limit you set (at most 5,000) and says when it did.

Choosing among them. Egalitarian: smallest total rank (Irving, Leather & Gusfield 1987). Minimum regret: smallest worst rank (Gusfield 1987). Balanced: the two sides' totals as close as possible. All three are picked from the full listing, so they are exact only when it finished.

Checked against the Python matching package 1.4.3 (Wilde, Knight & Gillard 2020) on 250 random instances of up to 30 applicants and 12 programmes, both sides proposing, with exact agreement; and against a brute-force search over every possible matching on 1,000 small random instances, with exactly the same set of stable matchings each time. Implemented from the papers; no third-party code was ported.

@article{gale1962college, author={Gale, David and Shapley, Lloyd S.}, title={College Admissions and the Stability of Marriage}, journal={The American Mathematical Monthly}, volume={69}, number={1}, pages={9--15}, year={1962}, doi={10.1080/00029890.1962.11989827}}
@article{mcvitie1971stable, author={McVitie, D. G. and Wilson, L. B.}, title={The stable marriage problem}, journal={Communications of the ACM}, volume={14}, number={7}, pages={486--490}, year={1971}, doi={10.1145/362619.362631}}
@article{roth1984evolution, author={Roth, Alvin E.}, title={The Evolution of the Labor Market for Medical Interns and Residents: A Case Study in Game Theory}, journal={Journal of Political Economy}, volume={92}, number={6}, pages={991--1016}, year={1984}, doi={10.1086/261272}}
@article{roth1986allocation, author={Roth, Alvin E.}, title={On the Allocation of Residents to Rural Hospitals: A General Property of Two-Sided Matching Markets}, journal={Econometrica}, volume={54}, number={2}, pages={425--427}, year={1986}, doi={10.2307/1913160}}
@article{roth1982economics, author={Roth, Alvin E.}, title={The Economics of Matching: Stability and Incentives}, journal={Mathematics of Operations Research}, volume={7}, number={4}, pages={617--628}, year={1982}, doi={10.1287/moor.7.4.617}}
@article{dubins1981machiavelli, author={Dubins, Lester E. and Freedman, David A.}, title={Machiavelli and the Gale-Shapley Algorithm}, journal={The American Mathematical Monthly}, volume={88}, number={7}, pages={485--494}, year={1981}, doi={10.1080/00029890.1981.11995301}}
@article{irving1987efficient, author={Irving, Robert W. and Leather, Paul and Gusfield, Dan}, title={An efficient algorithm for the ``optimal'' stable marriage}, journal={Journal of the ACM}, volume={34}, number={3}, pages={532--543}, year={1987}, doi={10.1145/28869.28871}}
@article{gusfield1987three, author={Gusfield, Dan}, title={Three Fast Algorithms for Four Problems in Stable Marriage}, journal={SIAM Journal on Computing}, volume={16}, number={1}, pages={111--128}, year={1987}, doi={10.1137/0216010}}
@book{gusfield1989stable, author={Gusfield, Dan and Irving, Robert W.}, title={The Stable Marriage Problem: Structure and Algorithms}, publisher={MIT Press}, year={1989}}
@article{roth1999redesign, author={Roth, Alvin E. and Peranson, Elliott}, title={The Redesign of the Matching Market for American Physicians: Some Engineering Aspects of Economic Design}, journal={American Economic Review}, volume={89}, number={4}, pages={748--780}, year={1999}, doi={10.1257/aer.89.4.748}}

Limits: up to 2,000 members in all; the listing of stable matchings stops at 5,000. Strict rankings only (no ties), the second side may have several places, the first side one each. Couples, quotas, ties and many-to-many matching are not handled. A stable matching is one definition of a good outcome; a real admissions, hiring or placement process has rules of its own.