Given a set of men, S m = { m 1 , m 2 ,..., m n }, and a set of women, S w = { w 1 , w 2 ,..., w n }, a matching is a one-to-one map, M : S m → S w . M is an unstable matching if a man and a woman exist who prefer each other to their M -mates. Stable is defined as not unstable. This book, which addresses the stable marriage problem in particular and stable matching problems in general, contains the following chapters:
Elementary Concepts and Results
The Structure and Representations of All Stable Matchings
Building and Exploiting the Representation of All Stable Matchings
The Stable Roommates Problem
The authors also include an appendix on open problems, a bibliography, an “Index to First Use of Major Notation,” and a subject index. The first paper on the subject introduced and solved the stable marriage problem; it gave an algorithm for finding a stable matching in both the monogamous and the polygamous versions [1]. Many variants of the basic problem have since been introduced and studied in over 100 technical papers. Knuth’s book summarized most results known in 1976 and discussed a number of open questions, thus stimulating research in the area [2].
The authors attempt to present most of the interesting results known in a single coherent exposition. The target audience is graduate-level computer scientists and interested readers with a moderate background in either algorithms or combinatorics.
In the first chapter, the authors distinguish the marriage from the roommates problem. In the marriage problem the participants are partitioned a priori; in the roommates problem they are partitioned a posteriori. The hospital/residents problem (also known as polygamous marriage or college admissions) is a many-to-one matching problem that can be transformed to a one-to-one problem by cloning hospital h (with q places) to q separate, identical hospitals, each with one place. The Gale-Shapley algorithm (GSA) may be viewed as a series of proposals from men to women; thus, it is not too surprising that the stable matching found is “man-optimal” and “woman-pessimal.” The complexity of GSA is O ( n 2 ) in the worst case, and in the average case it is n H n + O ( log n ) 4 where H n = 1 + ½ + ⅓ + ... + 1&slash;n is the n th harmonic number. The average number of stable matchings is asymptotic to ( n ln n )&slash; e. Each person has between ( ½ - &egr; ) ln n and ( 1 + &egr; ) ln n stable partners as n approaches infinity where &egr; is any positive constant.
Chapter 2 gives a revealing representation of the set of all stable matchings and of the marriage lattice ℳ. The number of stable matchings can grow exponentially with n. There is, however, a partial order π ( ℳ ) (called the rotation poset of ℳ) with O ( n 2 ) elements that represents all the stable matchings. The key idea in understanding the structure of the set of stable matchings is rotation. Let s M ( m ) denote m’s best chance for a mistress (that is, his most likely mistress) in the stable matching M. Let next M( m ) be the husband of s M ( m ); that is, next M ( m ) is m’s most likely cuckoldee. A rotation &rgr; is given by &rgr; ( m 0 , w 0 ) , ( m 1 , w1 ) ,..., ( m r - 1 , w r -1 ) where m i + 1 is cuckolded by m i and m 0 is cuckolded by m r - 1. If m i lost wife w i to m i - 1 then his next wife would be w i + 1. Rotations are driven by women as they rotate to mates they prefer over their previous mates. In contrast, the men rotate to mates they prefer less. Rotations express the minimal differences between stable matches. The rotation poset of ℳ, π ℳ, is a partial order on the rotations of ℳ.
Chapter 3 shows that stable matching problems can be efficiently mapped to linear programming problems. The stable marriage problem and the minimum s-t cut problem are structurally equivalent.
Chapter 4 discusses the roommates problem. The most striking difference between stable marriage and the roommates problem is that the latter is not always solvable. A stable marriage instance of the problem can be transformed to a stable roommates instance by appending to the end of each participant’s preference list all the other members of the same sex (in arbitrary order).
The appendix presents a variety of interesting open questions and conjectures. The bibliography is a comprehensive list of 126 items. The “Index to First Use of Major Notation” was handy, and I appreciated it. The index is too sparse.
This volume is very well written and contains good examples. It could even have been a good textbook for part of an algorithms course if the authors had included an appropriate set of exercises. The authors have served interested students and the scholarly community well. If you are interested in stable matching problems, you should get this book. Despite some omissions, it contains almost everything you ever wanted to know about the stable marriage problem.
