The New York City High School Search: A Matchmaking Algorithm
The New York City high school search is a competitive process, where students have preferences on where they want to go, and high schools have preferences on who they want to accept. The process used to be inefficient and chaotic; each student would list five preferences, and some students were matched with multiple schools and had the option to pick between them, whereas other students were matched with none.
In order to improve this process, three economists designed a matchmaking algorithm in order to maximize preferences. It was called a deferred acceptance algorithm, and it was based on mutuality. Each student and school submits an ordered list of their preferences, then after different rounds, the student is ultimately matched with their highest-ranked school that also wants them. The key idea is that the computer algorithm goes down the list of each of the students’ rankings in order, and tries to make a match with the students’ top-ranked schools. The schools can either accept or reject the students; in the case of a rejection, the computer looks at the next school on the students’ list, and the process repeats. The match is not finalized until the very end of the process.
This connects to the class discussion of matching markets and finding optimal assignments. We can see that the high school search is a matching market because there are two sides, the students and the high schools, who both want to be matched with the other. The algorithm discussed tries to find a perfect matching so that there are no constricted sets and each student and high school are happily paired together. Further, there is also a connection to game theory because some students may strategize how to list their preferences by making predictions on other’s behavior and how they think they rank on different school’s lists.
Article: https://www.nytimes.com/2014/12/07/nyregion/how-game-theory-helped-improve-new-york-city-high-school-application-process.html