Stable matching with uncertain pairwise preferences
Stable matching with uncertain pairwise preferences
复制标题
具有不确定的成对偏好的稳定匹配
DOI：
10.1016/j.tcs.2022.01.028
复制
发表时间：
2022
影响因子：
1.1
通讯作者：
Aziz H
中科院分区：
文献类型：
--
作者：
Aziz H
我们研究了一个双边匹配问题，其中代理人对他们可能的伙伴有独立的成对偏好，而这些偏好可能是不确定的。在这种情况下，代理人偏好的肯定首选部分可能会进入一个周期，甚至可能不存在以非零概率稳定的匹配。我们集中于检验可能稳定的匹配和确定稳定的匹配的存在性的计算问题，即稳定概率分别为正和1的匹配。我们证明了找到一个可能稳定的匹配是NP困难的，即使只有一方可以有循环偏好。另一方面，我们证明了当只有一方有循环偏好而另一方有传递偏好时，找到一个确定稳定的匹配问题是多项式时间可解的，但当双方都有循环偏好时，这个问题就变成了NP难问题。后者的复杂性结果也意味着在一类特殊的有向图中寻找核的难度。
We study a two-sided matching problem where the agents have independent pairwise preferences on their possible partners and these preferences may be uncertain. In this case, the certainly preferred part of an agent’s preferences may admit a cycle and there may not even exist a matching that is stable with non-zero probability. We focus on the computational problems of checking the existence of possibly and certainly stable matchings, ie, matchings whose probability of being stable is positive or one, respectively. We show that finding a possibly stable matching is NP-hard, even if only one side can have cyclic preferences. On the other hand we show that the problem of finding a certainly stable matching is polynomial-time solvable if only one side can have cyclic preferences and the other side has transitive preferences, but that this problem becomes NP-hard when both sides can have cyclic preferences. The latter complexity result also implies the hardness of finding a kernel in a special class of directed graphs.
登录
查看更多内容
DOI：
--
发表时间：
2014
期刊：
ACM Conference on Economics and Computation
影响因子：
--
作者：
Baharak Rastegari;A. Condon;Nicole Immorlica;Robert W. Irving;Kevin Leyton
通讯作者：
Kevin Leyton
偏好不确定下的帕累托最优配置
DOI：
--
发表时间：
2016
期刊：
Adaptive Agents and Multi-Agent Systems
影响因子：
--
作者：
H. Aziz;Ronald de Haan;Baharak Rastegari
通讯作者：
Baharak Rastegari
影响因子：
1.1
作者：
H. Aziz;P. Biró;Serge Gaspers;Ronald de Haan;Nicholas Mattei;Baharak Rastegari
通讯作者：
H. Aziz;P. Biró;Serge Gaspers;Ronald de Haan;Nicholas Mattei;Baharak Rastegari
不确定偏好下的帕累托最优配置：不确定性模型、算法和复杂性
影响因子：
14.4
作者：
H. Aziz;P. Biró;Ronald de Haan;Baharak Rastegari
通讯作者：
Baharak Rastegari
稳定婚姻问题中的配对偏好
DOI：
--
发表时间：
2018
期刊：
Symposium on Theoretical Aspects of Computer Science
影响因子：
--
作者：
Ágnes Cseh;Attila Juhos
通讯作者：
Attila Juhos