Question

Show that the deferred acceptance always terminates with a stable assignment.

Short answer

Deferred acceptance always terminates with a stable assignment.

Step-by-step solution

Step 1:

We shall prove this by contradiction method.

So, let

m denote a man and,

n denote a woman.

Then there exists a man m and woman w such that m prefers w over his assigned partner and w prefers m over her assigned partner.

Step 2:

This implies that m have proposed w in the previous iteration. And w prefers m over her assigned partner that means she would have rejected the proposal of her assigned partner I the iteration of algorithm.

So, this is the contradiction that she cannot refuse the proposal of her assigned partner.

So, our assumption is incorrect that means that deferred acceptance always terminates with a stable assignment.

Hence, the deferred acceptance always terminates with a stable assignment.