# Marriage Market Proof (Alternative Proof of Rural Hospitals Theorem)

How do I get (a) + (b) + (c) $\implies$ (d) $\implies$ (e)?

(a) Show that for each $m \in M$, if $\mu(m) = \emptyset$ for some stable matching $\mu$, then for the woman-optimal matching, $\mu_W$, $\mu_W (m) = \emptyset$.
Proof: Suppose for $m \in M$, $\mu(m) = \emptyset$ for some $\mu$ stable and that $\mu \neq \mu_W$. By definition $\mu_W$ gives $m$ his least preferred achievable partner. So we can conclude that $\mu \geq_m \mu_W \implies \emptyset \geq_m \mu_W$. But $\mu_W$ is stable so it must be individually rational, which means $\mu_W(m) = \emptyset$

(b) $m \in M$, for the man-optimal set, $\mu_M$, if $\mu_M (m) = \emptyset$, then $\mu(m) = \emptyset$ for every stable matching $\mu$.
Proof: If for $m \in M$, $\mu_M(m) = \emptyset$, then $\emptyset$ is $m$'s best achievable partner since the matching is man-optimal. So for any other matching, $\mu'$, $\emptyset\geq_m \mu'(m)$. By individual rationality of stable matchings, it must be that $\mu'$ also assigns $m$ to $\emptyset$.

(c) Show that for every man $m\in M$, if $\mu(m) \in W$ for some stable matching $\mu$, then $\mu_M(m) \in W$. Similarly, show the same for the women.
Proof: If a stable matching $\mu$ sends $m$ to $W$, then $m$ prefers his partner in $W$ over $\emptyset$, and that partner is achievable. So now if we consider $\mu_M(m)$, we get the m-optimal matching, and $m$ gets his most preferred achievable mate. So this mate is achievable and at least as preferred as the mate in $\mu$ and therefore more preferred than $\emptyset$ so $\mu_M(m) \in W$ for $m$ also. The same argument can be said from a women's perspective by replacing the $m$'s and $M$'s with $w$ and $W$.

(d) using (a), (b), and (c) show that $$|\{m \in M : \mu_M(m) = \emptyset\}| = |\{m \in M : \mu(m) = \emptyset \mbox{ for some stable matching } \mu\}|$$ (a) If a man is single in some $\mu$, then he is single in $\mu_W$
(b) If a man is single in $\mu_M$, then he is single in any other $\mu$.
(c) If a man is not single in some $\mu$, then he is also not single in $\mu_M$.

(e) Show that the set of agents who are single is the same for every stable matching.

From (b), it is sufficient to show that if $m$ is single in some stable matching $\mu$, then $m$ is single in $\mu_M$.
Suppose there were some $m$ for which this is not true, i.e., $m$ is single in $\mu$ but not in $\mu_M$. Then $m$ has a $\mu_M$-partner $w$. Then $w$ is not single in $\mu_M$, hence by the contrapositive of (a) (applied to women), $w$ is not single in $\mu$. Thus $w$ has a $\mu$-partner $m'$. Then $m'$ is not single in $\mu$, hence by (c), $m'$ has a $\mu_M$-partner $w'$. This process can be repeated indefinitely, alternately finding $\mu$-partners for the women and $\mu_M$ partners for the men. We cannot ever form a loop: if we loop back to the original $m$, then this contradicts the assumption that $m$ is single in $\mu$; if we loop back to somewhere in the middle, then someone will have 2 partners in the same matching. Hence we get infinitely many people via this process, which is a contradiction.