KFU. Card publication. Minimal instances with no weakly stable matching for three-sided problem with cyclic incomplete preferences

KAZAN
FEDERAL UNIVERSITY

- RUS
- 中文
- ES

MINIMAL INSTANCES WITH NO WEAKLY STABLE MATCHING FOR THREE-SIDED PROBLEM WITH CYCLIC INCOMPLETE PREFERENCES

Form of presentation

Articles in international journals and collections

Year of publication

2023

��

��

Authors, employees of KFU

Lerner Eduard Yulevich, author

Other authors

Lerner Regina Eduardovna, author

Bibliographic description in the original language

Lerner E. Yu. Minimal instances with no weakly stable matching for three-sided problem with cyclic incomplete preferences / E. Yu. Lerner, R. E. Lerner / Discrete Mathematics, Algorithms and Applications. - 2023. - Vol. 15. - No. 03, 2250095. https://doi.org/10.1142/S1793830922500951

Annotation

Given n men, n women, and n dogs, each man has an incomplete preference list of women, each woman has an incomplete preference list of dogs, and each dog has an incomplete preference list of men. We understand a family as a triple consisting of one man, one woman, and one dog such that the dog belongs to the preference list of the woman, who, in turn, belongs to the preference list of the man, while the latter belongs to the preference list of the dog. We understand a matching as a collection of nonintersecting families (some agents, possibly, remain single). A matching is said to be nonstable, if one can find a man, a woman, and a dog who do not live together currently but each of them would become “happier” if they do. Otherwise, the matching is said to be stable (a weakly stable matching). We give an example of this problem for 𝑛=3 where no stable matching exists. Moreover, we prove the absence of such an example for 𝑛<3. Such an example was known earlier only for 𝑛=6 [P. Biró and E. McDermid, Three-sided stable matchings with cyclic preferences, Algorithmica 58 (2010) 5–18]. The constructed examples also allow one to halve the size of the recently constructed analogous example for complete preference lists [C.-K. Lam and C.G. Plaxton, On the existence of three-dimensional stable matchings with cyclic preferences, in Algorithmic Game Theory, Lecture Notes in Computer Science, Vol. 11801 (Springer, 2019), pp. 329–342].

Keywords

incomplete preferences lists, three-sided problem, cycles, weighted directed graphs

The name of the journal

Discrete Mathematics, Algorithms and Applications

On-line resource for training course

http://dspace.kpfu.ru/xmlui/bitstream/handle/net/175691/3DSM3incomplete4.pdf?sequence=1&isAllowed=y

URL

https://www.worldscientific.com/doi/10.1142/S1793830922500951

Please use this ID to quote from or refer to the card

https://repository.kpfu.ru/eng/?p_id=278431&p_lang=2

Resource files

File name	Size (MB)	Format
3DSM3incomplete4.pdf	0,29	pdf	show / download

Full metadata record

Field DC	Value	Language
dc.contributor.author	Lerner Eduard Yulevich	ru_RU
dc.contributor.author	Lerner Regina Eduardovna	ru_RU
dc.date.accessioned	2023-01-01T00:00:00Z	ru_RU
dc.date.available	2023-01-01T00:00:00Z	ru_RU
dc.date.issued	2023	ru_RU
dc.identifier.citation	Lerner E. Yu. Minimal instances with no weakly stable matching for three-sided problem with cyclic incomplete preferences / E. Yu. Lerner, R. E. Lerner / Discrete Mathematics, Algorithms and Applications. - 2023. - Vol. 15. - No. 03, 2250095. https://doi.org/10.1142/S1793830922500951	ru_RU
dc.identifier.uri	https://repository.kpfu.ru/eng/?p_id=278431&p_lang=2	ru_RU
dc.description.abstract	Discrete Mathematics, Algorithms and Applications	ru_RU
dc.description.abstract	Given n men, n women, and n dogs, each man has an incomplete preference list of women, each woman has an incomplete preference list of dogs, and each dog has an incomplete preference list of men. We understand a family as a triple consisting of one man, one woman, and one dog such that the dog belongs to the preference list of the woman, who, in turn, belongs to the preference list of the man, while the latter belongs to the preference list of the dog. We understand a matching as a collection of nonintersecting families (some agents, possibly, remain single). A matching is said to be nonstable, if one can find a man, a woman, and a dog who do not live together currently but each of them would become “happier” if they do. Otherwise, the matching is said to be stable (a weakly stable matching). We give an example of this problem for 𝑛=3 where no stable matching exists. Moreover, we prove the absence of such an example for 𝑛<3. Such an example was known earlier only for 𝑛=6 [P. Biró and E. McDermid, Three-sided stable matchings with cyclic preferences, Algorithmica 58 (2010) 5–18]. The constructed examples also allow one to halve the size of the recently constructed analogous example for complete preference lists [C.-K. Lam and C.G. Plaxton, On the existence of three-dimensional stable matchings with cyclic preferences, in Algorithmic Game Theory, Lecture Notes in Computer Science, Vol. 11801 (Springer, 2019), pp. 329–342].	ru_RU
dc.language.iso	ru	ru_RU
dc.subject	incomplete preferences lists	ru_RU
dc.subject	three-sided problem	ru_RU
dc.subject	cycles	ru_RU
dc.subject	weighted directed graphs	ru_RU
dc.title	Minimal instances with no weakly stable matching for three-sided problem with cyclic incomplete preferences	ru_RU
dc.type	Articles in international journals and collections	ru_RU