#game-theory

There are $n$ men and $n$ women, and each person ranks all members of the other group. A perfect matching is unstable if some man and woman both prefer each other to their assigned partners. Prove that a stable matching always exists, and give an algorithm that finds one in $\mathcal{O}(n^2)$ time.