XVIII OBM

In round $k$ each unpaired boy $B$ in turn proposes to the girl $G$ he ranks highest amongst those he has not yet proposed to. If $G$ is not yet paired, or if she prefers $B$ to the boy she is currently paired with, then we pair $B$ and $G$ (and remove any existing pair for $G$). We claim that this algorithm terminates and gives a stable pairing.

First we must establish that it terminates. Each boy can propose to at most $n$ girls and in each round at least one boy must make a proposal, so it must terminate in $n^2$ rounds or less.

Second we must establish that it results in every boy and girl being paired off. Once a girl is paired, she always remains paired, although not necessarily to the same boy. Suppose girl $G$ ends up unpaired. Since there are equal numbers of boys and girls, a boy $B$ must also end up unpaired. By the end $B$ must have proposed to every girl, including $G$. Hence $G$ must have been paired at the end of that round. Contradiction.

Finally, we must establish that the pairing is stable. Suppose not, so that we end up with pairs $(B,G)$ and $(B^{\prime },G^{\prime })$, where $B$ prefers $G^{\prime }$ to $G$ and $G^{\prime }$ prefers $B$ to $B^{\prime }$. Since $B$ prefers $G^{\prime }$ to $G$ he must have proposed to $G^{\prime }$ before $G$. At the end of that round either $B$ and $G^{\prime }$ were paired, or $G^{\prime }$ was paired to $B^{\prime \prime }$ whom she preferred to $B$. In the first case, we have a contradiction because a girl can only change her pairing in favor of someone she prefers. So if she ends up paired to $B^{\prime }$ having earlier been paired to $B$, then she must prefer $B^{\prime }$ to $B$. Contradiction. In the second case, $G^{\prime }$ must prefer $B^{\prime \prime }$ to $B$ and $B^{\prime }$ to $B^{\prime \prime }$. Again a contradiction. So the pairing is stable.