Question

Write the deferred acceptance algorithm in pseudocode.

Short answer

$\left(P_a,w_a\right)$is pair of women and their accepted proposals.

And return is$\left(P_a,w_a\right)$ for all$a\in \left\{1,2,...,n\right\}$

Step-by-step solution

Step 1:

We will use ‘match’ algorithm.

Procedure match

$\left(m_1,m_2,\dots ,m_n,w_1,w_2,\dots .,w_n\text{with preference lists}{\mathrm{M}}_1,M_2,\dots M_n,W_1,W_2,\dots W_n,\right.\text{respectively)}$

Here$p_i$ is the proposal list of women$w_i$ .

Every man proposes to their preferred women and the women reject the proposal of all the men that are not their preferred man from the entire proposal. When the men will propose to the first women in their remaining preference list and the women will reject all the proposals of their no preferred men.

This will repeat until all women have exactly one remaining proposal.

Step 2:

For i : = 1 to n ,

$P_{i:=}\varphi$

While there exists a$P_i$ with$i\in \left\{1,2,...,n\right\}$ such that$P_{i:=}\varphi$

For j : = 1 to n

$P_{M_i\left(1\right)}:=P_{M_i\left(1\right)}\cup \left\{M_j\right\}$

For k : = 1 to n

best =$p_k\left(1\right)$

Step 3

For all $p\in P_k$do if p is preferred over best in$W_k$ then,

$M_{best}:=M_{best}-w_k$

Else

$M_p:=M_p-\left\{w_k\right\}$

Hence,$\left(P_a,w_a\right)$ is pair of women and their accepted proposals.

And return is$\left(P_a,w_a\right)$ for all$a\in \left\{1,2,...,n\right\}$