Two-Sided Matching

Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis

Author	Alvin E. Roth Marilda Sotomayor
Series	Econometric 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]

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]

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]