Stable matching theory

Last updated

In economics, stable matching theory or simply matching theory, is the study of matching markets. Matching markets are distinguished from Walrasian markets in the focus of who matches with whom. Matching theory typically examines matching in the absence of search frictions, differentiating it from search and matching theory. In 2012, the Nobel Memorial Prize in Economic Sciences was awarded to Alvin E. Roth and Lloyd Shapley for their work on matching theory. [1]

Contents

Overview

Matching has two main categories. One category is matching with nontransferrable utility (NTU), where match payoffs are nontransferable and stability requires individual rationality and double coincidence of wants. This strand of the literature emerged from the Gale and Shapley (1962) introduction of the stable marriage problem. The second category is matching with transferable utility (TU). The latter 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. [2]

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. [3]

Matching theory has been applied to study positive questions, such as who matches with who, as well as normative questions regarding how to best design matching markets.

Applications

Matching theory has been applied to study a wide set of applications, including: marriage, housing allocation, kidney exchange, the National Resident Matching Program, and school choice. [4]

Relationship with search and matching theory

Matching theory typically examines matching in the absence of search frictions in a centralized environment, differentiating it from search and matching theory. Under certain contexts, the search and matching equilibrium converges to a stable matching when search frictions disappear [5]

See also

Related Research Articles

Behavioral economics is the study of the psychological, cognitive, emotional, cultural and social factors involved in the decisions of individuals or institutions, and how these decisions deviate from those implied by classical economic theory.

Experimental economics is the application of experimental methods to study economic questions. Data collected in experiments are used to estimate effect size, test the validity of economic theories, and illuminate market mechanisms. Economic experiments usually use cash to motivate subjects, in order to mimic real-world incentives. Experiments are used to help understand how and why markets and other exchange systems function as they do. Experimental economics have also expanded to understand institutions and the law.

In mathematics, economics, and computer science, the stable marriage problem is the problem of finding a stable matching between two equally sized sets of elements given an ordering of preferences for each element. A matching is a bijection from the elements of one set to the elements of the other set. A matching is not stable if:

<span class="mw-page-title-main">Lloyd Shapley</span> American mathematician (1923–2016)

Lloyd Stowell Shapley was an American mathematician and Nobel Memorial Prize-winning economist. He contributed to the fields of mathematical economics and especially game theory. Shapley is generally considered one of the most important contributors to the development of game theory since the work of von Neumann and Morgenstern. With Alvin E. Roth, Shapley won the 2012 Nobel Memorial Prize in Economic Sciences "for the theory of stable allocations and the practice of market design."

<span class="mw-page-title-main">David Gale</span> American mathematician (1921–2008)

David Gale was an American mathematician and economist. He was a professor emeritus at the University of California, Berkeley, affiliated with the departments of mathematics, economics, and industrial engineering and operations research. He has contributed to the fields of mathematical economics, game theory, and convex analysis.

<span class="mw-page-title-main">Dale T. Mortensen</span> American economist

Dale Thomas Mortensen was an American economist, a professor at Northwestern University, and a winner of the Nobel Memorial Prize in Economic Sciences.

<span class="mw-page-title-main">Christopher A. Pissarides</span> British-Cypriot economist

Sir Christopher Antoniou Pissarides is a Cypriot economist. He is Regius Professor of Economics at the London School of Economics, and Professor of European Studies at the University of Cyprus. His research focuses on macroeconomics, labour economics, economic growth, and economic policy. In 2010, along with Peter Diamond and Dale Mortensen, he received the Nobel Prize in Economics, "for their analysis of markets with theory of search frictions."

In microeconomics, search theory studies buyers or sellers who cannot instantly find a trading partner, and must therefore search for a partner prior to transacting. It involves determining the best approach to use when looking for a specific item or person in a sizable, uncharted environment. The goal of the theory is to determine the best search strategy, one that maximises the chance of finding the target while minimising search-related expenses.

Robert Butler "Bob" Wilson, Jr. is an American economist and the Adams Distinguished Professor of Management, Emeritus at Stanford University. He was jointly awarded the 2020 Nobel Memorial Prize in Economic Sciences, together with his Stanford colleague and former student Paul R. Milgrom, "for improvements to auction theory and inventions of new auction formats". Two more of his students, Alvin E. Roth and Bengt Holmström, are also Nobel Laureates in their own right.

