Cyclic stable matchings

From Egres Open
Jump to: navigation, search

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

  1. 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
  2. C. Ng, D. S. Hirschberg, Three-dimensional stable matching problems, SIAM J. Discrete Math. 4 (1991), 245–252. DOI link
  3. 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
  4. K. Eriksson, J. Sjöstrand, P. Strimling, Three-dimensional stable matching with cyclic preferences, Math. Soc. Sci. 52 (2006), 77–87. DOI link
  5. P. Biró, E. McDermid, Three-sided stable matchings with cyclic preferences, Algorithmica, DOI link
  6. L. Farczadi, K. Georgiou, J. Könemann, Stable marriage with general preferences, arXiv link