**Lemma****:** Let be any individually rational matching with respect to strict preferences and let be all men who prefer to . If is nonempty, there is a pair that blocks such that is in and is in .

Proof.

Case 1: , i.e. the set of men who prefer to are matched to different sets of women under the matching rules and .

Pick any . Note that in this case because it’s a one-to-one matching.

Denote , and , so , and . This implies that and .

Note that , otherwise will block , contradicting to that .

Therefore, blocks such that and $m\in M-M’$.

Case 2:, i.e. the set of men who prefer to are matched to the same set of women under the matching rules and .

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

1) is not possible: If it were true, then since , there must be some such that . That means when we run the deferred-acceptance algorithm to implement , has already proposed to and got rejected, contradicting that has not been proposed.

2) i. , otherwise will propose to another woman, contradicting that is the last woman in to receive a proposal. Therefore . And since , that means . This implies .

ii. Since is the last woman to receive the proposal, it must be that before rejects , she must have rejected , i.e. her mate under . That means .

Combine i. and ii., we conclude that blocks .

Q.E.D.

Alternative proof:

Case 1: The same as above.

Case 2: .

Define the new market . is the same as restricted to , and is the same as restricted to , , .

Note that , , we must have and , otherwise would be blocked. We can write this as:

and

.

So that means under , is now ranked just below , and is now ranked just below .

In other words, the only men in who are unacceptable to are those such that , so is acceptable to under for all .

Note that restricted to is still stable for , because any pair that blocks under would also block it under .

Let be the -optimal matching for , then by Pareto-optimality Theorem, it must be that

(*) .

Otherwise, if , then it would be contradicting .

Furthermore, by the construction of .

Define on by on , and $latex\mu’=\mu_M$ on .

Combine it with (*), we have . is not stable for , so let be a blocking pair.

i). If in , and would be mutually acceptable under , by construction of , and so would block . Also note that

then

and

.

So does not block .

ii). If , and , then

and

.

blocks , but it does not block .

iii). If , , then

and

.

So does not block .

iv). If , , then

and

.

So does blocks . 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.