matchingtheorie

Matchingtheorie, the German term for matching theory, is a branch of economics and game theory that studies the design and analysis of mechanisms for pairing agents in markets where agents on one side have preferences over agents on the other. The central goal is to produce stable and efficient matchings in two-sided or multi-sided markets, such as workers to firms, students to schools, or organ donors to recipients. A matching is stable if there is no blocking pair: a pair of agents who would both prefer to be matched to each other over their current assignments.

Two foundational problems are the stable marriage and the hospital-residents problems. The Gale-Shapley deferred acceptance algorithm provides a method to compute a stable matching in a finite number of steps; it guarantees existence of a stable matching. In two-sided markets with many-to-one matches, schools or hospitals have capacities, and stable matchings form a lattice; there are optimal stable matchings for one side.

Historically, the field was developed by Lloyd Shapley and Alvin E. Roth. Their work on stable matching and game-theoretic aspects has informed the design of centralized matching mechanisms. Real-world deployments include the National Resident Matching Program for medical internships in the United States, and kidney exchange programs that re-match incompatible donor-recipient pairs into feasible matches. School choice systems and public sector allocations have also used matching algorithms to improve efficiency and fairness.

Current research in matching theory explores issues such as incomplete information, indifferences in preferences, ties, preferences with priorities, dynamic and repeated matching, fairness and stability notions beyond stability, and strategic considerations under various institutional rules or constraints.