Core Selection (Matching)
The selection of an allocation from the core of a matching market, typically via deferred-acceptance algorithms.
Definition
In a two-sided matching market (e.g., men-women, workers-firms), a matching is in the core if no blocking pair exists such that both prefer each other to their current partners under .
Gale-Shapley (1962) deferred acceptance algorithm finds the firm-optimal (or worker-optimal) stable matching in polynomial time.
Intuition
The core in matching corresponds to stability: no pair wants to leave their current match for each other.
Deferred acceptance simulates a market where one side proposes and the other provisionally holds the best offer, iteratively improving.
Worked example
The National Resident Matching Program (NRMP) uses a deferred-acceptance algorithm to match medical residents to hospitals. The resulting match is stable (core-selected).
School choice programs in New York and Boston use variants of the Gale-Shapley mechanism.
The math
The set of stable matchings forms a distributive lattice with the man-optimal and woman-optimal matchings as extreme points.
The core is nonempty in any two-sided matching market with strict preferences (Gale-Shapley). In one-sided (roommate) problems, the core may be empty.
Where it is used
Labor market matching, school assignment, kidney exchange, and online dating platforms.
Winner of the 2012 Nobel Memorial Prize (Shapley and Roth).
Go deeper
More in Game theory
Assembled from the ReLU.chat curated knowledge base. These explanations are concise on purpose; check the sources for anything important.