Contents -- Preface -- Foreword -- Acknowledgments -- List of Figures -- List of Tables -- List of Algorithms -- 1. Preliminary definitions, results and motivation -- 1.1 Introduction -- 1.1.1 Remit of this book -- 1.1.1.1 Matching under preferences -- 1.1.1.2 Free-for-all markets -- 1.1.1.3 Centralised matching schemes -- 1.1.2 The matching problems under consideration -- 1.1.2.1 Classification of matching problems -- 1.1.2.2 Bipartite matching problems with two-sided preferences -- 1.1.2.3 Bipartite matching problems with one-sided preferences -- 1.1.2.4 Non-bipartite matching problems with preferences -- 1.1.2.5 Further problem variants -- 1.1.3 Existing literature on matching problems -- 1.1.3.1 Algorithms and complexity literature -- 1.1.3.2 Game theory and economics literature -- 1.1.3.3 Algorithmic mechanism design literature -- 1.1.4 Contribution of this book -- 1.1.4.1 General overview -- 1.1.4.2 Chapter outline -- 1.1.4.3 What the book does not contribute -- 1.1.5 Outline of this chapter -- 1.2 Matchings in graphs -- 1.3 The Hospitals / Residents problem (hr) -- 1.3.1 Introduction -- 1.3.2 Key definitions -- 1.3.3 Key results (up to 1989) -- 1.3.4 Stable Marriage problem (sm) -- 1.3.4.1 Key definitions -- 1.3.4.2 Key results (up to 1989) -- 1.3.4.3 Rotations -- 1.3.5 Hospitals / Residents problem with indifference -- 1.3.6 Other variants of hr -- 1.3.6.1 Couples -- 1.3.6.2 Many-many stable matchings -- 1.3.6.3 Master lists -- 1.3.7 Motivation -- 1.4 The Stable Roommates problem (sr) -- 1.4.1 Introduction -- 1.4.2 Key definitions -- 1.4.3 Key results (up to 1989) -- 1.4.4 Rotations -- 1.4.5 Stable Roommates problem with indifference -- 1.4.6 Motivation -- 1.5 The House Allocation problem (ha) and its variants -- 1.5.1 Introduction -- 1.5.2 Formal definition of ha and hm -- 1.5.3 Pareto optimal matchings -- 1.5.4 Maximum utility matchings.

1.5.5 Popular matchings -- 1.5.6 Profile-based optimal matchings -- 1.5.7 Extensions of ha -- 1.5.8 Motivation -- Stable Matching Problems -- 2. The Stable Marriage problem: An update -- 2.1 Introduction -- 2.2 The 12 open problems of Gusfield and Irving -- 2.2.1 Introduction -- 2.2.2 1. Maximum number of stable matchings -- 2.2.3 2. The "divorce digraph" -- 2.2.4 3. Parallel algorithms for stable marriage -- 2.2.5 4. Batch stability testing -- 2.2.6 5. Structure of stable marriage with ties -- 2.2.7 6. Sex-equal matching -- 2.2.8 7. Lying and egalitarian matchings -- 2.2.9 10. Succinct certificates -- 2.2.10 11. Algorithmic improvements -- 2.3 The Subramanian and Feder papers -- 2.3.1 Subramanian: sri and network stability -- 2.3.2 Feder: sri and 2-sat -- 2.3.3 Other fixed-point approaches -- 2.4 Linear programming approaches -- 2.5 Constraint programming approaches -- 2.5.1 Introduction -- 2.5.2 Preliminaries -- 2.5.3 Overview of the csp model -- 2.5.4 Arc consistency in the csp model -- 2.6 Paths to stability -- 2.6.1 Introduction -- 2.6.2 The Roth-Vande Vate Mechanism -- 2.6.3 The Random Order Mechanism -- 2.6.4 Other decentralised algorithms -- 2.7 Median stable matchings -- 2.8 Size versus stability -- 2.9 Strategic issues -- 2.10 Further results -- 2.10.1 Stable Marriage problem with Forbidden pairs -- 2.10.2 Balanced stable matchings -- 2.10.3 Rationalizing matchings -- 2.10.4 Dinitz conjecture and stable marriage theory -- 2.10.5 The marriage graph -- 2.10.6 Sampling and counting -- 2.10.7 Online algorithms -- 2.10.8 Finding "good" stable matchings: unified approach -- 2.10.9 Locally stable matchings -- 2.10.10 Miscellaneous results -- 2.11 Conclusions and open problems -- 3. SM and HR with indifference -- 3.1 Introduction -- 3.2 Weak stability -- 3.2.1 Existence of a weakly stable matching -- 3.2.2 Absence of a lattice structure.

