Stable matching with uncertain linear preferences

DOI10.1007/s00453-019-00650-0zbMath1435.91123arXiv1607.02917WikidataQ90667602 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 matchings; stable marriage problem; polynomial-time algorithms; NP-hard problems; uncertain preferences

Mathematics Subject Classification ID

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68W25: Approximation algorithms

91B68: Matching models

Related Items

Review of the theory of stable matchings and contract systems, 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

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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