THE GALE-SHAPLEY — a dart

THE GALE-SHAPLEY a matching no pair wants to break

Given rankings on both sides, deferred acceptance always finds a stable matching — one with no pair who would both rather have each other. Proposers propose in preference order; receivers hold their best offer and reject the rest; it always terminates, always stable. The twist: the answer is not unique. Proposers get their best possible stable partner, receivers their worst — so who proposes changes the outcome.

THE TECHNIQUE deferred acceptance → a stable matching

The demo checks a 2×2 instance where the proposer-optimal and receiver-optimal matchings differ — and both are stable: live demo

HISTORY & CREDIT Gale & Shapley · 1962

“The stable matching is unique.” — there can be many; deferred acceptance yields the proposer-optimal one, and the receiver-proposing version gives a different, also-stable matching. cited

propose · each free proposer offers to their next choice.
hold & reject · receivers keep the best offer so far, reject the rest — no blocking pair survives.
1962 · Gale & Shapley; Roth ran it for medical-residency matching — Shapley & Roth, Nobel 2012.

Stable, but which stable one depends on who asks. algorithm

RECOMMEND FOR I-13 the two stable matchings, on the compiler

On i-13, for this instance the proposer-optimal and receiver-optimal matchings both have no blocking pair, yet they differ:

$ i13 run gm_gale-shapley.i13 RUN OK · 85 step(s) A_no_block = 1 -- man-optimal {m0-w0, m1-w1} stable B_no_block = 1 -- woman-optimal {m0-w1, m1-w0} stable both_stable = 1 differ = 1

Recommend as the KEEPER SHOT — a loose-spec DOF. “A stable matching” is a LOOSE-but-correct spec: two correct mechanisms (proposer- vs receiver-proposing) compute DIFFERENT valid outputs. The strongest same-function-differ candidate in a while — but the choice is fixed by which side proposes, a labeling of the input (B44), and it is the non-confluent mirror of the seated confluence axis. The panel rules; expected NULL, coordinate-dependent.