Lemma: Let $\mu$ be any individually rational matching with respect to strict preferences $P$ and let $M'$ be all men who prefer $\mu$ to $\mu_M$. If $M'$ is nonempty, there is a pair $(m, w)$ that blocks $\mu$ such that $m$ is in $M-M'$ and $w$ is in $\mu(M')$.

Proof.

Case 1: $\mu(M')\not=\mu_M(M')$, i.e. the set of men who prefer $\mu$ to $\mu_M$ are matched to different sets of women under the matching rules $\mu$ and $\mu_M$.

Pick any $w\in\mu(M')-\mu_M(M')$. Note that $\mu(M')\not\subset\mu_M(M')$ in this case because it’s a one-to-one matching.

Denote $m'=\mu(w)$, and $m=\mu_M(w)$, so $m'\in M'$, and $m\not\in M'$. This implies that $w\succ \mu_M(m)$ and $w\succ_m\mu(m)$.

Note that $m\succ_w m'$, otherwise $(m', m)$ will block $\mu_M$, contradicting to that $\mu_M is stable$.

Therefore, $(m, w)$ blocks $\mu$ such that $w\in\mu(M')$ and $m\in M-M’$.

Case 2:$\mu(M')=\mu_M(M')$, i.e. the set of men who prefer $\mu$ to $\mu_M$ are matched to the same set of women under the matching rules $\mu$ and $\mu_M$.

Let $w$ be the last woman in $W'$ to receive a proposal from an acceptable member of $M'$ in the deferred acceptance. Denote this man by $m'$. So there are two possibilities: 1) $w$ has not been proposed before, and $\mu_M(m')=w$; 2) $w$ is already engaged with some other man $m$, and she rejects $m$ and accepts $m'$.

1) is not possible: If it were true, then since $w\in W'$, there must be some $m'\in M$ such that $\mu(m')=w\succ_{m'}\mu_M(m)$. That means when we run the deferred-acceptance algorithm to implement $\mu_M$, $m'$ has already proposed to $w$ and got rejected, contradicting that $w$ has not been proposed.

2) i. $m\not\in M'$, otherwise $m$ will propose to another woman, contradicting that $w$ is the last woman in $W'$ to receive a proposal. Therefore $w\succ_m\mu_M(m)$. And since $m\not\in M'$, that means $\mu_M(m)\succ_m\mu(m)$. This implies $w\succ_m\mu(m)$.

ii. Since $w$ is the last woman to receive the proposal, it must be that before $w$ rejects $m$, she must have rejected $\mu(w)$, i.e. her mate under $\mu$. That means $m\succ_w\mu(m)$.

Combine i. and ii., we conclude that $(m, w)$ blocks $\mu$.

Q.E.D.

Alternative proof:

Case 1: The same as above.

Case 2$\mu(M')=\mu_M(M')$.

Define the new market $(M', W', P')$. $P'(m)$ is the same as $P(m)$ restricted to $W'\cup\{m\}$, and $P'(w)$ is the same as $P(w)$ restricted to $M'\cup\{w\}$, $\forall m\in M'$, $w\in W'$.

Note that $\forall m\in M'$, $w\in W'$, we must have $\mu(m)\succ_m\mu_M(m)$ and $\mu_M(m)\succ_w\mu(w)$, otherwise $\mu_M$ would be blocked. We can write this as:

$\mu_M\succ_{W'}\succ\mu$

and

$\mu\succ_{M'}\succ\mu_M$.

So that means under $P'$, $w'$ is now ranked just below $\mu(w)$, and $m$ is now ranked just below $\mu_M(m)$.

In other words, the only men in $M'$ who are unacceptable to $w$ are those $m$ such that $m\succeq_w \mu(w)$, so $\mu_M(w)$ is acceptable to $w$ under $P'$ for all $w\in W'$.

Note that $\mu_M$ restricted to $M'\cup W'$ is still stable for $(M', W, P')$, because any pair that blocks $\mu_M$ under $P'$ would also block it under $P$.

Let $\mu_M'$ be the $M'$-optimal matching for $(M', W', P')$, then by Pareto-optimality Theorem, it must be that

(*) $\mu_M'\succ_{M'}$.

Otherwise, if $\mu_M=\mu_M'$, then it would be contradicting $\mu\succ_{M'}\succ\mu_{M'}$.

Furthermore, $\mu_{M'}\succeq_{W'}\mu$ by the construction of $P'$.

Define $\mu'$ on $M\cup W$ by $\mu'=\mu_{M'}$ on $M'\cup W'$, and $latex\mu’=\mu_M$ on $(M'-M)\cup (W'-W)$.

Combine it with (*), we have $\mu'\succ_M\mu_M$. $\mu'$ is not stable for $(M,W, P)$, so let $\{m, w\}$ be a blocking pair.

i). If $\{m, w\}$ in $M'\cup W'$, $m$ and $w$ would be mutually acceptable under $P'$, by construction of $P'$, and so $\{m, w\}$ would block $\mu_M'$. Also note that

then

$w=\mu'(m)=\mu_{M'}(m)\succ_m\succ\mu_M(m)$

and

$\mu_{M'}(w)=\mu'(w)=m\succ_w\mu(w)$.

So $\{m, w\}$ does not block $\mu'$.

ii). If $m\in M'$, and $m\in W-W'$, then

$w=\mu'(m)=\mu'_M(m)\succ_m\succ\mu_M(m)$

and

$\mu(w)\succ_w\mu_M(w)=\mu'(w)=m$.

$\{m, w\}$ blocks $\mu_M$, but it does not block $\mu'$.

iii). If $m\in M-M'$, $w\in W-W'$, then

$w=\mu'(m)=\mu_M(m)\succ_m\mu(m)$

and

$\mu(w)\succ_w\mu_M(w)=\mu'(w)=m$.

So $\{m, w\}$ does not block $\mu'$.

iv). If $m\in M-M'$, $w\in W'$, then

$w=\mu'(m)=\mu_M(m)\succ_m\mu(m)$

and

$\mu_{M'}(w)=\mu'(w)=m\succ_w\mu(w)$.

So $\{m, w\}$ does blocks $\mu'$. It’s the desired blocking pair.

Q.E.D.

References:

Gale, D., & Sotomayor, M. (1985). Some Remarks on the Stable Matching. Discrete Applied Mathematics, 11, 223–232.

Roth, A. E., & Sotomayor, M. (1990). Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis. Cambridge University Press.