Gaming theory helps place NYC Students in school of choice

The NY Times neatly reported on the use of Nobel Prize winning gaming theory in the perennial problem of matching New York's high school students with the school of their choice. Since all 75,000 NYC Middle-school students have the option of attending any of the 426 NYC schools and there are many over-achievers, a simple priority list like the college acceptance process used to result in many unhappy applicants.

 

So a group of professors got together and modified a gaming theory called "The Stable Marriage" for this purpose. In the early 1960s, the economists David Gale and Lloyd Shapley proved that it was theoretically possible to pair an unlimited number of men and women in stable marriages according to their preferences.

 

By running a series of rounds of proposals and acceptances with tentative acceptance sometimes being trumped by a rejection and acceptance of another suitor, all the men and women get matched up with someone within their range of preferences.

 

Below is a nice graphic showing the process simplified to ten students, three schools, each of which have three slots, three preferences and three rounds. In reality there are more of each variable but, with computerization, the process works the same.

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.

Sources: Academic papers, with assistance from Parag Pathak, Massachusetts Insitute of Technology

By Ford Fessenden