Stable matching with uncertain linear preferences
From MaRDI portal
Publication:2309477
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.
Recommendations
Cites work
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- Algorithmics of matching under preferences. With a foreword by Kurt Mehlhorn
- College Admissions and the Stability of Marriage
- scientific article; zbMATH DE number 1617265 (Why is no real title available?)
- scientific article; zbMATH DE number 45086 (Why is no real title available?)
- scientific article; zbMATH DE number 48303 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- Improved approximation results for the stable marriage problem
- Matching markets under (in)complete information
- On the evaluation of election outcomes under uncertainty
- Pareto optimal allocation under uncertain preferences: uncertainty models, algorithms, and complexity
- Stable marriage and indifference
- Stable Matching with Uncertain Linear Preferences
- The Potts model and the Tutte polynomial.
- Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
Cited in
(19)- Compromises and rewards: stable and non-manipulable probabilistic matching
- Assignment mechanisms: common preferences and information acquisition
- Stable matching with uncertain pairwise preferences
- Stable Matching with Uncertain Linear Preferences
- Stable Matching with Evolving Preferences
- Finding stable matchings that are robust to errors in the input
- Paths to stability in two-sided matching under uncertainty
- Review of the theory of stable matchings and contract systems
- Stable matching with multilayer approval preferences: approvals can be harder than strict preferences
- Stable matching with multilayer approval preferences: approvals can be harder than strict preferences
- Computational complexity of \(k\)-stable matchings
- Adapting stable matchings to evolving preferences
- Stable matching with approval preferences under partial information
- Minimizing blocking agents for stable matching with partial approval information
- Competitive query minimization for stable matching with one-sided uncertainty
- Maximum-utility popular matchings with bounded instability
- The team order problem: maximizing the probability of matching being large enough
- Stable marriage with multi-modal preferences
- Commitment under uncertainty: Two-stage stochastic matching problems
This page was built for publication: Stable matching with uncertain linear preferences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2309477)
