Game Theory and Perfect Matching in the New York City High School Process
The New York City high school admissions process, for the majority of families, is extremely challenging, and has been for a very long time. In fact, until recently, the process was much worse. Tens of thousands of children were placed into schools that they had not even applied to, let alone were interested in. To conquer this problem, three economists (Atila Abdulkadiroglu, Parag Pathak, Alvine Roth) came up with a mathematical model that created an algorithm to smoothen the high school process: “Students submit a list of preferred schools in order, and schools prepare an ordered list of students whom they want or who meet their standards. After rounds of computer matching, schools and students are paired so that students get their highest-ranked school that also wants them.”
According to Networks, Crowds, and Markets: Reasoning About a Highly Connected World (David Easely and Jon Kleinberg), “Game theory is concerned with situations in which decision-makers interact with one another, and in which the happiness of each participant with the outcome depends not just on his or her own decisions but on the decisions made by everyone” (156). We see game theory play out in this situation: the payoff of the participants (in this case, students), depends not just on their rankings, but on the rankings of other students. In other words, the optimal placement of an individual student depends not only on their own trajectory, but on the trajectory of their peers.
There is also an element of perfect matching to this problem. Perfect matching, in graphical terms, is defined as follows: “When there are an equal number of nodes on each side of a bipartite graph, a perfect matching is an assignment of nodes on the left to nodes on the right, in such a way that (i) each node is connected by an edge to the node it is assigned to, and (ii) no two nodes on the left are assigned to the same node on the right” (279). To put this situation into more graphical terms, the students are nodes on the right and schools are nodes on the left. The edges represent a student’s acceptance to a school. In this case, to ensure perfect matching, the system utilizes three rounds and makes students rank their top three choices of schools. In the first round, the schools can either accept or reject the student; if the student is accepted to their top choice, they are done with the process. Unmatched students are placed into the next round of matching; like the first round, if they are matched with their second choice, they are done with the process, though those unmatched continue the process. This process goes on until all students are matched with a school. About 90% of the students are ultimately matched with one of their top three choices, but the other 10% continue the process until they are matched with a school, regardless of its rank.
This is just one of many examples of how game theory and perfect matching can help improve a flawed system in the government.
https://www.nytimes.com/2014/12/07/nyregion/how-game-theory-helped-improve-new-york-city-high-school-application-process.html