Stable matching with uncertain linear preferences

DOI10.1007/s00453-019-00650-0zbMath1435.91123arXiv1607.02917OpenAlexW2984092209WikidataQ90667602 ScholiaQ90667602MaRDI QIDQ2309477

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

Publication date: 1 April 2020

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1607.02917

zbMATH Keywords

stable matchingsstable marriage problempolynomial-time algorithmsNP-hard problemsuncertain preferences

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Matching models (91B68)

Related Items (5)

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 ⋮ Assignment mechanisms: common preferences and information acquisition ⋮ Stable matching with uncertain pairwise preferences

Uses Software

• PrefLib

Cites Work

• Matching markets under (in)complete information
• Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Stable marriage and indifference
• On the evaluation of election outcomes under uncertainty
• Pareto optimal allocation under uncertain preferences: uncertainty models, algorithms, and complexity
• The Potts model and the Tutte polynomial
• Stable Matching with Uncertain Linear Preferences
• Improved approximation results for the stable marriage problem
• Algorithmics of Matching Under Preferences
• College Admissions and the Stability of Marriage
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Stable matching with uncertain linear preferences