Boy Optimality

We say that (b,g) is a stable pair if there is some stable marriage in which b and g are matched. We say that g is a stable partner of b and vice versa.

The marriage returned by MATCH assigns every boy to his favorite stable partner! We, therefore, call this the boy-optimal match.

• Claim: At no point in the execution of MATCH does a girl reject a stable partner. This means that the first time a boy proposes to one of his stable partners, he gets to stay with her (and consequently marries his favorite stable partner).
• Let's assume that a stable pair is rejected. Let (b₁,g₁) be the first such stable pair. Let b₂ be the boy that causes the breakup of b₁ and g₁.
• Since (b₁,g₁) is a stable pair, there is some stable marriage that includes it. In one such stable marriage, let g₂ be b₂'s mate.
• But, a marriage that includes (b₁,g₁) and (b₂,g₂) can't be stable! Because g₁ rejected b₁ for b₂, we know g₁ would rather be with b₂. Because the (b₁,g₁) breakup was the first, we know that b₂ prefers g₁ to any other stable partner (such as the hypothetical g₂).
• So, (b₁,g₁) isn't a stable pair--a contradiction--and, therefore, no stable pair can be rejected.

This proves Theorem 7 (boy optimality), but it also implies Theorem 4: you get the same marriage independent of the order in which free boys propose.