Search

Can the Gale-Shapley Deferred Acceptance Algorithm produce cycles?

Abbreviated Question: 
Can the Gale-Shapley Deferred Acceptance Algorithm produce cycles?
Answer: 

There is nothing wrong with your findings. What you described may happen. It is about the rejection cycles that form in each iteration. During the running of the algorithm, many rejection cycles may occur. It seems like many rejection cycles occurred in your third iteration. After you removed matched agents, fewer rejection chains occurred in the fourth iteration. This is theoretically possible.