Stable Marriage
Problem Description
Given n men and n women, where each person has ranked all members of the opposite sex with a unique number between 1 and n in order of preference, marry the men and women together such that there are no two people of opposite sex who would both rather have each other than their current partners. If there are no such people, all the marriages are "stable" [1,2].
The stable matching problem has several practical applications, as well as several variants (some of which are hard to solve). The variant proposed in the following is known to be polynomially solvable.
Instances comprise n men and n women. Each person has ranked all members of the opposite sex with a number between 1 and n in order of preference. Note that ties are permitted in this setting, i.e., one person can equally prefer two or more members of opposite sex. The strong stable marriage problem with ties is the problem of finding a strongly stable matching mapping men to women. A matching is strong stable if and only if there is no pair m,w such that both the following conditions are satisfied:
- Man m is matched with a woman w' different from w and such that m prefers w over w';
- Woman w is matched with a man m' different from m and such that w prefers m over m', or m and m' are equally preferred by w.
There are instances that have no strongly stable matching when ties are permitted. However, an O(n^{3}) algorithm for deciding if a strong stable marriage does exist and finding one if any is reported in [3].
Predicates
Input: womanAssignsScore/3, manAssignsScore/3
Output: match/2
Input format
Let w_{1},...,w_{n} and m_{1},...,m_{n} be n women and men, respectively.
- womanAssignsScore(w,m,s) when a woman w assigns a score s to a man m
- manAssignsScore(m,w,s) when a man m assigns a score s to a woman w
Relations womanAssignsScore and manAssignsScore are complete specifications of preferences, i.e., womanAssignsScore (resp. manAssignsScore) is defined for each pair WOMAN,MAN (resp. MAN,WOMAN).
A score is a positive integer ranging from 1 to n. The higher the score is, the higher the preference is. Ties in scores are admitted, that is, a woman can assign the same score to several men, and vice versa.
Output format
A strong stable matching represented by means of instances of match(MAN,WOMAN). i.e., the relation expressed by match is such that no pair m,w satisfies both the following conditions:
match(m,w'), w' <> w, manAssignsScore(m,w,s), manAssignsScore(m,w',s'), s > s';
match(m',w), womanAssignsScore(w,m,s), womanAssignsScore(w,m',s'), s >= s'.
Example(s)
A given input is:
manAssignsScore(m_1,w_1,4). manAssignsScore(m_1,w_2,2). manAssignsScore(m_1,w_3,2). manAssignsScore(m_1,w_4,1). manAssignsScore(m_2,w_1,2). manAssignsScore(m_2,w_2,1). manAssignsScore(m_2,w_3,4). manAssignsScore(m_2,w_4,3). manAssignsScore(m_3,w_1,1). manAssignsScore(m_3,w_2,3). manAssignsScore(m_3,w_3,2). manAssignsScore(m_3,w_4,2). manAssignsScore(m_4,w_1,2). manAssignsScore(m_4,w_2,3). manAssignsScore(m_4,w_3,4). manAssignsScore(m_4,w_4,1). womanAssignsScore(w_1,m_1,3). womanAssignsScore(w_1,m_2,4). womanAssignsScore(w_1,m_3,2). womanAssignsScore(w_1,m_4,1). womanAssignsScore(w_2,m_1,1). womanAssignsScore(w_2,m_2,4). womanAssignsScore(w_2,m_3,3). womanAssignsScore(w_2,m_4,2). womanAssignsScore(w_3,m_1,4). womanAssignsScore(w_3,m_2,2). womanAssignsScore(w_3,m_3,3). womanAssignsScore(w_3,m_4,1). womanAssignsScore(w_4,m_1,3). womanAssignsScore(w_4,m_2,2). womanAssignsScore(w_4,m_3,4). womanAssignsScore(w_4,m_4,1).
Resulting in the following output:
match(m_1,w_1). match(m_2,w_3). match(m_3,w_2). match(m_4,w_4).
Additional sample instances: download
References
[1] Gale and Shapley: "College Admissions and the Stability of Marriage", American Mathematical Monthly 69, 9-14, 1962.
[2] Gusfield and Irving, "The Stable Marriage Problem: Structure and Algorithms", p. 54; MIT Press, 1989.
[3] Kavitha et al, "Strongly stable matching in time O(n m) and extension to the H/R problem", Proc. STACS 2004, pp. 222-233, 2004.
Author(s)
- Authors: Mario Alviano, Marco Manna, Francesco Ricca
- Affiliation: University of Calabria, Italy