Stable Matchings of students and high schools through Traditional Marriage Problem
Link: http://www.ams.org/samplings/feature-column/fc-2015-03
This article discusses about the matching between 8th graders and to the various high schools in New York City. The 8th graders would list their top 5 preferences of high schools they wanted to apply to, and the high schools would decide whether or not to accept, reject, or wait-list them. The students were notified of the admission decision and were allowed to accept only one acceptance offer and one spot on the waitlist. After the first round of decisions in which students would respond to any offers received, high schools with unfilled spots would send another round of offers. This process would continue on for a third round. However, this process had many issues, as after the third round, many students were not accepted into a school that was in their top 5 choices. In addition, this process would influence students to misrepresent their true preferences, as students would be scared that if they were rejected from their first choice, that their second choice school would be full during their second round of admission decision.
Economists Atila Abdulkadiroglu, Parag Pathak, and Alvin Roth designed a computerized algorithm to maximize the number of matchings between a student and the student’s first choice, and such algorithm draws its success from the principles of an algorithm developed by Gale and Shapley in 1962. This algorithm is known as the stable marriage algorithm, and the key to this algorithm is the idea of stability. A matching between a student and a high school is stable if “there is not a student and a school who would prefer to be matched with each other more than their current matches.”
In this stable marriage problem, we would like to arrange marriages between men and women so that with each marriage, there is not a man and woman who would prefer one another to his or her spouse. It is also important to note that there are equal number of men and women and that we do not consider same-sex marriage. Every man lists the women in order of his preference, and every women lists the men in order of her preference. In the first step of this algorithm, every man proposes to the first woman on his list. Every women looks at all the men who proposed to her and conditionally accepts the proposal from the men she most prefers. She rejects all others. Now, every man who is not matched to any woman proposes to the woman next on his preference list. Again, every women considers any new men who has proposed to her and any man she had previously accepted. They again accept the proposal from the man she most prefers, and this even implies rejecting the man she had previously accepted to. This process happens again until every men and women have a matching.
In fact, this algorithm produces a stable matching. We can prove that all the matches are optimal. Let’s suppose that a man m prefers a woman w1 more than his match with women w. That means in the algorithm, m proposed to w1 before to w. However, because m is not matched to w1, w1 must have rejected m because she prefers another man (i.e. m1) to m. Thus, m and w1 would never have preferred each other to their matches.
This algorithm can be further analyzed and be concluded that the matchings are male optimal but not woman optimal. More importantly, the dominant strategy for men is not to misrepresent his preferences of women.