Feeling spontaneous, the mayor of Groningen wants to help all singles in the city. He wants to do this by organizing a date for every single in town. Since he thinks that you are pretty smart, because you study econometrics, he gives you the job of making all the combinations for the dates. How would you do this?
In this case, we assume that we know the preferences of everyone. So from every man, we get a list with a ranking of women he prefers and from every woman we get a list with a ranking of the men that she prefers. We of course want people to be as happy as possible with their dates. Especially, we want the dates to be ‘stable’ so that it is not possible that people are going to change their date. With ‘stable’ I mean that it is not possible that a man and a woman both like each other more than their current date. In that case, they want to skip their dates and go with each other. Notice that this will not happen when some person likes another person more than his/her current date, but that other person likes his/her own date more. Furthermore, to make this problem a little bit easier, we assume that we have an equal amount of men and women. But the problem is, in the whole of Groningen we have thousands of people who are single. Would it even be possible to solve this problem? Does there even exist a possible combination in which no one is going to change their date?
Luckily, this combination does exist and there is a really smart algorithm to match all people. This algorithm is called the Gale-Shapley algorithm and it is named after its inventors David Gale and Lloyd Shapley. In 2012, Lloyd Shapley even earned the Nobel Memorial Prize in Economic Science for his work in the field of matching.
In this algorithm, we start off with all men making a proposal to their favorite woman. This means that some women might get a lot of proposals here and some may get none. All the women who got a proposal say “maybe” to the man who she prefers the most from all the men who proposed to her and she says “no” to all the others. Now we probably have some temporary couples and some men and women who still do not have a partner yet. Therefore, we continue to the next step where the same basically happens again. All the men who do not have a partner right now, make a proposal to a woman who they did not propose to before and who they prefer the most, even if this woman does have a partner at the moment. Now every woman who got a proposal will again make a choice. If there is a man who just proposed which she prefers over her current partner, she will choose the new man and her current man will become single again. After this step, the same happens again and again. In this way, the algorithm keeps iterating over the group until everyone has found a partner. And, as Gale and Shapley proved, this combination is always stable and the algorithm will always find it!
What I really like about this algorithm, is that it has really practical applications. There are variations of the algorithm which are used for the allocation of kidneys over patients or for the allocation of students over classes.
So, the only thing which is left for you to do, is to implement this algorithm in some programming language. You need to do this since the computations which are needed become really big when you want to do it for thousands of people. But after you have done this, the mayor will be really happy and Groningen will be filled with people who are dating. As you can see, algorithms can be helpful in almost every situation in your life.
This article was written by Stan Koobs
