Two-Sided Matching

Last updated
Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis
Author
SeriesEconometric Society monographs
Subject Matching markets
Publisher Cambridge University Press
Publication date
1990

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, [1] [2] and published in 1990 by the Cambridge University Press as volume 18 in their series of Econometric Society monographs. [3] For this work, Roth and Sotomayor won the 1990 Frederick W. Lanchester Prize of the Institute for Operations Research and the Management Sciences. [4]

Contents

Topics

The book's introduction discusses the National Resident Matching Program and its use of stable marriage to assign medical students to hospital positions, and collects the problems in economics that the theory of matching markets is positioned to solve. Following this, it has three main sections. [2] [4] [5]

The first of these sections discusses the stable matching problem in its simplest form, in which two equal-sized groups of agents are to be matched one-to-one. It discusses the stability of solutions (the property that no pair of agents both prefer being matched to each other to their assigned matches), the lattice of stable matchings, the Gale–Shapley algorithm for finding stable solutions, and two key properties of this algorithm: that among all stable solutions it chooses the one that gives one group of agents their most-preferred stable match, and that it is an honest mechanism that incentivizes this group of agents to report their preferences truthfully. [4] [5]

The second part of the book, which reviewer Ulrich Kamecke describes as its most central, concerns extensions of these results to the many-one matching needed for the National Resident Matching Program, and to the specific economic factors that made that program successful compared to comparable programs elsewhere, and that have impeded its success. One example concerns the two-body problem of married couples who would both prefer to be assigned to the same place, a constraint that adds considerable complexity to the matching problem and may prevent a stable solution from existing. [1] [4]

The third part of the book concerns a different direction in which these ideas have been extended, to matching markets such as those for real estate in which indivisible goods are traded, with money used to transfer utility. It includes results in auction theory, linear and nonlinear utility functions, and the assignment game of Lloyd Shapley and Martin Shubik. [4] [5] [6]

Audience and reception

Two-Sided Matching presents known material on its topics, rather than introducing new research, but it is not a textbook. Instead, its aim is to provide a survey of this area aimed at economic practitioners, with arguments for the importance of its material based on its pragmatic significance rather than its mathematical beauty. Nevertheless, it also has material of interest to researchers, including an extensive bibliography and a concluding list of open problems for future research. [4] Compared to other books on stable matching, including Marriages Stables by Donald Knuth and The Stable Marriage Problem: Structure and Algorithms by Dan Gusfield and Robert W. Irving, Two-Sided Matching focuses much more on the economic, application-specific, and strategic issues of stable matching, and much less on its algorithmic issues. [2]

Alan Kirman calls the book a "clear and elegant account" of its material, writing that its focus on practical applications makes it "of particular interest". [7] Theodore Bergstrom writes that it will also "delight economists who want to think beautiful thoughts about important practical problems". [1] Benny Moldovanu predicts that it "will become the standard source of reference" for its material. [8] And Uriel Rothblum calls it the kind of once-a-generation book that can "change the way in which an entire field of study is viewed." [2]

Related Research Articles

In the social sciences, methodological individualism is the principle that subjective individual motivation explains social phenomena, rather than class or group dynamics which are illusory or artificial and therefore cannot truly explain market or social phenomena.

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:

Lloyd Shapley American mathematician

Lloyd Stowell Shapley was an American mathematician and Nobel 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."

David Gale American mathematician

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.

Hobart Peyton Young is an American game theorist and economist known for his contributions to evolutionary game theory and its application to the study of institutional and technological change, as well as the theory of learning in games. He is currently centennial professor at the London School of Economics, James Meade Professor of Economics Emeritus at the University of Oxford, professorial fellow at Nuffield College Oxford, and research principal at the Office of Financial Research at the U.S. Department of the Treasury.

