Aziz Haris, Biró Péter, Gaspers Serge, de Haan Ronald, Mattei Nicholas, Rastegari Baharak
1UNSW Sydney, Sydney, Australia.
2Data61, Sydney, Australia.
Algorithmica. 2020;82(5):1410-1433. doi: 10.1007/s00453-019-00650-0. Epub 2019 Nov 14.
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.
我们考虑双边稳定匹配设置，其中由于信息或沟通有限，主体的偏好可能存在不确定性。我们考虑三种不确定性模型：（1）彩票模型——对于每个主体，在线性偏好上存在一个概率分布；（2）紧凑无差异模型——对于每个主体，指定一个弱偏好序，并且与该弱序兼容的每个线性序具有相同的可能性；（3）联合概率模型——在偏好配置文件上存在一个彩票。对于每个模型，我们研究计算给定匹配的稳定概率以及找到具有最高稳定概率的匹配的计算复杂性。我们还研究了更受限的问题，例如确定是否存在确定稳定的匹配。我们发现这些问题的复杂性情况丰富，表明不确定性的形式很重要。
