@inproceedings{d993bfa279cf45aa8f8afde2b5702eca,
title = "Stable matching with uncertain linear preferences",
abstract = "We consider the two-sided stable matching setting in which there may be uncertainty about the agents{\textquoteright} preferences due to limited information or communication. We consider three models of uncertainty: (1) lottery model — in which 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.",
author = "Haris Aziz and P{\'e}ter Bir{\'o} and Serge Gaspers and Haan, \{Ronald de\} and Nicholas Mattei and Baharak Rastegari",
year = "2016",
month = sep,
day = "1",
doi = "10.1007/978-3-662-53354-3\_16",
language = "English",
isbn = "9783662533536",
series = "Information Systems and Applications, incl. Internet/Web, and HCI",
publisher = "Springer Berlin Heidelberg",
pages = "195--206",
booktitle = "Algorithmic Game Theory",
address = "Germany",
}