# Stable Matching with Uncertain Linear Preferences

arXiv: https://arxiv.org/abs/1607.02917 · HTML: https://mlsanity.com/paper/1607.02917/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Jul 2016.

## Built on by (most cited first, 6 of 6)

- [Putting Gale & Shapley to Work: Guaranteeing Stability Through Learning](https://mlsanity.com/paper/2410.04376/) (2024)
- [Fairness in Matching under Uncertainty](https://mlsanity.com/paper/2302.03810/) (2023)
- [From Intelligent Agents to Trustworthy Human-Centred Multiagent Systems](https://mlsanity.com/paper/2210.02260/) (2022)
- [Centralized Selection with Preferences in the Presence of Biases](https://mlsanity.com/paper/2409.04897/) (2024)
- [Learning Bilateral Team Formation in Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2506.20039/) (2025)
- [DataCupid: Stable Matching Repair for Training Data Acquisition with Delayed Feedback](https://mlsanity.com/paper/2610.12960/) (2026)

## Abstract (arXiv)

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.