Stable Marriage Problem is the problem of finding a stable matching between two sets of elements given a set of preferences for each element. Formally, given a set M = {m_{1}, m_{2}, …, m_{n}} of n men, a set W = {w_{1}, w_{2}, …, w_{n}} of n women, a preference list (i.e., an ordering of n men) for each woman and a preference list (i.e., an ordering of n women) for each man, the problem is to find a set S of pairs (m,w) for some m ∈ M and w ∈ W such that

- Each m ∈ M and w ∈ W appears in exactly one pair in S
- If (m, w) ∈ S and (m’, w’) ∈ S, then it cannot be the case that m prefers w’ to w and w’ prefers m to m’