Some things couples always wanted to know about stable matchings (but were afraid to ask)

It is well-known that couples that look jointly for jobs in the same centralized labor market may cause instabilities. We demonstrate that for a natural preference domain for couples, namely the domain of responsive preferences, the existence of stable matchings can easily be established. However, a small deviation from responsiveness in one couple's preference relation that models the wish of a couple to be closer together may already cause instability. This demonstrates that the nonexistence of stable matchings in couples markets is not a singular theoretical irregularity. Our nonexistence result persists even when a weaker stability notion is used that excludes myopic blocking. Moreover, we show that even if preferences are responsive there are problems that do not arise for singles markets. Even though for couples markets with responsive preferences the set of stable matchings is nonempty, the lattice structure that this set has for singles markets does not carry over. Furthermore we demonstrate that the new algorithm adopted by the National Resident Matching Program to fill positions for physicians in the United States may cycle, while in fact a stable matchings does exist, and be prone to strategic manipulation if the members of a couple pretend to be single.