| Форма представления | Статьи в зарубежных журналах и сборниках |
| Год публикации | 2023 |
| Язык | английский |
|
Лернер Эдуард Юльевич, автор
|
|
Лернер Регина Эдуардовна, автор
|
| Библиографическое описание на языке оригинала |
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 |
| Аннотация |
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]. |
| Ключевые слова |
incomplete preferences lists, three-sided problem, cycles, weighted directed graphs |
| Название журнала |
Discrete Mathematics, Algorithms and Applications
|
| Ссылка для РПД |
http://dspace.kpfu.ru/xmlui/bitstream/handle/net/175691/3DSM3incomplete4.pdf?sequence=1&isAllowed=y
|
| URL |
https://www.worldscientific.com/doi/10.1142/S1793830922500951 |
| Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на эту карточку |
https://repository.kpfu.ru/?p_id=278431 |
| Файлы ресурса | |
|
|
Полная запись метаданных  |
| Поле DC |
Значение |
Язык |
| dc.contributor.author |
Лернер Эдуард Юльевич |
ru_RU |
| dc.contributor.author |
Лернер Регина Эдуардовна |
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/?p_id=278431 |
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 |
Статьи в зарубежных журналах и сборниках |
ru_RU |
|
EN 
中文 
ES 
Карта сайта
