How Game Theory Helped Improve New York City’s High School Application Process

Original Source: https://www.nytimes.com/2014/12/07/nyregion/how-game-theory-helped-improve-new-york-city-high-school-application-process.html

By Tracy Tullis

Dec. 5, 2014

Tuesday was the deadline for eighth graders in New York City to submit applications to secure a spot at one of 426 public high schools. After months of school tours and tests, auditions and interviews, 75,000 students have entrusted their choices to a computer program that will arrange their school assignments for the coming year. The weeks of research and deliberation will be reduced to a fraction of a second of mathematical calculation: In just a couple of hours, all the sorting for the Class of 2019 will be finished.

To middle-school students and their parents, the high-school admissions process is a grueling and universally loathed rite of passage. But as awful as it can be, it used to be much worse. In the late 1990s, for instance, tens of thousands of children were shunted off to schools that had nothing going for them, it seemed, beyond empty desks. The process was so byzantine it appeared nothing short of a Nobel Prize-worthy algorithm could fix it.

Which is essentially what happened.

About a decade ago, three economists — Atila Abdulkadiroglu (Duke), Parag Pathak (M.I.T.) and Alvin E. Roth (Stanford), all experts in game theory and market design — were invited to attack the sorting problem together. Their solution was a model of mathematical efficiency and elegance, and it helped earn Professor Roth a Nobel Memorial Prize in Economic Science in 2012.

Before the redesign, the application process was a mess. Or, as an economist might say, it was an example of a congested market. Each student submitted a wish list of five schools. Some of them would be matched with one of their choices, and thousands — usually the higher-performing ones — would be matched with more than one school, giving them the luxury of choosing. Nearly half of the city’s eighth graders — many of them lower-performing students from poor families — got no match at all. That some received surplus offers while others got none illustrated the market’s fundamental inefficiency.

Thousands of unlucky teenagers wound up waiting through the summer to get placed, only to be sent to schools they had not listed at all. And those schools, Professor Pathak discovered in a recent analysis, were “worse in all dimensions” — including student achievement, graduation rate and college admissions — than the schools the students had asked to attend.

Even more bizarre, the system encouraged safe, rather than ambitious, choices. Some sought-after schools accepted only the applicants who had made them their first choice. So students who aimed high and listed several such schools but were rejected by the first could blow their chances all the way down the list.

To address this flaw, the Education Department’s high school directory advised students to “determine what your competition is for a seat in this program"— a vexing task for even the best-informed among them.

Matchmaking With the Help of Game Theory

In 2003, New York City changed its method for matching eighth graders to high schools with a system, called a deferred acceptance algorithm, that was designed by a team of professors, including one who later won a Nobel prize in economic science. The key feature was mutuality: 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. Here, in simplified form, is how it works. In this example, each school can take three students, although it can list more, and each student can list up to three choices.