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 — 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.
|Title of host publication||Algorithmic Game Theory|
|Subtitle of host publication||9th International Symposium, SAGT 2016, Liverpool, UK, September 19–21, 2016, Proceedings|
|Publisher||Springer Berlin Heidelberg|
|Number of pages||12|
|Publication status||Published - 1 Sep 2016|
|Name||Information Systems and Applications, incl. Internet/Web, and HCI|