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?
The question whether the stable marriage theorem can be generalized to three classes already appeared in Knuth's book . The cyclic version described above was first mentioned by Ng and Hirschberg  as an open problem. This cyclic version can also be considered as a special case of the 3-way stable 3-way exchange problem.
On the negative side, Biró and McDermid  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  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.
- 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