Stable Marriage with General Preferences

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...

Full description

Saved in:
Bibliographic Details
Published in:Theory of computing systems 2016-11, Vol.59 (4), p.683-699
Main Authors: Farczadi, Linda, Georgiou, Konstantinos, Könemann, Jochen
Format: Article
Language:English
Subjects:
Algorithms
Analysis
Asymmetry
Computer programming
Computer Science
Feasibility
Game theory
Linear programming
Marriage
Matching
Mathematical models
Men
Partitions
Polynomials
Preferences
Studies
Theory of Computation
Three dimensional models
Women
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1432-4350
1433-0490
DOI:10.1007/s00224-016-9687-z