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.
翻译:在多个伙伴匹配问题的情况下, 代理商可以拥有与其能力相匹配的多个伙伴。 在本文中, 我们既考虑双向多个稳定匹配问题, 也考虑在地名录偏好下单向稳定固定装置问题。 我们从计算角度研究这一设置的强核心和最佳最佳最佳最佳最佳最佳方案。 首先, 我们提供了一个示例, 以显示强核心即使在这些对许多至许多问题的严格限制下也可以是空的, 并且决定强核心的不安全性是坚固的。 我们还在本文中看到, 一个匹配的匹配Pareto- 最优化的匹配问题和强核心特性是共同的。 我们从计算角度来研究这个设置的全核心和Pareto- 最佳最佳匹配办法的存在也是难的。 在正面方面, 我们给出了高效的算法, 找到一个几乎可行的强大核心解决办法, 每个代理商最多一个单位的能力都受到破坏, 以及找到一个匹配硬核心部分的匹配的半匹配点。 这些极核心特性是共同完成的问题, 这些多端- 交易最高级的算法也是基于最高级的路径算法。