# Can you marry them?

(For those who do not know what a Stable Marriage is, skip to the end for a list of definitions.)

Given the following rankings of 9 men and 9 women, how many stable marriages between them exist?

• A lower numerical rank denotes stronger preference.
• The set of men is expressed in upper case and the set of women is expressed in lower case.
• Each row denote the rankings of an individual
• $$rankMen$$ is the rankings men provide for the women.
• For easier parsing, the data is available here

$rankMen_{m,w} = \begin{matrix} & a & b & c & d & e & f & g & h & i \\ A & 7 & 3 & 8 & 9 & 6 & 4 & 2 & 1 & 5 \\ B & 5 & 4 & 8 & 3 & 1 & 2 & 6 & 7 & 9 \\ C & 4 & 8 & 3 & 9 & 7 & 5 & 6 & 1 & 2 \\ D & 9 & 7 & 4 & 2 & 5 & 8 & 3 & 1 & 6 \\ E & 2 & 6 & 4 & 9 & 8 & 7 & 5 & 1 & 3 \\ F & 2 & 7 & 8 & 6 & 5 & 3 & 4 & 1 & 9 \\ G & 1 & 6 & 2 & 3 & 8 & 5 & 4 & 9 & 7 \\ H & 5 & 6 & 9 & 1 & 2 & 8 & 4 & 3 & 7 \\ I & 6 & 1 & 4 & 7 & 5 & 8 & 3 & 9 & 2 \end{matrix}$

$rankWomen_{w,m} = \begin{matrix} & A & B & C & D & E & F & G & H & I \\ a & 3 & 1 & 5 & 2 & 8 & 7 & 6 & 9 & 4 \\ b & 9 & 4 & 8 & 1 & 7 & 6 & 3 & 2 & 5 \\ c & 3 & 1 & 8 & 9 & 5 & 4 & 2 & 6 & 7 \\ d & 8 & 7 & 5 & 3 & 2 & 6 & 4 & 9 & 1 \\ e & 6 & 9 & 2 & 5 & 1 & 4 & 7 & 3 & 8 \\ f & 2 & 4 & 5 & 1 & 6 & 8 & 3 & 9 & 7 \\ g & 9 & 3 & 8 & 2 & 7 & 5 & 4 & 6 & 1 \\ h & 6 & 3 & 2 & 1 & 8 & 4 & 5 & 9 & 7 \\ i & 8 & 2 & 6 & 4 & 9 & 1 & 3 & 7 & 5 \end{matrix}$

A marriage is a relation between a set of men $$(M)$$ to a disjunct set of women $$(W)$$ such that

1. for every man $$m \in M$$, there is a corresponding woman given by $$wife(m)$$
2. for every woman $$w \in W$$, there is a corresponding man given by $$husband(m)$$
3. $$wife$$ and $$husband$$ are inverse functions. That is, $wife(husband(w)) = w \quad \forall w \in W \\ husband(wife(m)) = m \quad \forall m \in M$

(If you find this confusing, the normal idea of a marriage is okay.)

Assume that every men has a ranking of preferences of the women and every women has a ranking of preferences of the men.

A marriage is considered stable iff there exists no pair of men and women $$(m,w)$$ such that

$rank_{m}(w) < rank_{m}(wife(m)) \quad \text{and} \\ rank_{w}(m) < rank_{w}(husband(w))$

(There are no two people of opposite sex who would both rather have each other than their current partners.)

×