The Stable Marriage Problem

Description

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