Playing Matchmaker for Students and High Schools
In an article from the New York Times, game theory and matching appear in the form of solving New York City’s high school application process nightmares: http://www.nytimes.com/2014/12/07/nyregion/how-game-theory-helped-improve-new-york-city-high-school-application-process.html.
Before a matching algorithm by economists Atila Abdulkadiroglu (Duke), Parag Pathak (M.I.T.) and Alvin E. Roth (Stanford) was created, NYC would have students select several schools in order of preference. Some would get a school they had listed, but the most common situation was that high performing students were offered spots in several schools while thousands were not offered a place in any school. Thus, there was a struggle to find a perfect matching between the open spots in high schools in NYC and middle school students (rising high school freshmen). There were so many problems that even when students listed preferences, they would receive matchings to schools they had not listed at all. More problems in accounting for preferences arose as well:
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 think about it in terms of the tables we’ve seen in class, the value to schools of a student’s application was 100 if the student had made them their first choice, but 0 otherwise. In such a situation, methods such as maximizing the total sum of the values that we’ve discussed become very difficult with such extreme numbers. At this point, some game theory gets involved: students were asked to find out about their competition and their possible choices to then make their choices accordingly. But for middle school students, finding this information is difficult, let alone acting on it.
A possible solution in other circumstances for scarce resources would be to mimic an auction: give the opportunity (the item in this case) to the person willing to pay the highest price. But in a situation concerning education, limiting opportunities as a result of (a lack of) wealth is socially and morally unacceptable. Thus, an auction was not a possibility for this problem.
In order to find an alternative solution, professors Abdulkadiroglu, Pathak, and Roth were enlisted to create a match making algorithm to more efficiently match students and spots within high schools. The result was the “deferred acceptance algorithm.” In this algorithm, a program would point students to their listed preferred schools. The schools would then “reject” all the students except the one most highly valued for a spot in the school, but would not accept them. Instead, the student would still be associated with the school (in the program), and another round of matching would start. If the student from the first round was still the most valued by the school, they would keep that student as a possible match. If another student appeared who was more highly valued, the previous student would be rejected and the newer student kept as a possible match. This would continue until most students were matched.
Once put into use, the number of unmatched students went down to a tenth of the number it was the year before: from 31,000 to 3,000 students. More students were matched to their first and second choice schools. Overall, there was a marked improvement as a result of finding an optimal matching strategy. Nevertheless, there are still problems in that low-income and low-performing children were more likely to be matched to underfunded schools. The algorithm was effective, but not necessarily socially equal. Thus, although matching can find connections between sets, it cannot necessarily solve economic or social problems in all cases.