In standard economics, prices move so that supply meets demand, but many situations forbid prices. In 1962, Shapley and Gale proposed the deferred-acceptance procedure—now called the Gale-Shapley algorithm—and proved it always produces a stable matching. In the 1980s, Roth showed that this very algorithm explained why the U.S. medical residency market worked better after centralization. Roth then redesigned the system to handle doctor couples and later applied similar ideas to high-school admissions and other arenas, ensuring the mechanisms resist strategic manipulation. Their combined work delivers fair and efficient allocations in many real markets.

The Gale–Shapley algorithm iteratively has the proposing side submit offers in order of preference while the receiving side tentatively holds its best offer and rejects the rest; the process converges to a core-stable matching. The side that proposes obtains its Pareto-optimal stable outcome, whereas the opposite side receives its worst stable outcome, making the choice of proposer crucial. Roth explained empirical puzzles—such as exploding offers and the couple problem—in the National Resident Matching Program and showed that switching to an applicant-proposing mechanism yields near strategy-proofness. In kidney exchange, he adapted top-trading-cycle ideas to create 3- and 4-way chains, mitigating shortage-induced incompatibilities and reducing patient mortality. These advances connect with auction theory and platform design, establishing mechanism design for matching markets as a vibrant interdisciplinary field.

Stable matching theory defines a choice function f that selects allocations free of blocking pairs from complete preference profiles over disjoint sets N and M. The Gale–Shapley deferred-acceptance algorithm computes a core element in O(n^2) time and satisfies group-strategy-proofness for the proposing side (Dubins–Freedman). To accommodate NP-hard couple externalities, the Roth–Peranson (1999) scheme augments applicant-proposing DA with heuristic swaps and regional pair constraints, mapping 200,000-plus residency matches into the stable set annually. In kidney exchange, an ILP maximizing cycle/chain covers on the compatibility graph is employed, and β-approximation results preserve incentive compatibility under horizon-k constraints. These applications have catalyzed research on matching with contracts, DA with ties, and fairness notions such as α-EF and justified envy in school choice, anchoring the agenda of mechanism design without money.