Stable Matching with Uncertain Pairwise Preferences

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, i.e., 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.