Matpic
mathematics, in pictures
Concept

Stable matching

A pairing of two sides in which no two people on opposite sides would both rather have each other than what they hold. One always exists and is found by deferred acceptance, and which of several is reached depends on which side proposes.

Named by 7 essays across one field — each of them below, with the objects they name alongside it.

One matching that is not stable, and all 24 counted by blocking pairs. An unstable matching with its blocking pair ringed and both members' rankings marked, above an exhaustive census of every matching of the instance by how many blocking pairs it has.

Nobody has a reason to run away

A matching is stable when no two people on opposite sides would both rather have each other than what they have — a condition that names nothing to build and everything to rule out. The surprise is that something always satisfies it, however perverse the rankings are made.

applied · Stable matching The 4 stable matchings of the instance, ordered by side one's preference. A Hasse diagram of the stable matchings with the best for side one at the top, beside a table giving the join and the meet of every pair.

The side that proposes wins

An instance usually has several stable matchings, and the set of them is not a heap — it is a lattice, closed under taking the better partner and under taking the worse. The two ends of that lattice are exactly what deferred acceptance returns from the two sides, so whoever proposes decides which end the instance lands on.

applied · Stable matching Every ranking 4 could submit, and the 4 that pay. One participant's true ranking, a cell for every ranking they could submit instead labelled with the partner it returns, the profitable misreports listed, and the same search run on the proposing side finding none.

No stable rule is safe from a lie

A stable matching always exists, and the side that proposes gets the best one it could hope for. This essay closes the story with the result that spoils it — one participant's whole strategy space searched, four submissions found that beat the truth, and a theorem saying no rule anywhere escapes.

applied · Stable matching Every stable matching leaves out the same people. 4 stable matchings of a market with short lists, drawn as two columns joined by edges; every one leaves the same letter and number unmatched.

The people every stable answer leaves out

Let the lists be short and let one side take several partners. Stable matchings still exist and there can be many of them — but every one leaves out exactly the same people, and a member who is left with an empty place holds exactly the same partners in every one. A three-line count proves it.

applied · Stable matching The odd ring that forbids a stable pairing. The ranked lists of 6 people and a stable partition of them drawn on a circle: pairs as plain chords, a ring of three or more as arrows from each person to the one they hold. An odd ring is present, as it is in every stable partition of this instance.

A ring that no pairing can break

Put everybody in one pool and a stable pairing may not exist. Allow rings as well as pairs and something stable always exists — and the pairs-only answer fails exactly when that stable arrangement contains a ring of odd length. Two sides make every ring even, which is the whole reason the two-sided theorem holds.

applied · Stable matching Who does well in a random market, as it grows. A log-log plot of the average rank of partner for the proposing side and the receiving side of random balanced markets against the market's size, with dashed curves for ln n and n over ln n.

One extra person on one side

In a random market of a thousand a side, whoever proposes gets about their seventh choice and whoever receives gets about their hundred-and-fortieth. Add one person to one side and the advantage of proposing all but disappears: the shorter side does well and the longer side badly, whichever side proposes, and most people are left with exactly one stable partner.

applied · Stable matching 15 stable matchings, by what each side pays. A scatter plot of every stable matching of one instance by the total rank each side receives, running from side one's best matching to side two's, with the median, the least-total and the most even matchings marked.

The matching in the middle

List every stable matching of a market, give each member their stable partners sorted from best to worst, and hand each the one in the middle. Nothing says the result should even be a matching — two people might pick the same partner — and yet it always is one, it is always stable, and the other side gets its median partners too.

applied · Stable matching

Named alongside it

The objects these essays reach for when they reach for this one.

Preference profileBlocking pairDeferred acceptanceCounterexampleExhaustive searchOrder latticeExistence proofInvariantLatticeBijectionConstructive proofCounting two ways

All concepts