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.