Stable Matching with Uncertain Linear Preferences
Stable Matching with Uncertain Linear Preferences
复制标题
DOI：
10.1007/s00453-019-00650-0
复制
发表时间：
2016-07
期刊：
影响因子：
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
我们考虑双边稳定匹配设置，在这种情况下，由于有限的信息或通信，代理的偏好可能存在不确定性。我们考虑了三种不确定性模型：(1)彩票模型-对于每个代理，线性偏好上存在概率分布；(2)紧凑无差异模型-对于每个代理，指定一个弱偏好顺序，并且每个与弱顺序相容的线性顺序是等可能的；(3)联合概率模型-在偏好配置文件上存在彩票。对于每一个模型，我们研究了计算给定匹配的稳定概率以及寻找具有最高稳定概率的匹配的计算复杂度。我们还研究了更有限的问题，如确定是否存在一定稳定的匹配。我们发现这些问题具有丰富的复杂性，表明不确定性所采取的形式是重要的。
We consider the two-sided stable matching setting in which there may be uncertainty about the agents’ preferences due to limited information or communication. We consider three models of uncertainty: (1) lottery model—for each agent, there is a probability distribution over linear preferences, (2) compact indifference model—for each agent, a weak preference order is specified and each linear order compatible with the weak order is equally likely and (3) joint probability model—there is a lottery over preference profiles. For each of the models, we study the computational complexity of computing the stability probability of a given matching as well as finding a matching with the highest probability of being stable. We also examine more restricted problems such as deciding whether a certainly stable matching exists. We find a rich complexity landscape for these problems, indicating that the form uncertainty takes is significant.