Matching Markets and NYC High School Admissions
Main Article, written by the 2012 Nobel Memorial Prize cowinner in Economic Science Alvin Roth (fun fact: he went to NYC public schools growing up): http://tinyurl.com/hnl8lyg
Supplementary Articles on the topic: http://tinyurl.com/oexwozm and http://tinyurl.com/jgz4s2k
The article “Why New York City’s high school admissions process only works most of the time” by Alvin Roth details of the application process to New York City public high schools. For those unaware, New York City has hundreds of public high schools and every year eighth graders list their twelve favorite schools in order of preference. Up until 2003, the city’s system for pairing students with schools was dysfunctional in that it left about a third of rising high schoolers without a high school assignment just before the academic year. Meanwhile, many high-performing students would receive offers to multiple schools. In 2003, a new system was introduced to pair students with schools. This system, pioneered in part by Alvin Roth, works by pairing schools and students who show mutual interest in one another. The first year the new system took affect, the number of unmatched students dropped from 31,000 the previous year to around 3,000.
One can think of the New York City public high schools admissions process as a sort of market, except instead of buyers and sellers the entities in question are students and schools. A bipartite graph can be generated wherein nodes on one side are students, and nodes on the other side are available spots at high schools. The ultimate goal is for each student to be paired with a distinct available spot: a perfect matching. In our text, such a perfect matching was generated by input from the buyer on how much they were willing to spend. Over time a perfect matching develops from systematic changes in price. The NYC high schools case differs in that such a perfect matching is deduced not only by input from the student (by ordering their twelve favorite schools in order of preference), but also by the schools (by systematically accepting or rejecting students, who then get considered for their next preference school and so on). This sort of system, wherein students and schools mutually accept each other based on preference, employs what is known as a deferred acceptance algorithm.
The case study for deferred acceptance algorithms is called the Stable Marriage Problem. The problem is explained as such: there are two groups, each of equal size and consisting of solely men or solely women. Every woman is to be paired with exactly one man and vice versa. Every person has a predetermined ranking of members of the opposite sex. The algorithm works as such: men first propose to their most favored woman, who can either reject him or give him a tentative acceptance (a “maybe”). If rejected, the man then proposes to his next most favored woman and so on. If given a “maybe,” the man and woman in question are “provisionally engaged.” The next round, if the woman is proposed to by a man who she ranked higher, she gives this new man a tentative acceptance and he becomes her new provisional partner. The remarkable thing about the deferred acceptance algorithm as applied to this problem is that in the end, the set of partnerships generated is stable. “Stable” in this context means that there are no two people of opposite sexes who would both rather have each other than the partners they are ultimately paired with. The deferred acceptance algorithm as applied to the NYC high schools admissions process is precisely this process except students are “proposing” to high schools, which either reject or tentatively accept them. The key word in both cases is tentative. No pairing is set in stone until the very end of the process, which is where the beauty and strength of the algorithm lies.
Of course, the issue with using a deferred acceptance algorithm with high school admissions is that the size of the set of students and the size of the set of available seats are unequal, so by definition a perfect matching cannot exist between them. Still, it’s notable how a sophisticated algorithm with applications in mathematics, computer science, and economics was implemented to help solve a real-world problem.