Pairwise Preferences in the Stable Marriage Problem
Pairwise Preferences in the Stable Marriage Problem
复制标题
稳定婚姻问题中的配对偏好
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Attila Juhos
中科院分区：
文献类型：
--
作者：
Ágnes Cseh;Attila Juhos
我们研究了两种偏好下经典的双边稳定婚姻问题。在最一般的情况下，代理人被允许将他们的偏好表达为对他们的任何两个优势的比较，他们也有权宣布平局，甚至退出这样的比较。随着我们在偏好中指定六个有序阶段，这种自由逐渐受到限制，以严格有序列表的经典情况结束。我们研究了当结合三个已知的稳定性概念-弱、强和超稳定性-在假设两方市场的每一方都获得六个有序程度之一的情况下发生的所有情况。通过设计三个多项式算法和两个NP-完备性证明，我们确定了所有未知情况的复杂性，从而给出了易处理和难处理情况之间偏好结构的精确边界。
We study the classical, two-sided stable marriage problem under pairwise preferences. In the most general setting, agents are allowed to express their preferences as comparisons of any two of their edges, and they also have the right to declare a draw or even withdraw from such a comparison. This freedom is then gradually restricted as we specify six stages of orderedness in the preferences, ending with the classical case of strictly ordered lists. We study all cases occurring when combining the three known notions of stability—weak, strong, and super-stability—under the assumption that each side of the bipartite market obtains one of the six degrees of orderedness. By designing three polynomial algorithms and two NP-completeness proofs, we determine the complexity of all cases not yet known and thus give an exact boundary in terms of preference structure between tractable and intractable cases.