School choice on the North Pole: there must be a better way!
This is a tale of three children: Poul, Pat, and Noel. They live on the North Pole and are looking forward to starting folkeskole.
The North Pole has three schools: Polar School, Northern School, and Hiver School. Each of these schools has exactly one open space for a new child next year.
Poul and Pat live in Polar district. Noel lives in Northern district. None of the children live in Hiver district.
The rules of the North Pole are clear. You get sent to the school of the district where you live, even if officially there are not enough open spaces. As a result, Poul and Pat will be sent to Polar School, and Noel will be sent to Northern School.
Poul and Pat are happy because they will end up at their favorite school, but Noel will not. All children like Polar School best, Northern School second best, and Hiver School least.
In fact, Noel envies Poul and Pat, and this envy seems justified. Noel actually lives closer to Polar School than both Poul or Pat, but just on the wrong side of the school district border. It doesn’t seem fair!
North Pole policy makers are also unhappy because Polar School is overcrowded, with two new children but only one official space. Hiver School has a space but no new child to fill it. It doesn’t seem efficient!
Policy makers therefore decide to get rid of the North Pole’s school districts and match children to schools using the deferred acceptance algorithm, with school priorities based only on the distance between a child’s home and the school in question.
Deferred acceptance works as follows (feel free to skip if you are already familiar with it!):
Each child sends a rank-ordered list with a first-choice school, a second-choice school, and a third-choice school. Then:
Round 1. Each child’s application is sent to the school they ranked first. If each school gets exactly one application, then all are accepted and the procedure ends. If not, then each school keeps the application of the child who lives closest, rejects all other children, and we move on to Round 2.
Round 2. The application of any child rejected in Round 1 is sent to the school they ranked second. If each school has exactly one application (including any application they kept in Round 1), then all are accepted and the procedure ends. If not, then each school keeps the application of the child who lives closest, rejects all other children, and we move on to Round 3.
Round 3. The application of any child rejected in Round 2 is sent to the school they ranked third. All schools must then have exactly one application, so all are accepted and the procedure ends.
Notice that a child whose application was kept in Round 1 might still be rejected in Round 2, if the school receives another application from a child who lives closer.
Suppose that Poul lives 20 km from Polar School, 70 km from Northern School, and 130 km from Hiver School. Pat lives 40 km from Polar School, 60 km from Northern School, and 90 km from Hiver School. Noel lives 10 km from Polar School, 50 km from Northern School, and 110 km from Hiver School.
Now come the questions:
a) Which child will end up at which school?
b) Will any child’s envy be justified, in the sense of being rejected by a school that accepts someone else who lives further away?
c) Do any schools end up being overcrowded?
Send your answers to firstname.lastname@example.org by Saturday December 11 at 23.59 for your chance to win a prize: a copy of the novel “The Wind-Up Bird Chronicle” by Haruki Murakami.
Happy Christmas from Nick Vikander
PS. You can also think about how these answers might change if policy makers implemented a distance guarantee, ensuring that no child could be sent to a school further than 100 km from their home (unless they ranked it higher than a closer school). Or a sibling guarantee, ensuring that any child with an older sibling attending a particular school is also offered a place at that school. But these are questions for another day!