<span class="mw-page-title-main">Alvin E. Roth</span> American academic (born 1951)

Alvin Eliot Roth is an American academic. He is the Craig and Susan McCaw professor of economics at Stanford University and the Gund professor of economics and business administration emeritus at Harvard University. He was President of the American Economic Association in 2017.

In economics, search and matching theory is a mathematical framework attempting to describe the formation of mutually beneficial relationships over time. It is closely related to stable matching theory.

<span class="mw-page-title-main">Market design</span>

Market design is a practical methodology for creation of markets of certain properties, which is partially based on mechanism design. In some markets, prices may be used to induce the desired outcomes — these markets are the study of auction theory. In other markets, prices may not be used — these markets are the study of matching theory.

The National Resident Matching Program (NRMP), also called The Match, is a United States-based private non-profit non-governmental organization created in 1952 to place U.S. medical school students into residency training programs located in United States teaching hospitals. Its mission has since expanded to include the placement of U.S. citizen and non-U.S. citizen international medical school students and graduates into residency and fellowship training programs. In addition to the annual Main Residency Match that in 2021 encompassed more than 48,000 applicants and 38,000 positions, the NRMP conducts Fellowship Matches for more than 60 subspecialties through its Specialties Matching Service (SMS). The NRMP is sponsored by a board of directors that includes medical school deans, teaching hospital executives, graduate medical education program directors, medical students and residents, and one public member.

In mathematics, economics, and computer science, the Gale–Shapley algorithm is an algorithm for finding a solution to the stable matching problem. It is named for David Gale and Lloyd Shapley, who published it in 1962, although it had been used for the National Resident Matching Program since the early 1950s. Shapley and Alvin E. Roth won the 2012 Nobel Prize in Economics for work including this algorithm.

Parag A. Pathak is Professor of Economics at the Massachusetts Institute of Technology and is affiliated with the National Bureau of Economic Research where he co-founded and directs the working group on market design.

Tayfun Sönmez is a Turkish-American professor of economics at Boston College. He is a Fellow of the Econometric Society and the 2008 winner of the Social Choice and Welfare Prize, which honors scholars under the age of 40 for excellent accomplishment in the area of social choice theory and welfare economics. Sönmez has made significant contributions in the areas of microeconomic theory, mechanism/market design, and game theory. His work has been featured by the U.S. National Science Foundation for its practical relevance.

The rural hospitals theorem (RHT) is a fundamental theorem in the theory of stable matching. It considers the problem of matching doctors to hospitals for residency, where each doctor is matched to a single hospital but each hospital has several positions for doctors. The total number of positions is larger than the total number of doctors, so some hospitals inevitably remain with unfilled positions. Usually, rural hospitals are less wanted than urban hospitals, so they often remain with many empty positions. This raised the question of whether the mechanism used to match doctors to hospitals can be changed in order to help these rural hospitals.

Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis is a book on matching markets in economics and game theory, particularly concentrating on the stable marriage problem. It was written by Alvin E. Roth and Marilda Sotomayor, with a preface by Robert Aumann, and published in 1990 by the Cambridge University Press as volume 18 in their series of Econometric Society monographs. For this work, Roth and Sotomayor won the 1990 Frederick W. Lanchester Prize of the Institute for Operations Research and the Management Sciences.

In economics and social choice theory, a no-justified-envy matching is a matching in a two-sided market, in which no agent prefers the assignment of another agent and is simultaneously preferred by that assignment.

References

  1. "The Sveriges Riksbank Prize in Economic Sciences in Memory of Alfred Nobel 2012". The Nobel Prize. Retrieved 2020-12-29.
  2. Chade, Hector; Eeckhout, Jane; Smith, Lones (2017). "Sorting through Search and Matching Models in Economics" (PDF). Journal of Economic Literature . 55: 493–544.
  3. Niederle, Muriel; Roth, Alvin; Sönmez, Tayfun (2007). The New Palgrave Dictionary of Economics, 2nd edition (PDF). Palgrave Macmillan.
  4. Levin, Jonathan (2011). "Matching Theory and Its Applications".
  5. Lauermann, Stephan; Nöldeke, Georg (2014). "Stable marriages and search frictions". Journal of Economic Theory . 151: 163–95.