The Gale-Shapley Algorithm and the Stable Matching Problem

This article explores the Gale-Shapley algorithm, a groundbreaking mathematical solution to the stable matching problem. It provides a clear breakdown of how this step-by-step process pairs two distinct groups based on mutual preferences, eliminating chaos in complex markets. Specifically, this piece examines the mechanics of the algorithm and how it guarantees optimal placements for medical school graduates seeking residencies and facilitates life-saving organ exchanges between incompatible donors and recipients.

Understanding the Stable Matching Problem

In mathematics and economics, the stable matching problem asks how to pair two equally sized groups of participants—who each have ranked preferences for the other group—so that the resulting pairs are "stable."

A match is considered unstable if there is at least one participant from Group A and one from Group B who are not matched together, but both prefer each other over their current assigned partners. In the real world, this instability leads to participants breaking their agreements to pair up with each other instead, causing the system to collapse.

In 1962, mathematicians David Gale and Lloyd Shapley proved that regardless of the number of participants or how conflicting their preferences are, a stable match is always mathematically possible.

How the Gale-Shapley Algorithm Works

To solve the stable matching problem, Gale and Shapley developed an iterative process known as the deferred acceptance algorithm. The mathematics rely on asymmetry: one group acts as the "proposers" and the other acts as the "reviewers."

The algorithm runs in rounds until everyone is matched:

  1. Round One Proposals: Every unmatched proposer in Group A makes an offer to their absolute top choice in Group B.
  2. Tentative Acceptance: Each reviewer in Group B looks at all the offers they received. They tell the proposer they like best to "wait" (a tentative acceptance) and permanently reject all other offers.
  3. Subsequent Proposals: In the next round, any proposer who was rejected crosses that reviewer off their list and proposes to their next highest choice.
  4. Trading Up: Reviewers in Group B compare the new proposals to the person they currently have on hold. If they prefer a new proposer, they reject the old one and put the new one on hold. If not, they reject the new proposer.
  5. Termination: The process repeats until no rejections are made. At this point, all tentative matches become final.

Mathematically, this guarantees a stable outcome. A proposer starts at the top of their list and only moves down when rejected. Therefore, if a proposer prefers a different reviewer over their final match, that reviewer has already rejected them for someone better. No mutually beneficial side-deals can exist.

Solving Medical Residency Placements

Before the 1950s, the market for pairing graduating medical students with hospital residency programs was failing. Hospitals competed fiercely for top students by making job offers earlier and earlier—sometimes two years before a student graduated. Students were forced to accept or reject offers blindly, and hospitals faced last-minute cancellations when students received better offers elsewhere.

To stop this chaos, the National Resident Matching Program (NRMP) implemented a system based on the Gale-Shapley algorithm, later refined by economist Alvin Roth.

Today, the process works seamlessly:

  • Medical students interview at various hospitals and submit a ranked list of their preferred residency programs to a central clearinghouse.
  • Hospitals submit a ranked list of the students they interviewed.
  • The computer runs the Gale-Shapley algorithm, with students acting as the proposers and hospitals acting as the reviewers.

Because the algorithm guarantees stability, no student can find a hospital that prefers them over its assigned residents, and no hospital can poach a student who would rather be there than at their assigned hospital. The algorithm eliminates the need for strategic manipulation, allowing both students and hospitals to rank their true preferences honestly.

Facilitating Life-Saving Organ Donations

While the original Gale-Shapley algorithm was designed for two-sided markets (where money or contracts are involved), its mathematical framework was expanded by Lloyd Shapley and Alvin Roth to operate in markets where monetary transactions are illegal, such as human organ transplants.

Patients needing a kidney transplant often have a friend or relative willing to donate. However, the donor and recipient frequently have incompatible blood or tissue types. Previously, that donor would simply be turned away, and the patient would remain on a waitlist.

Using the mathematical principles of stable matching, economists created Kidney Exchange Programs. In this variation, incompatible donor-recipient pairs are entered into a central database. Compatibility and medical urgency serve as the "preferences."

The algorithm searches for stable cycles of exchange:

  • Two-Way Swap: Donor A is incompatible with Recipient A, and Donor B is incompatible with Recipient B. However, the algorithm finds that Donor A is a biological match for Recipient B, and Donor B is a match for Recipient A.
  • Never-Ending Chains: A single non-directed donor (someone who donates a kidney out of altruism without a paired recipient) triggers a chain. Their kidney goes to Recipient A, whose incompatible Donor A gives a kidney to Recipient B, whose incompatible Donor B gives to Recipient C, and so on.

By applying the rules of stable matching, the algorithm ensures that no incompatible pair is matched into a cycle where a better biological match was available and willing elsewhere in the pool. These mathematical matches happen simultaneously in operating rooms across the country, resulting in thousands of life-saving transplants that would otherwise never occur.