The Deferred Acceptance Algorithm: The Economics of Matchmaking in the High School Application Process
Over the past few decades – as the nation’s college application process becomes increasingly selective, thereby making it more difficult for aspiring students to attend the schools of their choice – the New York City high school application process has adopted an algorithm that works to ensure more students get into the high school of their choice. A little over a decade ago, the original process of high school selection consisted of each student composing a list of five schools they would prefer to attend, and then simply hoping they got matched with a school that was on the list they had submitted. Unfortunately, through this system nearly half of the students were assigned to schools that weren’t even on their list. However, with the help of economists Atila Abdulkadiroglu, Parag Pathak, and Alvin E. Roth, the number of prospective students who were assigned to schools they hadn’t selected dropped from 31,000 to just 3,000. How were they able to drastically fix such an apparently flawed process? Through the application of a renown economic concept known as the stable marriage problem.
Abdulkadiroglu, Pathak, and Roth were able to take the solution to the stable marriage problem – known as the deferred acceptance algorithm – and apply a manifestation of it to the high school application process through a matchmaking system composed of a series of rounds. In this system, students select their preferred schools in order, while schools compose a list of students whom they would accept. Then, through a series of rounds, students are eventually matched with the highest-ranking school that will accept them. This process has continuously proven itself more effective at efficiently placing students in the schools that best fit them than the previous process. The first year that the deferred acceptance algorithm was used, approximately half of all students were assigned to their first-choice schools, with a third of students placed at their other highly preferred schools.
This article relates to the content discussed in this course because it contains elements of game theory as well as bipartite graphs. The algorithm is designed with the goal of coming as close to a perfect matching as possible. Although it’s not truly possible that every student gets matched with one of their top choice schools, the algorithm comes extremely close to ensuring that each student is placed at the best school that will accept them. While it is not explicitly stated in the article, the components of this class regarding matching value are essential to the algorithm to function efficiently. In a sense, the algorithm is looking to assign students to schools so that the matching value of the graph is as high as possible.
Link to article: https://www.nytimes.com/2014/12/07/nyregion/how-game-theory-helped-improve-new-york-city-high-school-application-process.html