Coding Towards The Answer, Part 1

_ Gale-Shapley Algorithm

As a background, Gale-Shapley Algorithm matches N men and N women for marriage, so each person gets their highest preference. This is the stable marriage problem, and it has many applications, like how to match doctors into residency programs. In the doctor residency match, there are residents who want to go to certain hospitals, and hospitals that want certain resident doctors. You need to match those preferences up together. The Gale-Shapley algorithm always finds a solution.

This is sometimes known as the Stable marriage problem which addresses matching markets in economic theory.

On the example of matching partners (in this case, 4 kings and 4 queens), the first step is that the men will propose to their first choices. They think about all the women who are available, and they each propose to their best preferred choices. The women, if any of them receive multiple proposals, will then pick their favorite from those choices. The men who are rejected will then return to the next round and propose to their next best choice. The women that are not hitched, if any of them have multiple proposals, will pick their favorite on the following rounds. This process will keep repeating until each person is matched. When each person is matched, this will always be a stable match.