In mathematics, economics and computer science, particularly in the fields of combinatorics, game theory and algorithms, the stable-roommate problem (SRP) is the problem of finding a stable matching for an even-sized set. A matching is a separation of the set into disjoint pairs ("roommates"). The matching is stable if there are no two elements which are not roommates and which both prefer each other to their roommate under the matching. This is distinct from the stable-marriage problem in that the stable-roommates problem allows matches between any two elements, not just between classes of "men" and "women".

Alvin E. Roth American academic (born 1951)

Alvin Elliot 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 Economics Association in 2017.

Market design

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, named for David Gale and Lloyd Shapley who had described it as solving both the college admission problem and the stable marriage problem. It takes polynomial time, and the time is linear in the size of the input to the algorithm. It is a truthful mechanism from the point of view of the proposing participants, for whom the solution will always be optimal.

In computational complexity theory, CC is the complexity class containing decision problems which can be solved by comparator circuits of polynomial size.

Top trading cycle (TTC) is an algorithm for trading indivisible items without using money. It was developed by David Gale and published by Herbert Scarf and Lloyd Shapley.

Benny Moldovanu is a German-Israeli economist who currently holds the Chair of Economic Theory II at the University of Bonn. His research focuses on applied game theory, auction theory, mechanism design, contests and matching theory, and voting theory. In 2004, Moldovanu was awarded the Gossen Prize for his contributions to auction theory and mechanism design.

Stable marriage with indifference is a variant of the stable marriage problem. Like in the original problem, the goal is to match all men to all women such that no pair of man and woman who are unmarried to each other, would simultaneously like to leave their present partners and pair with each other instead.

Marilda A. Oliveira Sotomayor is a Brazilian mathematician and economist known for her research on auction theory and stable matchings. She is a member of the Brazilian Academy of Sciences, Brazilian Society of Econometrics, and Brazilian Society of Mathematics. She was elected fellow of the Econometric Society in 2003 and international honorary member of the American Academy of Arts and Sciences in 2020.

In mathematics, economics, and computer science, the lattice of stable matchings is a distributive lattice whose elements are stable matchings. For a given instance of the stable matching problem, this lattice provides an algebraic description of the family of all solutions to the problem. It was originally described in the 1970s by John Horton Conway and Donald Knuth.

In mathematics, economics, and computer science, the stable matching polytope or stable marriage polytope is a convex polytope derived from the solutions to an instance of the stable matching problem.

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.

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.

The Marriage Pact is an unofficial yearly matching activity that takes place on American college campuses, by which students fill out compatibility surveys in order to find a partner among fellow participants, who they agree will be their backup "safety" spouse in the future in case they are then unmarried.

References

  1. 1 2 3 Bergstrom, Theodore C. (June 1992), "Review of Two-Sided Matching", Journal of Economic Literature , 30 (2): 896–898, JSTOR   2727713
  2. 1 2 3 4 Rothblum, Uriel G. (January 1992), "Review of Two-Sided Matching", Games and Economic Behavior , 4 (1): 161–165, doi:10.1016/0899-8256(92)90011-g
  3. ↑ Wieczorek, A., "Review of Two-Sided Matching", zbMATH , Zbl   0726.90003
  4. 1 2 3 4 5 6 Kamecke, Ulrich (November 1992), "Review of Two-Sided Matching", Economica , New Series, 59 (236): 487–489, doi:10.2307/2554894, JSTOR   2554894
  5. 1 2 3 Potters, Jos (1993), "Review of Two-Sided Matching", Mathematical Reviews , MR   1119308
  6. ↑ Winters, Jan Kees (October 1992), "Review of Two-Sided Matching", European Journal of Political Economy , 8 (3): 510–514, doi:10.1016/0176-2680(92)90017-b
  7. ↑ Kirman, Alan P. (July 1992), "Review of Two-Sided Matching", The Economic Journal , 102 (413): 975–976, doi:10.2307/2234601, JSTOR   2234601
  8. ↑ Moldovanu, B. (January 1992), "Review of Two-Sided Matching", Journal of Economics , 55: 116–117, ProQuest   1299512649
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.