Two's Company, Three's a Crowd: Stable Family and Threesome Roommates Problems

stable matchings. In the stable family problem, sets of
women, men, and dogs are given, all of whom state their preferences
among the other two groups. The goal is to organize them into family units, so that no three of them have the incentive to desert
their assigned family members to form a new family.
A similar problem, called the threesome roommates problem, assumes that a group of persons, each with their preferences among the combinations of two others, are to be partitioned into triples. Similarly,
the goal is to make sure that no three persons want to break up
with their assigned roommates.

Ng and Hirschberg were the first to investigate these two problems.
In their formulation, each participant provides a
strictly-ordered list of all combinations. They proved that under
this scheme, both problems are NP-complete. Their paper reviewers
pointed out that their reduction exploits \emph{inconsistent}
preference lists and they wonder whether these two problems
remain NP-complete if preferences are required to be consistent.
We answer in the affirmative.

In order to give these two problems a broader outlook, we also
consider the possibility that participants can express indifference,
on the condition that the preference consistency has to be maintained.
As an example, we propose a scheme in which all participants
submit two (or just one in the roommates case) lists ranking
the other two groups separately. The order of the combinations
is decided by the sum of their ordinal numbers. Combinations
are tied when the sums are equal. By introducing indifference,
a hierarchy of stabilities can be defined. We prove that all
stability definitions lead to NP-completeness for existence
of a stable matching.