The Stable Marriage Problem

Title
Contents
Series Foreword
Preface
Chapter 1: Elementary Concepts and Results
1.1. Introduction
1.2. The Gale-Shapley Algorithm
1.3. The Set of Stable Matchings
1.4. Some Simple Extensions of Stable Marriage
1.5. Lower Bounds for Stable Marriage
1.6. The Hospitals/Residents Problem
1.7. Deceit, Coalitions, and Strategy
1.8. Notes and References
Chapter 2: The Structure and Representation of All Stable Matchings
2.1. Introduction
2.2. A Simple Compact Representation
2.3. Generalization to a Ring of Sets
2.4. Representing a Ring of Sets by Set Differences
2.5. Representing the Stable Matchings by Differences
2.6. Notes and References
Chapter 3: Building and Exploiting the Representation of All Stable Matchings
3.1. Introduction
3.2. Constructing the Rotation Poset
3.3. Efficient Construction
3.4. Three Problems with "Easy" Solutions
3.5. Efficient Enumeration of All Stable Matchings
3.6. Finding Fair Stable Matchings
3.7. Linear Programming and Stable Marriage
3.8. Equivalent Structures and Problems
3.9. NP-Hardness
3.10. Notes and References
Chapter 4: The Stable Roommates Problem
4.1. Introduction
4.2. The Stable Roommates Algorithm
4.3. Structure of Roommates Matchings
4.4. Exploiting the Structure
4.5. Variations and Extensions
4.6. Notes and References
Appendix: Open Problems
Bibliography
Index to First Use of Major Notation
Index