In many places around the world, schools select their students via automated systems. These systems consider factors such as the schools’ capacity, proximity of the school to the students’ homes, and the students’ grades from previous education. Often, these systems also take the students’ preferences into account. This is usually done asking the students to submit a ranking of their preferred schools. An important feature of such systems is ensuring that students (and their families) report their rankings truthfully rather than attempting to “game the system” for their benefit. If it is possible to game the system, fairness becomes an issue for students who do submit their true rankings, as they are at a disadvantage. Moreover, families with better information or more resources are often in a stronger position to manipulate the system to their advantage, which can amplify social inequity in a community. Can the system be designed in such a way that it cannot be cheated?
First, let's consider a system that was widely used in Boston in the 90's and the 00's, the so-called Boston School Choice Mechanism. Here's how it works, step by step:
Students submit a ranked list of schools, with their top choice, second choice and so on.
In the first round, students are considered for their top-choice school. If more students apply than there are seats, a priority system (like living nearby) determines who gets in. Once the school is full, any remaining students move to the next round.
This continues until every student is assigned a school or all seats are filled.This continues until every student is assigned a school or all seats are filled.
A key feature of this mechanism is that once a student is assigned to a school, that assignment is final. This creates opportunities for strategic manipulation. Take the following fictional example: Harjot dreams of going to Tangent Tech, a popular school that gets many applications. She puts Tangent Tech first and Cosine College, a respected school, second. She lives close to Cosine College, so she receives priority for this school in case there are more applicants than seats. Francesco also dreams of going to Tangent Tech. He lives close to Sine School but prefers Cosine College even though it is far away. He tries to cheat the system: the chances of him getting into Tangent Tech are small. He decides to be dishonest and put Cosine College first, even though it is not his true preference.
What happens? In the first round, he gets into Cosine College and it happens to fill up. Harjot gets rejected from Tangent Tech and moves to the next round. Sadly, Cosine College is full in the next round and Harjot is forced to go to Sine School, a school she does not like and is far away.
This example uses only three schools. Now imagine there are two, three, or more highly popular schools that you would ideally apply for. Putting several of such schools on top of your ranking can make you extra vulnerable to 'strategic rankers' like Francesco.
This kind of manipulation is a major flaw in the Boston mechanism. In fact, it became so common that parents in Boston were advised to “game the system” by ranking schools strategically. As Pathak and Sönmez (2008) report, a well-organized parent group in Boston advised their members to adopt strategies like the following:
“One school choice strategy is to find a school you like that is undersubscribed and put it as your top choice, OR, find a popular school you like and rank it first, and choose a less popular school as a ’safe’ second choice.”
Can we remedy this situation and design a mechanism where students are encouraged to rank their school preferences honestly? Luckily game theory, the study of how individuals (or agents) make decisions in strategic situations, has a dedicated “branch” focusing on creating rules for games that encourage players to be honest about their preferences called mechanism design. Ideally, the rules are set up so that telling the truth is the best strategy for each player, no matter what others do, a concept called truthfulness or strategyproofness. In many social choice settings, this is not an easy task and the literature on the topic usually focuses on proving that truthfulness is impossible to achieve in a meaningful way.
Fortunately, this is not the case for school choice, as a mechanism called Deferred Acceptance (DA), from 1962 and designed by David Gale and Lloyd Shapley, offers a solution. DA can be implemented as a truthful mechanism, meaning it encourages students to rank schools based on their true preferences1. Here’s how it works:
Each student applies to their first-choice school. The schools tentatively accept students based on their available spots and priority system (such as proximity or siblings already attending). Any students who aren’t accepted move to the next round.
In the next round, students who weren’t accepted reapply to their second-choice school. Schools re-evaluate and may replace lower-priority students with higher-priority ones if necessary.
This process continues until all students are matched with a school or there are no more spots available.
What happens if Harjot and Francesco are assigned using DA? In the first round, Harjot is again rejected from Tangent Tech and Francesco is tentatively assigned to Cosine College. In the second round, Harjot knocks on Cosine College's door and replaces Francesco, because Harjot has priority over Francesco. In the next round, Francesco is rejected from Tangent Tech because it is full and he has no priority. In the third round, he is assigned to to Sine School.
The power of the DA mechanism is that students will always receive the best match possible based on the choices they submit and we can prove this mathematically! But what does this mean? Francesco was better off lying under the Boston School Mechanism. But the resulting assigment is unstable. A school-student assignment, also called a matching, is unstable when a school and a student prefer each other compared to their current matches. Consider again the case where Francesco is at Cosine College. Cosine College prefers Harjot over Francesco and Harjot prefers Cosine College over Sine School. If Cosine College ignores the mechanism and enrols Harjot, both Cosine College and Harjot are happier. In a stable matching this never happens; no school-student couple is better off circumventing the mechanism.
Now we can mathematically prove the following: for every student, the school they are assigned to is the highest-ranked school they can possibly get in stable matching. This means that if Harjot is assigned her second school, Cosine College, there exists no stable matching where she is assigned her first choice, Tangent Tech.
How does this relate to being honest? Let's look at Francesco again. Cosine College is his true second choice, but he is worried he will not get in, so he lies and ranks in first. Is this a valid strategy under the DA mechanism? Suppose Francesco is honest. If he does not get into Cosine College, he goes to Sine School. The mathematical result tells us that this is the best he can get in any stable matching. So there is not stable matching where he gets into Tangent Tech, nor one where he gets into Cosine College. So he is bound to go to Sine School anyway in this case. He is better off being honest and ranking Tangent Tech first, such that he does not miss out on his dream of going to Tangent, if a spot were to open up for him.
In conclusion, the beauty of the DA mechanism is that students can safely rank schools based on their true preferences without needing to strategize. This did not go unnoticed: the Boston School Mechanism was widely implemented but, in recent years, has often been replaced by the truthful DA mechanism in school choice scenarios. And so, by using DA, school choice is designed in such a way that honesty is the best policy!
The cover photo is an adaptation from an image on this webpage. The other illustration was made with the help of Microsoft Copilot.
Finding a dating schedule that matches pairs of potential lovers up into dating couples, is an example of an algorithmic problem. There is a clearly defined input, given by the lists of who is considered an acceptable dating partner to whom. It is also clear what we want as the output: a pairing of classmates into acceptable boy-girl pairs that has as many pairs (dates) as possible. How can you find the best dating schedule?
During our teenage years, everything changes. It’s no surprise that our brain does too. But how do we make sense of this transformation? Is there a way to quantify it? Networks might just be the answer.
We want our guts to be filled with a diverse range of mutually beneficial and competitive interactions, a perfect blend of friends, frenemies, and enemies to keep our guts active and body on its toes. Read how networks can help understand these interactions!
