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.

The (strong) stable marriage problem is the problem of finding a (strong) 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:

1. Man m is matched with a woman w' different from w and such that m prefers w over w';
2. 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.

An O(n³) algorithm for finding a strong stable marriage is reported in [3].

Predicates

• Input: womanAssignsScore/3, manAssignsScore/3

• Output: match/2

Input format

Let w₁,...,w_n and m₁,...,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:

1. match(m,w'), w' <> w, manAssignsScore(m,w,s), manAssignsScore(m,w',s'), s > s';

2. match(m',w), womanAssignsScore(w,m,s), womanAssignsScore(w,m',s'), s >= s'.

Example(s)

INPUT

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

OUTPUT

match(m_1,w_1). match(m_2,w_3). match(m_3,w_2). match(m_4,w_4).

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)

• Author: Francesco Ricca
  • Affiliation: University of Calabria, Italy
• Author: Mario Alviano
  • Affiliation: University of Calabria, Italy
• Author: Marco Manna
  • Affiliation: University of Calabria, Italy