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