Stable Marriage Solver screenshot

Stable Marriage Solver

Solve the stable marriage problem with Gale–Shapley from two preference tables, and verify that the matching has no blocking pair.

Privacy First
0 Runs
Updated 2026-11-22
Runs in your browser
No sign-up, no upload
Stability verified, not assumed

Stable Marriage Solver

Solve the stable marriage problem with Gale–Shapley from two preference tables, and verify that the matching has no blocking pair.

How this page computes

Both preference tables are parsed and validated: the same names on both sides, each line ranking every member of the other side, no repeats. Ranks are turned into positions so a comparison is a number.

The proposers then propose in order while a free list is non-empty. A final pass over every preferred-but-unmatched pair is the stability check, and the output states how many proposals were made.

The calculation runs entirely in this browser tab; nothing is uploaded.

Two sides each rank the other, and the page finds a matching in which no pair would rather be with each other than with their assigned partners. On the two-by-two sample the answer is A with X and B with Y, and the page then checks every pair rather than trusting the algorithm.

Gale–Shapley is linear and always terminates with a stable matching, but which one depends on who proposes: the proposers get their best stable partner and the receivers their worst. The page says which side proposed so the result is read correctly.

How to use Stable Marriage Solver

Write one line per proposer as "A: X Y" — the name, a colon, then every receiver in order of preference. Do the same for the receivers, ranking every proposer.

Press Run. Each line must rank every member of the other side, because a partial ranking cannot answer whether a pair would rather be together. The output names the pairs and states that every blocking pair was checked.

Gale–Shapley, and the check that makes it trustworthy

Each free proposer approaches its next choice in order. A receiver who is free accepts; a receiver already matched compares the newcomer with the current partner and keeps the preferred one, releasing the other to propose again. Proposers only move down their lists, receivers only move up theirs, so the process terminates.

The stability check is separate from the algorithm: for every proposer and every receiver it prefers to its own match, the page asks whether that receiver also prefers it. A single yes would be a blocking pair, and the page refuses with the pair named if it ever finds one.

What to Expect

Best for

  • Matching two sides where both have preferences
  • A residency, school-place or task-assignment toy model
  • Seeing why the proposing side does better

Not ideal for

  • Preferences that tie two candidates equally, which need a tie rule
  • Three-sided matching, which is a different problem
  • Unequal sides, which this page refuses

What this tool keeps

  • Every ranking exactly as typed

What may need cleanup

  • Nothing: the matching is stable and complete

Common errors

  • A list that ranks fewer than everyone is refused with the count
  • A name on one side that is not on the other is refused by name
  • A repeated preference on one line is refused

Example use cases

  • Match two proposers with two receivers
  • Show that swapping who proposes changes the matching
  • Check that a hand-made matching has a blocking pair

Sample input

A: X Y and B: Y X; X: B A and Y: A B

Sample output

stable matching A - X and B - Y, with zero blocking pairs

Who this is for

  • Students meeting matching theory
  • Readers checking an assignment

Frequently asked questions

Why does the proposing side get its best partner?

Because a proposer only moves down its list when rejected, and it is rejected only by a receiver who prefers someone else. The matching it ends with is the best it can get in any stable matching, which is the proposer-optimal property.

What is a blocking pair?

A proposer and a receiver who are not matched to each other but both prefer each other to their assigned partners. If one existed, the matching would be unstable, and the page checks every such pair before printing its answer.

Can the two sides be different sizes?

Not on this page. With unequal sides some members stay unmatched, which changes the definition of stability, so the page refuses and names the two counts.

Developer program

Build custom tools for your store

Join the SDK program to create useful ecommerce utilities for your store.