How Game Theory Helped Improve New York City’s High School Application Process
As a yearly ritual, eight graders from New York City middle schools begin the process of applying for a spot in high schools. While the actual application process may take days of hard work, the sorting algorithm that assigns students to high schools only takes a fraction of a second for each individual. However, there seems to be a fundamental flaw in the sorting algorithm. Thousands of high performing students got matched to more than one high school while nearly half of New York City’s eight graders got no match at all. Before 2004, up to 31,000 students did not get matched to a high school, and, as a result, have to go through the grueling process in the summer to get matched again. Due to the algorithm’s inefficiency, NYC invited experts in Game Theory, Atila Abdulkadiroglu (Duke), Parag Pathak (M.I.T.) and Alvin E. Roth (Stanford), to redesign the sorting algorithm. The new sorting algorithm worked extremely well compared to the previous algorithm, bring the number of unmatched students each year to about 3000. Professor Roth earned the Nobel Memorial Prize in Economic Science in 2012 as a result of the new sorting algorithm.
The basis for this new algorithm is the deferred acceptance algorithm, which is a solution to the famous problem in economics: the stable marriage problem. In the algorithm, each suitor proposes to his first choice mate while each woman rejects all proposals but her favorite. If the suitor gets rejected, he will then propose to his second choice, and so on, until every person is matched. This solution is stable because the woman is able to accept a proposal that she desires later than the proposal she has previously considered. This algorithm is scaled up and tweaked for use in NYC’s high school acceptance sorting algorithm in which the suitor is analogous to the applicants and the woman is analogous to the high school. The applicants would rank the high schools in order of preference while the high schools would have their own ranking of applicants. In the first round, the students would be evaluated for their first choice school and receive a rejection or tentative acceptance. The students would move to second round when they will be evaluated at their second choice schools. This process would continue until ideally every person is matched to a school. The key success of this algorithm is “mutuality”, since students are able to “get their highest possible ranked school that also wants them there” (Tullis, 2014). The dominant strategy for the students is to simply apply for the highest ranked high school (ranking high schools in true preference order). Since the high schools accept students solely based on student rankings, applying for the highest possible ranked high school represents the best scenario for both the high school and the student (Nash Equilibrium). There is no point in trying to outsmart the system by putting the first choice high school second.
This game model does not consider the lack of resources that the poor and immigrant children face. They tend to apply for lower-ranking schools and rank them as top choices.
Source:
http://www.nytimes.com/2014/12/07/nyregion/how-game-theory-helped-improve-new-york-city-high-school-application-process.html