|
This article is cited in 1 scientific paper (total in 1 paper)
Instances of small size with no stable matching for three-sided problem with complete cyclic preferences
E. Yu. Lerner Kazan Federal University, 18 Kremlyovskaya str., Kazan, 420008 Russia
Abstract:
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$.
Keywords:
stable marriage, preference matrix, cyclic preferences, directed weighted graph, stable matching, counterexample.
Received: 30.08.2021 Revised: 13.12.2021 Accepted: 23.12.2021
Citation:
E. Yu. Lerner, “Instances of small size with no stable matching for three-sided problem with complete cyclic preferences”, Izv. Vyssh. Uchebn. Zaved. Mat., 2022, no. 6, 26–36; Russian Math. (Iz. VUZ), 66:6 (2022), 20–27
Linking options:
https://www.mathnet.ru/eng/ivm9781 https://www.mathnet.ru/eng/ivm/y2022/i6/p26
|
Statistics & downloads: |
Abstract page: | 97 | Full-text PDF : | 18 | References: | 16 | First page: | 7 |
|