- Код статьи
- S0044466925010114-1
- DOI
- 10.31857/S0044466925010114
- Тип публикации
- Статья
- Статус публикации
- Опубликовано
- Авторы
- Том/ Выпуск
- Том 65 / Номер выпуска 1
- Страницы
- 120-138
- Аннотация
- В работе рассматривается модель стабильных реберных подмножеств (“матчингов”) в двудольном графе G = (V, E), в котором предпочтения для вершин одной доли (“фирм”) задаются при помощи функций выбора со стандартными свойствами консистентности, заменяемости и кардинальной монотонности, а предпочтения для вершин другой доли (“работников”) – при помощи линейных порядков. Для такой модели дается комбинаторное описание структуры ротаций и предлагается алгоритм построения посета ротаций с оценкой временн´ой сложности O(|E|2) (включая обращения к оракулам, связанных с функциями выбора). Как следствие, можно получить “компактное” аффинное представление стабильных матчингов и эффективно решать смежные задачи. Библ. 21.
- Ключевые слова
- двудольный граф функция выбора линейные предпочтения стабильный матчинг аффинная представимость последовательный выбор
- Дата публикации
- 17.09.2025
- Год выхода
- 2025
- Всего подписок
- 0
- Всего просмотров
- 25
Библиография
- 1. Gale D. and Shapley L.S. College admissions and the stability of marriage // Amer. Math. Monthly 69 (1) (1962) 9–15.
- 2. Gusfield D. and Irving R.W. The stable marriage problem: structure and algorithms, MIT press, 1989.
- 3. Manlove D. Algorithmics of matching under preferences, Vol. 2, World Scientific, 2013.
- 4. Kelso A.S. and Crawford V.P. Job matching, coalition formation and gross substitutes // Econometrica 50 (1982) 1483–1504.
- 5. Roth A.E. Stability and polarization of interests in job matching // Econometrica 52 (1984) 47–57.
- 6. Blair C. The lattice structure of the set of stable matchings with multiple partners // Math. Oper. Res. 13 (1988) 619–628.
- 7. Plott C.R. Path independence, rationality, and social choice // Econometrica 41 (6) (1973) 1075–1091.
- 8. Alkan A. On preferences over subsets and the lattice structure of stable matchings // Review of Economic Design 6 (1) (2001) 99–111.
- 9. Alkan A. A class of multipartner matching models with a strong lattice structure // Econom. Theory 19 (2002) 737–746.
- 10. Birkhoff G. Rings of sets // Duke Mathematical Journal 3 (3) (1937) 443–454.
- 11. Irving R.W. and Leather P. The complexity of counting stable marriages. SIAM J. Comput. 15 (1986) 655–667.
- 12. Irving R.W., Leather P. and Gusfield D. An efficient algorithm for the optimal stable marriage problem // J. ACM 34 (1987) 532–543.
- 13. Picard J. Maximum closure of a graph and applications to combinatorial problems // Manage. Sci. 22 (1976) 1268–1272.
- 14. Faenza Yu. and Zhang X. Affinely representable lattices, stable matchings, and choice functions. ArXiv:2011.06763v2[math.CO], 2021.
- 15. Stanley R.P. Two poset polytopes. Discrete and Computational Geometry 1 (1) (1986) 9–23.
- 16. Danilov V.I. Sequential choice functions and stability problems. ArXiv:2401.00748v2 [math.CO], 2024.
- 17. Alkan A. and Gale D. Stable schedule matching under revealed preference. J. Economic Theory 112 (2003) 289–306.
- 18. Aizerman M. and Malishevski A. General theory of best variants choice: Some aspects // IEEE Transactions on Automatic Control 26 (5) (1981) 1030–1040.
- 19. Cechlarova K. and Fleiner T. On a generalization of a stable roommates problem. EGREST Technical Report No. 2003–03, 2003.
- 20. Mourtos I. and Samaris M. Stable allocations and partially ordered sets // Discrete Optimization 46 (2022) 100731.
- 21. Karzanov A.V. On stable assignments generated by choice functions of mixed type // Discrete Applied Math. 358 (2024) 112–135, https://doi.org/10.1016/j.dam.2024.06.037.