3.2.3 Sizes of weakly stable matchings -- 3.2.4 NP-hardness of max smti -- 3.2.5 Parameterized complexity of max smti -- 3.2.6 Approximability of max smti and max hrt -- 3.2.6.1 Overview of approximability results for max smti -- 3.2.6.2 Kiraly's approximation algorithm -- 3.2.6.3 Comparison of approximation algorithms for max smti -- 3.2.6.4 Heuristics for max hrt -- 3.2.6.5 "Cloning" hospitals -- 3.2.7 Other problems involving weak stability -- 3.3 Strong stability -- 3.3.1 Existence of a strongly stable matching -- 3.3.2 Rural Hospitals Theorem for hrt -- 3.3.3 Strongly stable matchings form a lattice -- 3.3.4 Finding a strongly stable matching -- 3.4 Super-stability -- 3.4.1 Existence of a super-stable matching -- 3.4.2 Rural Hospitals Theorem for hrt -- 3.4.3 Super-stable matchings form a lattice -- 3.4.4 Finding a super-stable matching -- 3.4.5 Optimal super-stable matchings -- 3.5 Other results -- 3.5.1 Semi-strong stability -- 3.5.2 Many-many strongly stable matchings -- 3.5.3 Partially-ordered preference lists -- 3.6 Conclusions and open problems -- 4. The Stable Roommates problem -- 4.1 Introduction -- 4.2 Updates to open problems 8-12 from Gusfield & Irving -- 4.2.1 8: Solvable Roommates Instances -- 4.2.2 9: Roommates to Marriage -- 4.2.3 10: Succinct Certificates -- 4.2.4 11: Algorithmic Improvements -- 4.2.5 12: Optimal Roommates -- 4.2.6 12.1: Linear Programming for Roommates -- 4.3 Stable partitions -- 4.3.1 Introduction -- 4.3.2 Definition and structure of stable partitions -- 4.3.3 Algorithms for finding a stable partition -- 4.3.4 Maximum stable matchings -- 4.3.5 Stable half-matchings -- 4.3.6 P-stable matchings and absorbing sets -- 4.4 Mirror posets and median graphs -- 4.5 Indifference -- 4.5.1 Introduction -- 4.5.2 Weakly stable matchings -- 4.5.3 Strongly stable matchings -- 4.5.4 Super-stable matchings.

