Matching markets

This strand of the literature emerged from the Gale and Shapley (1962) introduction of the Gale-Shapley algorithm. Problems studied in this strand include:

• Stable marriage problem - a one-to-one matching between agents of two disjoint groups, each of whom has strict preferences over agents of the other group, so the preferences form a bipartite graph. The typical example is men and women, as in the campus Marriage Pact.
• Hospitals-residents problem - a one-to-many matching between agents of two disjoint groups. The typical example is matching medical school graduates for internships in hospitals, as in the National Resident Matching Program.
• Stable matching with indifference - a generalization of the stable marriage problem, where agents on each group may be indifferent between two or more agents of the other group.
• Stable roommates problem - a one-to-one matching between agents of a single group. This is a generalization of stable marriage, as the preferences form a general graph.
• Pareto optimal matchings;
• Popular matchings;
• Rank-maximal matching and generous matching.

This strand dates back to work on Monge (1781) and Kantorovich (1942) work on optimal transportation theory, in particular following Koopmans and Beckmann (1957) who studies the problem with pricing. Modern TU matching follows work by Shapley and Shubik (1971), who provided a TU equivalent of Gale and Shapley (1962), as well as Becker (1973) who applied TU matching to the marriage market.

Walrasian markets are markets with people and commodities, where people buy and sell commodities, and have different preferences regarding various bundles of commodities, but do not match with other people. In contrast, the theory of matching markets focuses of who matches with whom.

Search-and-matching theory is a descriptive theory describing the decentralized formation of matches when there are search frictions (the search is costly). In contrast, matching markets theory usually considers normative (desirable) properties of matchings, and centralized rules that guarantee such properties. Under certain contexts, the search and matching equilibrium converges to a stable matching when search frictions disappear.

Matching theory typically focuses on two-sided matching, where two types of workers are considered (e.g. men and women in the marriage market, firms and workers in the labor market, and students matching with colleges). A smaller literature considers other types of matching, such as one-sided matching (e.g. the stable roommates problem) and many-sided matching (e.g. man-woman-child matching). Within two sided matching, three types of matches are considered: one-to-one, many-to-one, and many-to-many.

Matching theory has been applied to study a wide set of applications, including: marriage, housing allocation, kidney exchange, the National Resident Matching Program, school choice, and hedging strategies in options financial markets.