liveBook · Manning

Stability

As explained in Algorithms Every Programmer Should Know

A stable matching is an assignment in which no unmatched pair would both prefer each other to their current partners.

A matching is stable when no unmatched pair would both prefer each other to their current partners. Such a pair could disrupt the assignment by switching, so stability rules out mutually desirable alternatives. section 2.0

Students and universities

Suppose X ranks Alice first, Y ranks Bob first, and Z ranks Carol first; each student also ranks that university first. Pairing X with Alice, Y with Bob, and Z with Carol leaves no unmatched pair that prefers one another. section 2.1.1

Gale–Shapley builds stable matches through proposals and temporary acceptances. Stability does not mean every participant gets an ideal match: the proposing side tends to fare better, and a stable result need not be optimal for everyone. section 2.0 section 2.3.2

The same idea is adapted to settings such as residency placement and ride-sharing, where avoiding mutually preferable alternatives can help limit withdrawals, cancellations, or other disruptions. section 2.2.4 section 2.2.2

How Algorithms Every Programmer Should Know covers it

How deep it goes
Defines stability through mutually preferable unmatched pairs and contrasts it with universal optimality, without developing a formal proof.
Examples
Uses student–university preferences and points to residency placement, ride-sharing, dating, and restaurant allocation.
What you can do after
Evaluate whether an assignment is stable by checking for an unmatched pair that would mutually prefer one another.
How it connects
Connects stability to Gale–Shapley, deferred acceptance, ranked preferences, and proposer advantage.

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.