Talks and Poster Presentations (with Proceedings-Entry):
H. Aziz, P. Biro, S. Gaspers, R. de Haan, N. Mattei, B. Rastegari:
"Stable Matching with Uncertain Linear Preferences";
Talk: International Symposium on Algorithmic Game Theory,
Liverpool, United Kingdom;
2016-09-19
- 2016-09-21; in: "Proceedings of the 9th International Symposium on Algorithmic Game Theory - SAGT 2016",
(2016),
ISBN: 978-3-662-53353-6;
195
- 206.
English abstract:
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.
Electronic version of the publication:
http://publik.tuwien.ac.at/files/publik_256475.pdf
Created from the Publication Database of the Vienna University of Technology.