4.6 "Almost stable" matchings -- 4.6.1 Introduction -- 4.6.2 Hardness results -- 4.6.3 Matchings with a constant no. of blocking pairs -- 4.6.4 Bounded length preference lists -- 4.6.5 Open problems -- 4.7 Globally-ranked pairs -- 4.7.1 Definitions and motivation for the srti-grp model -- 4.7.2 Globally acyclic preferences -- 4.7.3 Weakly / strongly stable matchings in srti-grp -- 4.7.4 Related work -- 4.8 Other extensions of sr -- 4.8.1 Introduction -- 4.8.2 Stable Roommates problem with Forbidden Pairs -- 4.8.3 Stable Crews problem -- 4.8.4 Stable Fixtures problem -- 4.8.5 Stable Multiple Activities problem -- 4.8.6 Stable Allocation problem -- 4.8.7 Stable Roommates problem with Choice Functions -- 4.8.8 Coalition Formation Games -- 4.9 Conclusions and open problems -- 5. Further stable matching problems -- 5.1 Introduction -- 5.2 hr with lower and common quotas -- 5.2.1 Introduction -- 5.2.2 hr with lower quotas (model 1) -- 5.2.3 hr with lower quotas (model 2) -- 5.2.4 hr with common quotas -- 5.2.5 Classified stable matching -- 5.3 hr with couples -- 5.3.1 Introduction -- 5.3.2 Problem definition and preliminary results -- 5.3.3 Algorithmic results -- 5.3.4 Consistent couples -- 5.3.5 Inseparable couples -- 5.4 Many-many stable matching -- 5.4.1 Introduction -- 5.4.2 Definition of the basic wf model -- 5.4.3 wf-1: preferences over individuals -- 5.4.4 wf-2: group preferences -- 5.5 The Student-Project Allocation Problem -- 5.5.1 Introduction -- 5.5.2 Lecturer preferences over students: spa-s -- 5.5.2.1 Introduction -- 5.5.2.2 Overview of Algorithm spa-s-student -- 5.5.2.3 Properties of stable matchings in an instance of spa-s -- 5.5.2.4 Lecturer-oriented algorithm -- 5.5.2.5 Open problems -- 5.5.3 Lecturer preferences over projects -- 5.5.4 Lecturer preferences over student-project pairs -- 5.6 3D stable matching problems.

5.6.1 3D variants of sm -- 5.6.1.1 Strictly-ordered preferences over pairs -- 5.6.1.2 Preferences over pairs with ties -- 5.6.1.3 Lexicographic preferences over pairs of agents -- 5.6.1.4 Preferences over individual agents -- 5.6.2 3D variants of sr -- 5.6.2.1 Strictly-ordered preferences over pairs -- 5.6.2.2 Preference lists over pairs with ties -- 5.6.2.3 Preferences over individual agents -- 5.6.2.4 Three-Way Kidney Transplant -- 5.6.2.5 Geometric 3dsr -- 5.7 Exchange-stable matching problems -- 5.7.1 Exchange-stability as a solution concept -- 5.7.2 Exchange-blocking coalitions -- 5.7.3 Stable matchings that are exchange-stable -- 5.8 Two additional stable matching problems -- 5.8.1 Bistable matching problems -- 5.8.2 The Cycle Stable Roommates problem -- 5.9 Conclusions and open problems -- Other Optimal Matching Problems -- 6. Pareto optimal matchings -- 6.1 Introduction -- 6.2 House Allocation problem -- 6.2.1 Strictly-ordered preferences -- 6.2.1.1 Testing for Pareto optimality -- 6.2.1.2 Maximum Pareto optimal matchings -- 6.2.1.3 Other results for Pareto optimal matchings -- 6.2.1.4 Matchings in the cor -- 6.2.2 Preference lists with ties -- 6.2.2.1 Characterisation of Pareto optimal matchings -- 6.2.2.2 Matchings in the core -- 6.3 Capacitated House Allocation problem -- 6.4 Hospitals / Residents problem -- 6.5 Stable Roommates problem -- 6.5.1 Introduction -- 6.5.2 Preliminary observations -- 6.5.3 Characterising Pareto optimal matchings -- 6.5.4 Maximum Pareto optimal matchings -- 6.5.5 Coalition formation games -- 6.6 Conclusions and open problems -- 7. Popular matchings -- 7.1 Introduction -- 7.2 House Allocation problem -- 7.2.1 Introduction -- 7.2.2 Characterising popular matchings -- 7.2.3 Finding a popular matching -- 7.2.4 Maximum popular matchings -- 7.2.5 Structure of popular matchings -- 7.2.6 Popular matchings in hat.

7.2.7 Matchings with small unpopularity.