# Cyclic stable matchings

We are given three equal-sized groups of individuals: dogs, men, and women. Each dog has a strict preference order of the men; each man has a strict preference order of the women; and finally, each woman has a strict preference order of the dogs. We want to partition them into dog-man-woman triplets, so that there is no **blocking triplet** (a triplet not in the partition, where each member strictly prefers its/his/her partner in the triplet to its/his/her partner in the partition). Does such a partitioning always exist?

## Remarks

The question whether the stable marriage theorem can be generalized to three classes already appeared in Knuth's book ^{[1]}. The cyclic version described above was first mentioned by Ng and Hirschberg ^{[2]} as an open problem. This cyclic version can also be considered as a special case of the 3-way stable 3-way exchange problem.

Boros et al. ^{[3]} proved that the conjecture is true if the size of each group is at most 3. Eriksson et al.^{[4]} extended this to the case when each group has size 4.

On the negative side, Biró and McDermid ^{[5]} showed that the problem becomes NP-complete if the preference lists are allowed to be incomplete (i.e. each dog/man/woman has a set of acceptable partners). They also considered the following "strongly stable" version of the conjecture. A triplet is **weakly blocking** if it is not in the partition, and each member either prefers its/his/her partner in the triplet to its/his/her partner in the partition, or its/his/her partner in the triplet is the same as in the partition. If there is no weakly blocking triplet, the partition is called **strongly stable**. Biró and McDermid showed that a strongly stable partition does not always exist, and it is NP-complete to decide if it exists.

Farczadi, Georgiou, and Könemann ^{[6]} proved that if we fix a perfect matching on dogs and men, then it is NP-complete to decide if this matching can be extended to a stable partition of triplets.

## References

- ↑ D. E. Knuth,
*Mariages Stables et leurs relations avec d'autres problèmes combinatoires*, Les Presses de l'Université de Montréal, 1976, French. Full text in pdf - ↑ C. Ng, D. S. Hirschberg,
*Three-dimensional stable matching problems*, SIAM J. Discrete Math. 4 (1991), 245–252. DOI link - ↑ E. Boros, V. Gurvich, S. Jaslar, D. Krasner,
*Stable matchings in three-sided systems with cyclic preferences*, Discrete Math. 289 (2004), 1–10.DOI link - ↑ K. Eriksson, J. Sjöstrand, P. Strimling,
*Three-dimensional stable matching with cyclic preferences*, Math. Soc. Sci. 52 (2006), 77–87. DOI link - ↑ P. Biró, E. McDermid,
*Three-sided stable matchings with cyclic preferences*, Algorithmica, DOI link - ↑ L. Farczadi, K. Georgiou, J. Könemann,
*Stable marriage with general preferences*, arXiv link