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.
- in round one all men are single. They propose to their highest preference-woman.
- 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.
- 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.
- 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.
For this demonstration I used the animation package, which is a very nice way to just record multiple plots and wrap them into some output file of your choice. The code is below.
Code on gist: https://gist.github.com/1628636