Game Theory in School Admission as a Matching Problem
In class, we have extensively discussed matching markets and the problems of making satisfactory matchings. Matching markets can also exist as two-sided markets where each agent has a list of matching preferences for the agents of the other class. Realistically, many real-life matching markets involve preferences, such as the hospitals and residents matching problem. One such problem is the stable marriage problem. In this problem, there are multiple rounds; in each round, men propose to their highest preference woman that they didn’t propose to in previous rounds; the woman may accept the proposal if she prefers that man to her current arrangement, or she can reject them. This continues until all men and women have been matched, and it has been proved that this matching is a stable matching (there is no pair of a man and woman that both prefer each other to their current partner, leading to a ‘divorce’). Furthermore, it has also been proved that such a matching is optimal for the men (each man receives his highest-ranked partner that leads to a stable matching).
The linked article describes a similar dilemma of matching NYC high school students with schools. Under the ‘old’ system, students would rank five schools that they wanted to attend in order of preference, and the schools would then extend offers of admission to students in one round. The issue is that many high-achieving students would receive multiple offers from high-ranking, while thousands would not receive any. This setup actually discouraged students from ranking their true preferences, since many high-ranking schools only extended offers to students who also ranked them as first. To see why, we can consider each student as a ‘player’ in the high school admissions game. Then, we can say each student gets a payoff of p1 from being accepted to his/her top choice school, p2 from his/her second, etc. up to p5 for his/her fifth choice school (where p1 > p2> …. > p5 > 0), and a payoff of 0 for being unmatched. Each player wants to maximize his/her own payoff, but the payoff depends on the strategies of other students. If enough other students apply to school p1 that the player believes has a higher chance of being accepted, then the player should switch his/her strategy to ranking p2 first, and repeat the process. Ultimately, this results in many students ‘playing it safe’ to avoid being unmatched and receiving a payoff of 0, without attempting to try for their true top-choice schools.
To solve the issue of both many students being unmatched and many students being matched with schools that are not their true preference, three economists proposed a model similar to the stable marriage problem. This draws parallels to the high school admission problem, and the economists designed an algorithm similar to the stable marriage problem algorithm. First, they increased the number of schools that students are allowed to rank from 5 to 12, allowing a more accurate matching (since schools are able to rank every student that applies, limiting the preferences of the students limits the number of matchings that can be made). In their algorithm, the students are the ‘men’ and the schools are the ‘women’ (as in the problem described . In each round, students essentially ‘propose’ to their highest ranked school that they have not ‘proposed’ to yet. Schools are able to accept the student or reject the student based on their own rankings; if it accepts the students, it may reject previously accepted students if it favors the new student over them. The rounds continue until each school has accepted the maximum number of students.
However, even though some students still end up unmatched (as in the original marriage problem), this new algorithm has reduced the number of unmatched students from the order of thousands to hundreds. Furthermore, this algorithm is optimal for the students! Since the students assume the role of the ‘men’ in the original marriage problem as described above, each student will be matched with his/her highest-ranked school that results in a stable matching. And, as the article mentions, this algorithm encourages students to give their rankings in a true preference order, so it does not penalize students who want to try for top schools but are afraid that being too ambitious will lead to them being unmatched.
This article demonstrates how game theory and matching problems are extremely relevant to many real-life scenarios. In many markets, the goal is to maximize the amount of matchings that are made so that the most agents are satisfied; this applies to organ donation markets, hospital/resident matching, and, of course, school admissions. Leveraging an understanding of matching markets allowed economists to maximize the matchings between students and schools. Additionally, it removed much of the necessity for students to base their own application strategies off of the choices of other students, or ‘players’. Instead, students are able to choose a dominant strategy of ranking their own true preferences, since the choices of other ‘players’ do not affect their own payoff. Overall, this has led to a much better process for high school admissions matching in NYC.
Link: https://www.nytimes.com/2014/12/07/nyregion/how-game-theory-helped-improve-new-york-city-high-school-application-process.html?