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?
A counterexample was found by Chi-Kit Lam and C. Gregory Plaxton [1]. Furthermore, they show that it is NP-complete to decide if a cyclic stable matching exists.
Remarks
The question whether the stable marriage theorem can be generalized to three classes already appeared in Knuth's book [2]. The cyclic version described above was first mentioned by Ng and Hirschberg [3] 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. [4] proved that the conjecture is true if the size of each group is at most 3. Eriksson et al.[5] extended this to the case when each group has size 4.
On the negative side, Biró and McDermid [6] 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 [7] 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
- ↑ C.-K. Lam, C. G. Plaxton, On the Existence of Three-Dimensional Stable Matchings with Cyclic Preferences, 2019, arXiv link
- ↑ 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
