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

×

Problem Loading...

Note Loading...

Set Loading...