论文标题
偏好下的分数匹配：稳定性和最佳性
Fractional Matchings under Preferences: Stability and Optimality
论文作者
论文摘要
我们彻底研究了经典稳定婚姻和稳定的室友问题的广义版本，代理商可能会分享合作伙伴。我们考虑了两个突出的稳定概念：序稳定性[Aharoni和Fleiner，《组合理论杂志》，2003年]和基本稳定性[Caragiannis等人，ACM EC 2019]和两个最佳标准：最大化社会福利（即，特工的整体满意度），并最大程度地提高匹配的成本（即最大程度地匹配的代理人）（即，其代理人）（即，均为符合人数）（即，均为代理人），即。在观察到始终存在并意味着基本稳定性的情况下，并且在有限的情况下，一组稳定的匹配允许晶格结构，我们获得了有关找到最佳的顺序稳定或心脏稳定匹配的计算复杂性的完整图片。在此过程中，我们回答了Caragiannis等人提出的一个公开问题。 [AIJ 2020]。
We thoroughly study a generalized version of the classic Stable Marriage and Stable Roommates problems where agents may share partners. We consider two prominent stability concepts: ordinal stability [Aharoni and Fleiner, Journal of Combinatorial Theory, 2003] and cardinal stability [Caragiannis et al., ACM EC 2019] and two optimality criteria: maximizing social welfare (i.e., the overall satisfaction of the agents) and maximizing the number of fully matched agents (i.e., agents whose shares sum up to one). After having observed that ordinal stability always exists and implies cardinal stability, and that the set of ordinally stable matchings in a restricted case admits a lattice structure, we obtain a complete picture regarding the computational complexity of finding an optimal ordinally stable or cardinally stable matching. In the process we answer an open question raised by Caragiannis et al. [AIJ 2020].
