The Deferred Acceptance Algorithm
In the article “How game theory helped improve New York City’s high school application Process”, written by Tracy Tullis for the New York Times, Tullis explains the way in which economists Atila Abdulkadiroglu, Parag Pathak, and Alvin E. Roth used certain game theory alongside of matching market graphs to try and fix the sorting problem that left thousands of New York middle-schoolers devastated over the fact that they didn’t get into any schools. The New York High School application process goes like this: students put in a list of schools they are interested in in a computer program which, after school consultation, will assign placements. To most of us familiar with application processes we know that they come hand in hand with disappointment and unfairness. Not everyone can be happy – or can they? Theoretically, we can assume that students should always be able to get into at least one of their listed schools (even if it’s not their first choice –and in this case perfect matching is practically impossible). However, this is not true and here lies the problem: while some students receive no acceptances other receive a surplus of them. So, when a really good applicant gets into many different high schools including his first choice, he is taking up spots (spots he doesn’t intend on filling) that could have been allocated to students who would actually end up attending those schools. If we simplify the situation we can visualize the problem as a bipartite graph –on one side we have the hundred of schools and on the other the thousand of students – with many different constricted sets (the students who don’t get into their choices because their spots were given to others). Though not described like this in the article, the piece does allude to constricted sets by defining it as a “congested market.”
The economists mentioned set out to find a new design for the application process which would diminish the amount of restricted sets in the allocation process. The article describes a “deferred acceptance algorithm” meant to redesign this problem. The algorithm uses a certain game theory to match the students to one of their listed schools. It follows the same logic as the “stable marriage problem” which pairs young men and women based on their preferences. To explain this the article uses the example of the table below.
Here students submit up to three of their favorite schools (between 1, 2 and 3) in order of preference (listed next to the letters representing students). The tables show the three rounds meant to provide an end-game where students get the highest ranked school they listed that also wants them. Same logic applies to the stable marriage problem: we are looking for a stable matching in the marriage market where both people end up with the highest ranked person who also wants them. In game theory this is called a stable strategy –where all preferences are optimized. Here we can almost think of it as searching for a complex version of market-clearing prices… but we replace prices with an additional set of valuations. In essence, we’d have one valuation where the student lists their school preference and a second valuation (which can change depending on the round) where the school accepts or rejects the student. In the table the school valuations are present through checks and crosses. The goal is to go through enough rounds to end up with a graph considered stable.
We take for example students A, B, C, and D. We keep in mind that schools can only take three students. A, C, and D apply to their first choice 1 and get in the first round (so in the first round school 1 filled up all three spots). B only applies to two schools (2 and 1), and doesn’t get into his first choice (#2). B – being an unmatched student – is then paired with its next choice (school 1) which recognizes that B had to be paired with at least one school, accepts his offer, and rescinds its offer to D. Student D is then paired with his next choice : school 3. The game/algorithm goes on until we find a somewhat stable solution. This table clearly illustrates how the deferred algorithm works in order to optimize all student/school relations, but also shows how not everyone can be happy. If there are three spots for each three schools there are a total of nine spots yet there are ten applicants… So while we are finding more equal ways to allocate high-schools there is still some work to be done.
Nevertheless, this algorithm has proven its merit: “the first year that students were sorted this way then number of unmatched plummeted from 31,000 to 3000.”
We learned in today’s lecture that the proper term for this type of matching is matching with preferences using tables