What could matching have to do with New York City High Schools?
Given how many New York City kids come to Cornell, we know how competitive it is to get accepted into a specialized high school there. Prior to the current system, students submitted their top 5 schools, hoping to get a match. While some high achieving students got to pick between more than one school, most students were lucky to get one, while many got none at all, making for an inefficient market that forced students to rank safer choices, rather than aim for a high school at a risk of not getting in.
This article summarized the computer system implemented in 2003 by Atila Abdulkadiroglu, Parag Pathak, and Alvin E. Roth, who sought to resolve this issue– a system that won those professors a Nobel prize! Through their system, students ranked their schools in order and the schools prepared their list of students in order as well. Mutuality ensured that schools and students were paired such that students got their highest-ranked school that also wanted them. Here, a student’s dominant strategy would be ranking the schools in their true order, according to Abdulkadiroglu.
Under the new system, we can imagine this system as a matching problem.
A perfect matching is “an assignment of each item to a different person so that each person is linked to an item they are willing to take. This is ensured by mutuality. In the context of INFO 2040, we can imagine the schools as items and students as people. We can also assume that each student’s value for a school is proportional to their ranking for it (higher ranking meaning higher valuation).
For simplicity, we could imagine Students A, B, C and Schools X, Y, Z where Student A ranks School X the highest (valuation = 3), B ranks Y as their top choice (valuation = 3), and C ranks Z (valuation = 3). If those schools also rank those students mutually, then the total market value is (3+3+3) + (3+3+3) = 18, and thus optimized. Everyone wins and gets their top choices, however it is not this simple.
Say, in another example, the students rank the schools the same way, but School X wants Student B, Y wants A, and Z wants C, then the only mutual first-choice pairing is between School Z and Student C. From there, mutual rankings must again be reassessed until all matches are paired, and done so in a way that optimizes the market value as well!
Of course the situation is not as simple as having equal numbers of students and schools, but the concept of perfect matching can help us start to understand how the matching algorithm behind the New York City high school application process!