As you may have read in the news recently, Lloyd Shapley and Alvin Roth just won the 2012 Nobel Memorial Prize in Economic Sciences for their work on the Gale-Shapley Algorithm. The Algorithm is a formal matchmaking system that is currently used to pair up medical students with residency programs. Back in the 1960s, when Gale and Shapley first publicized the algorithm, they demonstrated how their algorithm would work by using it to efficiently pair of men and women. Imagine a ball with an equal number of men and women. Each man has a order list of his preferences of women and each women has a list of preferences of men.
The Gale-Shapley algorithm sought to create an optimal mating scheme for the ball, but first they had to ask, "what would be an optimal outcome?" They came up with the term "stable" to describe a mating scheme in which no pair of paired-people would prefer each other to their own parters. That is, no two unpaired would like to rudely leave their own partners on the dance floor to go dance with another. It is important to note that there can be plenty of men and women in the Gale-Shapley Algorithm who would rather be with someone else than their own parter, however, because the scheme is stable, that desired person would rather be with his or her own parter than this unhappy person, thus the scheme is optimal.
"Well how does this magical algorithm work", you ask? Well, it's actually pretty simple. Maybe even so simple that by the end of this post you'll think, "They got the Nobel Prize for that?" It goes like this: In the first hour, each guy approaches his first choice girl and asks her to dance. Each girl that is approached rejects all of her suitors but the one highest on her list. She doesn't accept him just yet, but she continues talking to him, disallowing him to ask other girls to dance. In the next hour, each rejected male will approach the next girl on his list. Again, each girl will look at all of her suitors, including the one she may have kept from the previous hour, and she rejects all but the one highest on her list. This process will continue until every boy is paired of with a girl. We can prove this marriage is stable as follows: Assume for the sake of contradiction that the not-coupled pair Alice and Bob prefer each other to their own partners. However, because Bob prefers Alice to his own partner, this means that Bob must have approached Alice before he approached his own partner. Yet, because Alice and Bob are not paired together, that means that Alice must have rejected Bob in favor of another suitor, say Charlie. Now, because of how the algorithm works, Alice is either paired off with Charlie or someone she likes better than Charlie. Thus she could not prefer Bob to whomever she is paired off with and we have reached a contradiction.
It is interesting to note that this algorithm, as it is, optimizes for each boy individually. That is, there is no boy that could say that things could have worked out better for himself without creating an unstable pair, or a pair of two people that prefer each other than their current partners. However, this system in which guys go down their list-of-girls and girls go up their list-of-guys, is not as favorable to women as it could be. If they collude, women can arrange things greatly in their favor.
So now, instead of a ball with an equal number of hapless boys and girls, imagine a scheming group of girls that form a sorority. Each girl is told to go out and find one unique boy that they want as their number-one-choice boy and write his name on a list to invite him to their Gale-Shapley party. And by "unique", I mean that no two girls can invite the same boy. The ingenious leader of this sorority writes her own first choice boy on the list. However, she doesn't stop there. She also writes the name of one more boy to list of invitees. This boy is known throughout the sorority as the Universal Boob. That is, he is a nice guy that every girl likes, but that no girl has the hots for. So each girl agrees to put this Boob second on their list of preferences. Lastly, this scheming sorority invites one final person to their party: an unattractive girl named Ugla who they all know will be the last choice on every boy's list.
Let's examine how this rigged Gale-Shapley party will play out. The first question to ask is: Who will end up with Ugla? With a bit of reasoning, it becomes obvious that the only person that could end up with Ugla is the Boob. To see why this is, assume for the sake of contradiction that Ugla ends up with a boy other than the Boob. However, this non-Boob boy is the first choice of another girl. And because Ugla is the last on every boy's list, that means that this non-Boob boy must have approached the girl that likes him most before he approached Ugla. And if he did approach her first, then he would have ended up with her. Thus we reach a contradiction which means that the Boob always ends up with Ugla. So with a bit of scheming, a sorority of girls can each go home with their first choice boy, each boy thinking that they have ended up with their optimal mate and none the wiser.
Most of the above post was taken from a talk given by Prof. Peter Freyd on 12/5/12.