be two stable matchings. Then.
$M \lor M' \equiv ((b_1, \max_{b_1}(g_1, g_1'), \dots, (b_n, \max_{b_n}(g_n, g_n')))$
is a stable matching.
§ Step 1: This is a matching
First we show that it is indeed a matching: the marriages are all monogamous.
Assume that we had $g_1 = \max_{b_1}(g_1, g_1') = \max_{b_2}(g_2, g_2') = g_2'$.
Since $(b_2, g_2')$ is the match in $M'$ and $g_1 = g_2'$, we have that $(b_2, g_1)$
is the match in $M'$. We also know that $g_1 >_{b_1} g_1'$ from the assumption.
Since the matching $M'$ is stable, we need to ensure that $(g_1, b_1)$ is not a
rogue couple; $b_1$ prefers $g_1$ over $g_1'$. Thus, we must have that $b_2 >_{g_1} b_1$
to ensure that $(b_2, g_1)$ is stable.
However $M$ is stable, and $(b_1, g_1) \in M$. Since we have that $b_2 >_{g_1} b_1$,
for $(b_1, g_1)$ to be stable, we must ensure that $(b_2, g_1)$ is not
a rogue couple, since $g_1$ prefers $b_2$ over $b_1$. This we must have
that $g'_1 >_{b_2} g_1$.
But this contradicts the equation $\max{b_2}(g_2, g_2') = g_2' = g_1$ (?)
§ Sid musings
the girls are monotonic filters, where they only allow themselves to match higher. The propogate (in the kmett/propogators sense of the word) information to all lower requests that they will not match. The boys are in some kind of atomic write framework with conflict resolution, where a girl allows a boy to "write" into her 'consider this boy' state if the boy is accepted by her filter.
§ References