What is the stable marriage problem?

It's the problem of matching members of two equal-sized groups, each with ranked preferences over the other group, so that no two people who aren't matched to each other would both prefer to be — a 'stable' matching with no incentive to defect.

How does the Gale-Shapley algorithm work?

Unmatched proposers repeatedly propose to their most-preferred reviewer they haven't tried yet; each reviewer holds onto their best offer received so far and rejects worse ones, even discarding an earlier match if a better proposer comes along, until every proposer is matched.

Does a stable matching always exist?

Yes — the Gale-Shapley algorithm is a constructive proof that a stable matching always exists for any set of complete preference lists, no matter how the preferences are arranged.

What does 'proposer-optimal' mean?

It means every proposer ends up with the best possible partner they could get in any stable matching — the tradeoff is that reviewers, symmetrically, get their worst outcome among all stable matchings compared to running the algorithm with roles reversed.

Do preference lists need to rank everyone?

Yes — this calculator requires each participant's preference list to be a complete ranking of every member of the opposite group with no repeats, matching the classic formulation of the problem.

Is the stable matching unique?

Not necessarily — different valid stable matchings can exist for the same preferences; Gale-Shapley finds the proposer-optimal one specifically, not an arbitrary stable matching among possibly several.

How many participants can this calculator handle?

This calculator supports up to 15 participants per side, keeping the algorithm and preference-list validation instant while covering typical hand-entered examples.

Where is the stable marriage problem used in real life?

The same algorithm (and its many-to-one variant) is used for matching medical residents to hospitals (the National Resident Matching Program), students to schools, and in some kidney exchange and job-matching platforms.

Stable Marriage Problem Solver — Find a Stable Matching Between Two Groups

Our Stable Marriage Problem Solver finds a matching between two equal-sized groups — proposers and reviewers — such that no pair would both prefer each other over their assigned match, using the Gale-Shapley deferred-acceptance algorithm, given each participant's ranked preference list over the other group.

Quick Answer

Enter ranked preference lists for two equal-sized groups to instantly find a stable matching via the Gale-Shapley algorithm.

Proposer preferences

One line per proposer: Name: pref1, pref2, ... ranking every reviewer, e.g. A1: B2, B1, B3.

Reviewer preferences

One line per reviewer: Name: pref1, pref2, ... ranking every proposer, e.g. B1: A3, A1, A2.

How to Use the Stable Marriage Problem Solver — Gale-Shapley Algorithm Online

1
Enter each proposer's preferences as one line: Name: pref1, pref2, pref3, ... (ranked from most to least preferred).
2
Enter each reviewer's preferences the same way, ranking every proposer.
3
Click 'Calculate' to find a stable matching via the Gale-Shapley algorithm.

Why Use Stable Marriage Problem Solver — Gale-Shapley Algorithm Online?

A matching between two groups is 'stable' if there's no pair who would both rather be matched to each other than to their current assigned partners — such a pair would have an incentive to break their existing matches, making the pairing unstable. The Gale-Shapley algorithm always finds a stable matching (a foundational result that earned the 2012 Nobel Prize in Economics): each unmatched proposer proposes to their top remaining choice, each reviewer tentatively accepts their best offer so far and rejects the rest (even bumping a previous match if a better offer arrives), and this repeats until everyone is matched. The result is not just stable but proposer-optimal — every proposer gets the best partner they could possibly have in any stable matching.

Frequently Asked Questions

Related Tools

Network Flow Calculator — Max Flow via Edmonds-Karp Online

Find the maximum flow from a source to a sink in a capacitated directed graph using the Edmonds-Karp algorithm. Free calculator with a simple edge-list input.

Graph Coloring Calculator — Welsh-Powell Algorithm Online

Color a graph's vertices so no two connected nodes share a color, using the greedy Welsh-Powell algorithm. Free calculator with a simple edge-list input.

Permutation Calculator — Calculate P(n,r) Online

Calculate permutations P(n,r) — the number of ways to arrange r items from n total items where order matters. Free calculator with step-by-step solutions and formula breakdowns.