Advertisement
Published in:
2005 | OriginalPaper | Chapter
Specialised Constraints for Stable Matching Problems
Authors : Chris Unsworth, Patrick Prosser
Published in: Principles and Practice of Constraint Programming - CP 2005
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
The stable marriage problem (SM) and the Hospital / Residents problem (HR) are both stable matching problems. They consist of two sets of objects that need to be matched to each other; in SM men to women, and in HR residents to hospitals. Each set of objects expresses a ranked preference for the objects in the other set, in the form of a preference list. The problem is then to find a matching of one set to the other such that the matching is stable. A matching is stable iff it contains no blocking pairs. A blocking pair in a matching
M
consists of two objects
x
and
y
one from each set(
x
= man and
y
= woman for SM or
x
= hospital and
y
= resident in HR), such that
x
and
y
are not matched in
M
and both
x
and
y
would rather be matched to each other than to there assignment in
M
.