http://en.wikipedia.org/wiki/Stable_marriage_problem

...

Everyone gets married

Once a woman becomes engaged, she is always engaged to someone. So, at the end, there cannot be a man and a woman both unengaged, as he must have proposed to her at some point (since a man will eventually propose to everyone, if necessary) and, being unengaged, she would have to have said yes.

The marriages are stable

...



[edit] Algorithm



function stableMatching {

Initialize all m ∈ M and w ∈ W to free

while ∃ free man m who still has a woman w to propose to {

w = m's highest ranked such woman who he has not proposed to yet

if w is free

(m, w) become engaged

else some pair (m', w) already exists

if w prefers m to m'

(m, w) become engaged

m' becomes free

else

(m', w) remain engaged

}

}



...their algorithm has been used to pair graduating medical (interns) students with hospital (residencies) jo http://bit.ly/oKofKF