Stable marriage with general preferences

DOI10.1007/S00224-016-9687-ZzbMATH Open1356.91072arXiv1407.1853OpenAlexW199219868MaRDI QIDQ506532FDOQ506532

Authors: Linda Farczadi, Konstantinos Georgiou, Jochen Könemann 

Publication date: 1 February 2017

Published in: Theory of Computing Systems (Search for Journal in Brave)

Abstract: We propose a generalization of the classical stable marriage problem. In our model, the preferences on one side of the partition are given in terms of arbitrary binary relations, which need not be transitive nor acyclic. This generalization is practically well-motivated, and as we show, encompasses the well studied hard variant of stable marriage where preferences are allowed to have ties and to be incomplete. As a result, we prove that deciding the existence of a stable matching in our model is NP-complete. Complementing this negative result we present a polynomial-time algorithm for the above decision problem in a significant class of instances where the preferences are asymmetric. We also present a linear programming formulation whose feasibility fully characterizes the existence of stable matchings in this special case. Finally, we use our model to study a long standing open problem regarding the existence of cyclic 3D stable matchings. In particular, we prove that the problem of deciding whether a fixed 2D perfect matching can be extended to a 3D stable matching is NP-complete, showing this way that a natural attempt to resolve the existence (or not) of 3D stable matchings is bound to fail.

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

Recommendations

• Stable marriage with general preferences. Extended abstract
• Three-sided stable matchings with cyclic preferences
• Hard variants of stable marriage.

zbMATH Keywords

matchingNP-completenessstable marriagecyclic stable marriage

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Matching models (91B68)

Cites Work

• Some remarks on the stable matching problem
• Improved approximation results for the stable marriage problem
• Title not available (Why is that?)
• College Admissions and the Stability of Marriage
• Nontransitive preferences in decision theory
• Three-sided stable matchings with cyclic preferences
• Circular stable matching and 3-way kidney transplant
• Algorithmics of matching under preferences. With a foreword by Kurt Mehlhorn
• Three-dimensional stable matching with cyclic preferences
• Preference structures and their numerical representations
• Linear programming brings marital bliss
• Title not available (Why is that?)
• A 25/17-approximation algorithm for the stable marriage problem with one-sided ties
• Hard variants of stable marriage.
• Stable marriage and indifference
• The structure of stable marriage with indifference
• Matching with partially ordered contracts
• Stable marriage with general preferences. Extended abstract
• Approximation Algorithms for the Sex-Equal Stable Marriage Problem
• A 3/2-Approximation Algorithm for General Stable Marriage
• Title not available (Why is that?)
• The mathematics of preference, choice and order. Essays in honor of Peter C. Fishburn
• An experimental investigation of violations of transitivity in choice under uncertainty

Cited In (11)

• The structure of stable marriage with indifference
• Stable marriage with general preferences. Extended abstract
• Pairwise Preferences in the Stable Marriage Problem
• Three-sided stable matching problem with two of them as cooperative partners
• The envy-free matching problem with pairwise preferences
• Stable matching with uncertain pairwise preferences
• Three-dimensional stable matching with cyclic preferences
• Matching through institutions
• Pareto efficient matchings with pairwise preferences
• Circular stable matching and 3-way kidney transplant
• Three-sided stable matchings with cyclic preferences

This page was built for publication: Stable marriage with general preferences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q506532)