Matching (Two-Sided Models)

By: Alvin E. Roth

One of the main functions of many markets and social processes is to match one kind of agent with another: e.g. students and colleges, workers and firms, marriageable men and women. A class of "two-sided matching models" for studying such processes was introduced by Gale and Shapley (1962), who focused on college admissions and marriage.

A market is two-sided if there are two sets of agents, and if an agent from one side of the market can be matched only with an agent from the other side. Gale and Shapley proposed that a matching (of students and colleges, or men and women) could be regarded as stable only if it left no pair of agents on opposite sides of the market who were not matched to each other but would both prefer to be. They showed that a special property of two-sided (as opposed to one or three-sided) markets is that stable matchings always exist (at least when agents' preferences are uncomplicated).

The idea is that, if we consider matching processes whose rules are that any two agents on opposite sides of the market can be matched to each other if they both agree, then, unless a matching is stable, there are players who wish to be matched to each other but who are not, even though the rules allow them to arrange such a match. So only stable matchings are likely to arise if the matching process is sufficiently "free" as to allow all potential matchings to be considered.

A natural application of two-sided matching models is to labor markets. Shapley and Shubik (1972) showed that the properties of stable matchings are robust to generalizations of the model which allow both matching and wage determination to be considered together. Kelso and Crawford (1982) showed how far these results can be generalized when firms, for example, may have complex preferences over the composition of their workforce.

Two-sided matching models have proved useful in the empirical study of labor markets, starting with the demonstration in Roth (1984) that since the early 1950's the entry level labor market for American physicians has been organized in a way that produces (predominantly) stable matchings. Subsequent work has identified natural experiments which show that labor markets organized so as to produce unstable matchings suffer from certain kinds of difficulties which are largely avoided in comparable markets organized to produce stable matchings. This work combines the traditions of cooperative and noncooperative game theory, by considering how the strategic environment faced by market participants influences the stability of the resulting market outcome.

Recent work has focused on the timing of transactions. Bergstrom and Bagnoli (1993) model causes of delay in marriage, while Roth and Xing (1994) discuss several dozen matching markets in which there has been a tendency for transactions to become steadily earlier (e.g. clerks for Federal judges in the United States are now hired almost two years before they begin work, and similar phenomena are observed among British doctors, graduates of elite Japanese universities, etc.).

An overview of matching can be found in Roth and Sotomayor (1990).


Bergstrom, Ted and Mark Bagnoli [1993], "Courtship as a Waiting Game," Journal of Political Economy, 101, 185-202.

Gale, David and Lloyd Shapley [1962], "College Admissions and the Stability of Marriage," American Mathematical Monthly, 69, 9-15.

Kelso, Alexander S.,Jr. and Vincent P. Crawford [1982], "Job Matching, Coalition Formation, and Gross Substitutes", Econometrica, 50, 1483-1504.

Roth, Alvin E. [1984], "The Evolution of the Labor Market for Medical Interns and Residents: A Case Study in Game Theory", Journal of Political Economy, 92, 1984, 991-1016.

Roth, Alvin E. and Marilda Sotomayor [1990], Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis, Cambridge, Cambridge University Press.

Roth, Alvin E. and Xiaolin Xing [1994] "Jumping the Gun: Imperfections and Institutions Related to the Timing of Market Transactions," American Economic Review, 84, September, 992-1044.

Shapley, Lloyd S. and Martin Shubik [1972], "The Assignment Game I: The Core," International Journal of Game Theory, 1, 111-130.

( Social Science Encyclopedia, 2nd edition, Adam Kuper and Jessica Kuper (editors), London, Routledge, 1996, 512-513.)