In 2015, the city of Amsterdam implemented an algorithm-based system to allocate children to secondary schools, inspired by a globally successful school admission mechanism. However, minor modifications to the algorithm have inadvertently led to unintended consequences, favouring privileged families, and creating frustration among parents. In this blog we examine how small changes in design details can have profound impacts on the outcomes of matching algorithms.

Matching Markets

There are various allocation problems that cannot and should not be resolved solely through monetary exchanges. These challenges can be effectively addressed by employing game theoretical approaches. These allocation problems commonly arise in matching markets, which have been extensively explored by researchers in the field of Market Design. One notable example of such an allocation problem is the matching of children to educational institutions like schools or kindergartens.

At first glance, the allocation of children to schools may appear to be more of a socio-political issue, rather than an economic one. Nevertheless, the application of game theory has proven to be highly advantageous in these contexts. By leveraging game theory as a theoretical foundation to understand incentives, sequences of actions etc., experts specialising in Matching Markets analyse and develop algorithms that offer practical solutions to address specific allocation problems.

Gale Shapley Algorithm

In the realm of school choice, the Gale-Shapley Algorithm stands out as the most widely utilised and extensively researched mechanism. Within this mechanism, students are required to rank their preferred schools based on their personal preferences. In the initial round, students make virtual offers to their top-choice school, while schools provisionally accept as many offers as possible, taking into account their priorities among students. In the subsequent rounds, students who were not assigned to their first-choice school proceed to make offers to their second-choice school. As the offers made in the first round were merely tentative, these students now compete with those who were already allocated to their first-choice schools. Once again, schools tentatively accept offers in line with their own priorities. This iterative process continues until all children are either assigned to a school or rejected by their least preferred school.

The Gale-Shapley Algorithm’s success can be attributed to its fulfilment of two crucial criteria, identified by Market Designers when implementing a matching mechanism: stability and strategy-proofness.

Firstly, the Gale-Shapley Algorithm ensures “stability” in the context of school admissions. This means that the preferences of cities and schools are consistently satisfied. In simpler terms, if my child has higher priority than my neighbour’s child for a specific school (due to factors such as better grades or social criteria), it is impossible for my neighbour’s child to secure a place at that school if my child fails to secure a place, especially in a school that my child prefers. While this may seem like an obvious requirement, most commonly used matching methods, such as the Boston mechanism or decentralised mechanisms, fail to fulfill this criterion.

Secondly, the mechanism is “strategy-proof,” implying that parents do not need to engage in strategic considerations when submitting their school preferences to the city. Unlike many other mechanisms where it may be advantageous to omit highly popular schools where one expects their child to have limited chances of admission, the Gale-Shapley Algorithm always incentivises truthful reporting.

In summary, an allocation mechanism exists that is transparent, easily comprehensible, and possesses all the necessary attributes for a fair and efficient allocation of children to schools. The Gale-Shapley Algorithm not only meets these requirements, but has also been proven successful through extensive implementation and analysis.

Amsterdam school admission

To implement a fair and efficient school allocation system, the city of Amsterdam embraced the renowned Gale-Shapley Algorithm in 2015. However, in an attempt to fine-tune the process, two additional mechanisms were introduced, inadvertently undermining some of the algorithm’s positive features:

1. “Reciprocal” Priorities of Schools: In a select few schools, students receive priority only if they have ranked those schools as their top choice. This introduction of reciprocal priorities has introduced a new layer of complexity to the decision-making process for students and parents. In some cases, it may be strategically advantageous to rank a school as the first preference, even if it is actually the second preference. This strategic move comes into play when a student perceives their chances of admission to their true first choice as low. By ranking the second choice first, they increase the likelihood of securing a place there, and if not, they maintain equal chances in all subsequent preferences.
2. The “Tail Improvement” Mechanism: Initially, 4% of available spots are reserved and subsequently allocated to students who were either not assigned any school or received their lowest-ranked preference (12th choice). If vacancies remain, they are then allocated to students who were assigned their 11th choice, and so on. This mechanism has unintentionally created complexities in the decision-making process. Some parents have discovered that they can outsmart the system by strategically placing highly sought-after schools in their preference list between ranks 3 and 12. This tactical maneuver ensures that they either secure one of their two top choices during the initial allocation or, if initially assigned an unfavuorable school, benefit from being reassigned to their first choice through the “Tail Improvement” mechanism. Consequently, well-educated and well-informed families gain an advantage in navigating this nuanced system.

Remarkably, to level the playing field and counteract the advantage enjoyed by more privileged families, Dutch NGOs now even provide tips to parents on how to navigate the system effectively. They offer resources, including instructional videos, on how to “play” the allocation system.

While this may appear equitable, it carries unforeseen consequences. If a significant number of parents begin incorporating these strategic considerations, it could result in a large portion of students not being matched at all (or to their 11^th or 12^th choice), leading to unfavourable outcomes even after the “Tail Improvement” Mechanism is applied.

This highlights the unintended consequences of introducing non-strategy-proof elements to the mechanism, namely creating a sense of insecurity among parents and needlessly complicating what was originally intended to be a straightforward process.

This case serves as a reminder that even minor deviations from a strategy-proof mechanism can have far-reaching implications. In the pursuit of fairness and simplicity, it is crucial to carefully assess the potential consequences of introducing additional complexities, ensuring that the allocation system remains transparent and accessible to all stakeholders.