Strong core and Pareto-optimality in the multiple partners matching problem under lexicographic preference domains

• 成果类型: Article
• 署名作者: Biro, Peter; Csaji, Gergely
• 署名单位: Corvinus University Budapest; Eotvos Lorand University
• 刊物名称: GAMES AND ECONOMIC BEHAVIOR
• ISSN/ISSBN: 0899-8256
• DOI: 10.1016/j.geb.2024.03.010
• 发表日期: 2024
• 页码: 217-238
• 关键词: Stable matchings; many-to-many matching; Lexicographic preferences; core; Computation complexity

摘要

We study strong core and Pareto-optimal solutions for multiple partners matching problem under lexicographic preference domains from a computational point of view. The restriction to the two-sided case is called stable many -to -many matching problem and the general one-sided case is called stable fixtures problem. We provide an example to show that the strong core can be empty even for many -to -many problems, and that deciding the non -emptiness of the strong core is NP -hard. On the positive side, we give efficient algorithms for finding a near feasible strong core solution and for finding a fractional matching in the strong core of fractional matchings. In contrast with the NP -hardness result for the stable fixtures problem, we show that finding a maximum size matching that is Pareto-optimal can be done efficiently for many -to -many problems. Finally, we show that for reverse -lexicographic preferences the strong core is always non -empty in the many -to -many case.