Question:
I am analyzing the deferred acceptance algorithm, where I execute this algorithm, then delete the matches from the original preference list (the dataset is large enough that this is not a problem) and execute the algorithm again. I repeat this 5 times to get the first op to fifth best recommendations per person. Then I look at the mean 'ranking' of the first through fifth recommendation (where the person highest on ones preference list would have 'rank' 1 etc.). However, the result I get is the following: [6.798, 8.338, 10.283, 8.904, 12.706]. Can it be possible that the mean rank of the fourth recommendation is lower than the mean rank of the third recommendation? I could find nothing about this online.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.
An example of a rejection cycle is as follows: Suppose person A is rejected from her third choice and applied to his fourth choice in the next step. Let's call his fourth choice person B. Suppose Person B tentatively matched with Person C in the previous period. If person B likes A better than C, then the tentatively held person C will get rejected. Then, Person C will apply to her next choice and cause the rejection of someone who was tentatively held. This process continues and ends with the rejection of person A. In this example, person A initiated a rejection chain that came back to him at the end.
The deferred acceptance algorithm finds a stable matching. It may find a bad match concerning the average rank for one side of the market. A great paper that studies the trade-off between the stability of matching and efficiency is Kesten (2010), titled "School Choice with Consent," Quarterly Journal of Economics. Example 2 in this paper shows how bad of a match the deferred acceptance may find.
