Stable matching with uncertain linear preferences

Haris Aziz, Péter Biró, Serge Gaspers, Ronald de Haan, Nicholas Mattei, Baharak Rastegari

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

20 Citations (Scopus)
250 Downloads (Pure)


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.
Original languageEnglish
Title of host publicationAlgorithmic Game Theory
Subtitle of host publication9th International Symposium, SAGT 2016, Liverpool, UK, September 19–21, 2016, Proceedings
PublisherSpringer Berlin Heidelberg
Number of pages12
ISBN (Electronic)9783662533543
ISBN (Print)9783662533536
Publication statusPublished - 1 Sept 2016

Publication series

NameInformation Systems and Applications, incl. Internet/Web, and HCI
ISSN (Print)0302-9743


Dive into the research topics of 'Stable matching with uncertain linear preferences'. Together they form a unique fingerprint.

Cite this