Stable Matching in Two Dimensions: An Algorithmic Exploration

What is Stable Matching?

Stable matching refers to an algorithmic process that pairs elements from two distinct sets based on preferences, ensuring no pair would prefer to be matched with another element outside of the current pairing. This concept was first introduced by David Gale and Lloyd Shapley in 1962.

The most well-known stable matching algorithm is the deferred acceptance algorithm, which guarantees a stable outcome for all participants.

How Does the Algorithm Work?

In the context of the simulation, proposers (one set) and receivers (another set) have ranked preferences over each other. The algorithm proceeds in rounds where proposers make offers to their top choice, and receivers either accept or reject based on their own preference lists.

If a receiver accepts an offer, any previous offer is broken, and the proposer moves on to its next preference. This process continues until all pairs are stable.

Why Does It Matter?

Stable matching algorithms have numerous practical applications, such as college admissions, organ transplants, and even job assignments in the labor market.

The algorithm ensures that no two parties would prefer to be matched with each other over their current partners, which is crucial for maintaining stability and fairness.

Real-World Examples

In college admissions, stable matching algorithms help match students to colleges based on mutual preferences, ensuring a fair outcome.

For the National Resident Matching Program (NRMP), doctors are matched with residency programs in hospitals, using a similar algorithm to ensure that both parties are satisfied.

Frequently asked questions

Try it live

Everything above runs in your browser — open Stable Matching (2D) and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.