Matching theory (economics)

Matching theory (economics)
Name	Matching theory
Field	Microeconomics, Game theory, Market design
Notable contributors	David Gale, Lloyd Shapley, Alvin E. Roth
Related theories	Cooperative game theory, General equilibrium theory, Social choice theory

Matching theory (economics). Matching theory is a branch of microeconomics and game theory that studies the formation of mutually beneficial relationships between agents in markets without traditional price mechanisms. It provides a framework for analyzing and designing allocation systems for heterogeneous and indivisible goods, such as jobs, schools, organs, or partners. The field is distinguished by its focus on two-sided matching markets and its deep integration of theoretical proofs with practical market design.

Overview

Matching theory analyzes markets where monetary transfers are either impossible or highly restricted, necessitating direct pairwise allocations. Foundational work by David Gale and Lloyd Shapley introduced the concept of stability as a central solution concept, proving that stable matchings always exist for certain market structures. This theoretical work was later extended and applied by economists like Alvin E. Roth to real-world problems, leading to the design of institutions such as the National Resident Matching Program and kidney exchange programs. The theory sits at the intersection of cooperative game theory, social choice theory, and computation, influencing both economic theory and operations research.

Core concepts and models

The foundational model is the Gale–Shapley algorithm, or deferred acceptance algorithm, which operates in a two-sided market with agents on one side (e.g., medical students) and institutions on the other (e.g., teaching hospitals). Key properties include stability, which ensures no pair of agents would mutually prefer each other over their current assignments, and strategy-proofness for one side of the market. Other central models include the college admissions problem, the hospital/resident problem, and the housing market model. More complex extensions involve many-to-one matching, as in school choice programs, and matching with contracts, which can incorporate terms like salaries or schedules.

Key results and theorems

The seminal result is the Gale–Shapley theorem, which guarantees the existence of at least one stable matching for any two-sided market with strict preferences. A corollary is the rural hospitals theorem, which states that hospitals that fail to fill all positions in one stable matching will have the same number of filled positions in every stable matching. The lattice theorem demonstrates that the set of stable matchings forms a distributive lattice, with optimal stable matchings for each side. Furthermore, the revealed preference analysis in matching markets shows that the deferred acceptance algorithm is strategy-proof for the side that makes proposals.

Applications

Matching theory has been successfully implemented in numerous high-stakes markets. A landmark application is the redesign of the National Resident Matching Program, which assigns medical graduates to residency programs in the United States and Canada. In education, it underpins school choice systems in cities like New York City and Boston. The theory also guides the design of kidney exchange programs, such as the Alliance for Paired Donation, enabling life-saving transplants. Other applications include the assignment of students to public schools, the placement of new lawyers to judicial clerkships, and the matching of internet advertisers to search engine keywords.

Algorithmic and computational aspects

The deferred acceptance algorithm is computationally efficient, with polynomial-time complexity, making it practical for large-scale implementation. Research in computer science and operations research has explored the computational complexity of finding stable matchings under various constraints, such as incomplete preference lists or couples applying together. The integration of matching theory with algorithmic game theory has led to studies on incentive compatibility and the price of anarchy in decentralized matching markets. Modern challenges include designing algorithms for dynamic matching, as seen in ride-sharing platforms like Uber and Lyft.

History and development

The field originated with the 1962 paper "College Admissions and the Stability of Marriage" by David Gale and Lloyd Shapley. For decades, it remained a theoretical curiosity until Alvin E. Roth demonstrated its direct applicability to the failing National Resident Matching Program in the 1980s. Roth's empirical and experimental work bridged theory and practice, a contribution recognized with his share of the 2012 Nobel Memorial Prize in Economic Sciences, which he received alongside Shapley. Subsequent development has been driven by interdisciplinary collaboration among economists, computer scientists at institutions like Stanford University and Harvard University, and practitioners designing real-world allocation systems.

Category:Economic theories Category:Game theory Category:Market design