The Blocking Lemma (Gale--Sotomayor)

The Blocking Lemma of Gale and Sotomayor. Fix a two-sided market with a finite set $M$ of men and a finite set $W$ of women, each agent holding a strict ordering of the opposite side, and let matchings be bijections $M \to W$.

Let $\mu$ be a male-optimal stable matching: it is stable, and every man weakly prefers it to his partner in any other stable matching. Let $\nu$ be an arbitrary matching — no stability is assumed of it — and put

the set of men who strictly prefer $\nu$ to the male-optimal stable matching. Assume $R \neq \emptyset$, witnessed by a man $m_0$.

The lemma asserts that $\nu$ is then blocked by a pair drawn from outside $R$ on the man's side and from inside $\nu(R)$ on the woman's side: there exist men $m$ and $m'$ with $m' \in R$ and $m \notin R$ such that the pair $(m, \nu(m'))$ blocks $\nu$, i.e.

The point of the statement is the location of the blocking pair. That an unstable $\nu$ has some blocking pair is immediate from male-optimality once some man prefers $\nu$; what the lemma adds is that one can always find a blocking man who does not belong to $R$, paired with a woman who is matched under $\nu$ to a member of $R$. This is exactly the form in which the lemma is used to prove that the male-propose deferred-acceptance mechanism is strategy-proof for the men: a single man's misreport can only create blocking pairs involving himself, while the lemma produces a blocking pair involving somebody else.

The standard proof splits on whether $\nu(R) = \mu(R)$. When the two sets of women differ, a woman in $\nu(R) \setminus \mu(R)$ together with her $\mu$-partner furnishes the pair directly, using only stability of $\mu$. When they coincide, the hybrid matching that follows $\nu$ on $R$ and $\mu$ elsewhere is a matching that all men of $R$ strictly prefer to $\mu$, and the conclusion is extracted from the deferred-acceptance run producing $\mu$.