Instances of small size with no stable matching for three-sided problem with complete cyclic preferences

E. Yu. Lerner

Izvestiâ vysših učebnyh zavedenij. Matematika, no. 6 (2022), pp. 26-36.

Résumé

Given $n$ men, $n$ women, and $n$ dogs, each man has a complete preference list of women, while each woman does a complete preference list of dogs, and each dog does a complete preference list of men. We understand a matching as a collection of $n$ nonintersecting triples, each of which contains a man, a woman, and a dog. A matching is said to be nonstable, if one can find a man, a woman, and a dog which belong to different triples and prefer each other to their current partners in the corresponding triples. Otherwise the matching is said to be stable (a weakly stable matching in 3DSM-CYC problem). According to the conjecture proposed by Eriksson, Söstrand, and Strimling (2006), the 3DSM-CYC problem always has a stable matching. However, Lam and Paxton (2019) have proposed an algorithm for constructing preference lists in the 3DSM-CYC problem of size $n=90$, which has allowed them to disprove the mentioned conjecture. The question on the existence of counterexamples of a lesser size remains open. In this paper, we construct an demonstrative instance of the 3DSM-CYC problem with no stable matching, whose size $n=24$.

Détail

Keywords: stable marriage, preference matrix, cyclic preferences, directed weighted graph, stable matching, counterexample.

Bibliographie

[1] Lam C.-K., Plaxton C.G., “On the Existence of Three-Dimensional Stable Matchings with Cyclic Preferences”, Algorithmic Game Theory, Lect. Notes in Comput. Sci., 11801, Springer, 2019, 329–342, arXiv: 1905.02844 | DOI | MR | Zbl

[2] Eriksson K., Söstrand J., Strimling P., “Three-dimensional stable matching with cyclic preferences”, Math. Soc. Sci., 52 (2006), 77–87 | DOI | MR | Zbl

[3] Lerner E.Yu., Lerner R.E., “Minimal instances with no weakly stable matching for three-sided problem with cyclic incomplete preferences.”, Discrete Math., Algorithms and Appl., 2021 (to appear) | DOI

[4] Biró P., McDermid E., “Three-sided stable matchings with cyclic preferences”, Algorithmica, 58 (2010), 5–18 | DOI | MR | Zbl

[5] Gale D., Shapley L.S., “College admissions and the stability of marriage”, Am. Math. Mon., 69 (1962), 9–15 | DOI | MR | Zbl

[6] Knuth D.E., Stable marriage and its relation to other combinatorial problems: an introduction to the mathematical analysis of algorithms, CRM Proceedings and Lecture Notes, 10, American Math. Society, 1996 | DOI | MR | Zbl

[7] Lerner E.Yu., “Sootvetstvie zadach ob ustoichivom parosochetanii i o naznachenii”, Izv. vuzov. Matem., 2011, no. 11, 34–40 | Zbl

[8] Manlove D.F., Algorithmics of matching under preferences, Theor. Comput. Sci., World Sci., 2013 | MR | Zbl

[9] Boros E., Gurvich V., Jaslar S., Krasner D., “Stable matchings in three-sided systems with cyclic preferences”, Discrete Math., 289:1–3 (2004), 1–10 | MR | Zbl

[10] Pashkovich K., Poirrier L. “Three-dimensional stable matching with cyclic preferences”, Optimization Letters, 14 (2020), 2615–2623 | DOI | MR | Zbl

[11] Pittel B., “On random stable matchings: Cyclic ones with strict preferences and two-sided ones with partially ordered preferences”, Advances in Appl. Math., 120:3 (2020), 1–27 | MR

[12] Lerner E.Yu., Instances of small size with no weakly stable matching for three-sided problem with complete cyclic preferences, 2021, arXiv: 2107.10102v1

[13] Blair C., “Every finite distributive lattice is a set of stable matchings”, J. Combinatorial Theory, Ser. A, 37:3 (1984), 353–356 | DOI | MR | Zbl

[14] Gusfield D., Irving R.W., Leather P., Saks M., “Every finite distributive lattice is a set of stable matchings for a small stable marriage instance”, J. Combinatorial Theory, A44 (1987), 304–309 | DOI | MR | Zbl

[15] Irving R.W., Leather P., “The complexity of counting stable marriages”, SIAM J. Computing, 15:3 (1986), 655–667 | DOI | MR | Zbl

[16] Gusfield D., Irving R.W., The Stable Marriage Problem-Structure and Algorithms, The MIT Press, Cambridge, MA, 1989 | MR | Zbl

[17] Danilov V.I., “Existence of stable matchings in some three-sided systems”, Math. Social Sci., 46:2 (2003), 145–148 | DOI | MR | Zbl