论文标题
在词典偏好下，多个合作伙伴匹配问题的强核和帕累托最佳解决方案
Strong core and Pareto-optimal solutions for the multiple partners matching problem under lexicographic preferences
论文作者
论文摘要
在匹配问题的多个合作伙伴中，代理商可以使多个合作伙伴达到其能力。在本文中，我们考虑了双面多面的稳定匹配问题，也考虑了在词典偏好下的单方面稳定固定装置问题。我们从计算的角度研究了这种设置的强核和帕累托最佳解决方案。首先，我们提供一个例子，以表明即使在这些严重的限制下，强大的核心也可以空无一人，而决定强核的非空置性是NP-HARD。我们还表明，对于给定的匹配检查帕累托（Pareto）截然不同性，强大的核心属性是多到多个问题的共同完全问题，并且决定存在完整的帕托托（Pareto）优化匹配也是固定装置问题的NP-HARD。在正面，我们提供了有效的算法来找到几乎可行的强核解决方案，在每个代理商中，最多只能侵犯一个容量，并且还可以在分数匹配的强核中找到半匹配。这些多项式时间算法基于顶级交易周期算法。最后，我们还表明，对于多到多个问题，找到最大尺寸匹配的帕累托最佳匹配可以有效地完成，这与固定装置问题的硬度结果相反。
In a multiple partners matching problem the agents can have multiple partners up to their capacities. In this paper we consider both the two-sided many-to-many stable matching problem and the one-sided stable fixtures problem under lexicographic preferences. We study strong core and Pareto-optimal solutions for this setting from a computational point of view. First we provide an example to show that the strong core can be empty even under these severe restrictions for many-to-many problems, and that deciding the non-emptiness of the strong core is NP-hard. We also show that for a given matching checking Pareto-optimality and the strong core properties are co-NP-complete problems for the many-to-many problem, and deciding the existence of a complete Pareto-optimal matching is also NP-hard for the fixtures problem. On the positive side, we give efficient algorithms for finding a near feasible strong core solution, where the capacities are only violated by at most one unit for each agent, and also for finding a half-matching in the strong core of fractional matchings. These polynomial time algorithms are based on the Top Trading Cycle algorithm. Finally, we also show that finding a maximum size matching that is Pareto-optimal can be done efficiently for many-to-many problems, which is in contrast with the hardness result for the fixtures problem.
