New York City’s High Schools and Game Theory
Every year, there are approximately 80,000 eighth graders in New York City who need to choose from amongst 700 high schools when the graduate. Alvin Roth, Nobel Prize winner for economics, designed a system based on game theory to facilitate this process. Before Roth came up with his system, each student would submit a list of their top 5 choices of schools, and each of those schools would see their lists. There was an issue here because if a school saw that a student didn’t rank their school first, then that school wouldn’t consider that student. Because of this, the students actually only had one choice of school.
To resolve these issues, Roth used a method called the deferred acceptance algorithm, which is based off of game theory. The algorithm is very complex but can be easily explained in the context of matching men and women who want to get married. Each man proposes to their first woman of choice and then the women only take one and reject the others. Then, the men who get rejected make new offers in order of their preferences until they get a woman. Any man who doesn’t get someone to marry when they go through their list of preferences has another round in which they can list more preferences based on the women who are still available. If there are any more men leftover from this round, another round can occur.
In the New York City school system, the men are equivalent to the students and the women to the schools. From this, Roth came up with a system in which the students list up to 12 of their top choices in order of preference and included three rounds of choosing so that all students . Because of this the amount of students involved increased from 66% to 93%. The New York City school system still uses Roth’s algorithm and it has shown to be very fruitful.
Sources:
1) http://www.forbes.com/forbes/2010/0809/opinions-harvard-alvin-roth-freakonomics-ideas-opinions.html
2) http://isites.harvard.edu/fs/docs/icb.topic781759.files/10.%20School%20Matching%20Systems.pdf