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.


1 Answer 1


I think it's easier to just bypass (d) and show (e) directly.

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.