Question

Show that the deferred acceptance algorithm terminates.

Short answer

the deferred acceptance algorithm terminates.

Step-by-step solution

Step 1:

We shall prove this by contradiction method.

So, let

n denote a man and,

$p_i$proposal list of women$w_i$ .

Now, we will assume that the algorithm never terminates.

This is possible only when there exists an integer$i\in \left\{1,2,...,n\right\}$ and then$p_i$ remains empty in every iteration.

Step 2:

When there are equal number of women and men ten there exists an integer$j_k\in \left\{1,2,...,n\right\}$ where$i\ne j_k$ . So, that$P_i$ contains at least two proposals in the$K^{th}$ iteration of the algorithm.

Now, at least one proposal will be rejected in the$K^{th}$ iteration.

Then there will be infinite number of iterations which implies that there are infinite numbers of rejected proposals.

Step 3:

We know that in each iteration at least one proposal should be rejected. But this is impossible because there are at most$n^2$ rejected proposals.

This is the contradiction which implies that we assume that the algorithm never terminates is not correct and proves that the deferred acceptance algorithm terminates.