The Deferred Acceptance Algorithm (DAA) goes back to Gale and Shapley (1962). They introduce a rather simple algorithm that finds a stable matching for example for college admissions or in a marriage market. In a marriage market where M men have preferences over W women, and men take the role of the proposing party, the DAA produces what is called the M-stable matching: each man strictly prefers the M-stable matching to any other potential matching. “Stable” means that no couple of a man and a woman could break the matching by choosing another mate. This is quite a strong result.
Variations of this algoritm are used in Hospital assignments in the USA, whereby recently graduated doctors submit preferences over hospitals, and hospitals submit preferences over graduates. Another application is the kidney exchange, where the algorithm is used to find the best match between a set of donors and a set of receivers. If you’re interested in this, check out Al Roth’s website.

Here I’m going to use R to make a little simulation of this. It’s not a spectacular movie, but it shows you how the algorithm works. So here goes: We have M men and W women in a marriage market, and each participant has a complete set of preferences (a ranking) over all participants of the other sex. In the demonstration I assumed strict preferences (no indifference between any 2 members) and that nobody wants to be single, but the algorithm can handle this.

1. in round one all men are single. They propose to their highest preference-woman.
2. Each woman who receives at least one proposal picks her highest preference from the set of proposers. Otherwise she stays single. Men who were rejected, go back to the set of singles.
3. in Round two, all remaining singles propose to their second preference. All women who receive proposals accept the best mate. If there was a mate “deferentially accepted”, i.e. some man from round one, he is released back into the set of singles.
4. the algorithm stops once we cycled over all W preferences, or if there are no more male singles left. At that point the current match is the one that gets implemented.