Stable matching with uncertain linear preferences

Aziz, Haris, Biró, Péter, Gaspers, Serge, de Haan, Ronald, Mattei, Nicholas and Rastegari, Baharak (2020) Stable matching with uncertain linear preferences. Algorithmica, 82 (5). pp. 1410-1433. DOI

PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader

Official URL:

Open Access


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—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.

Item Type:Article
Uncontrolled Keywords:stable matchings, stable marriage problem, uncertain preferences, NP-hard problems, polynomial-time algorithms
Mathematics, Econometrics
ID Code:7298
Deposited By: MTMT SWORD
Deposited On:24 Mar 2022 16:44
Last Modified:24 Mar 2022 16:44

Repository Staff Only: item control page


Downloads per month over past year

View more statistics