Assigning students to schools under capacity and priority rules

Every year a school district has to do something that looks like a matching problem and behaves like a negotiation. Students submit a ranked list of schools, every school has a hard capacity, and a handful of rules sit on top that are not negotiable at all: a reserved share of places for priority students, and preference for children who have relatives already at a particular school. Get the mechanism wrong and the district is the one paying for it.

The data. The real instance came from a single district and was provided by a collaborator, with 8,500 students across 86 schools. Each student has a ranked list of preferred schools, a priority flag, and a list of schools where they have relatives. Each school has a total capacity and the percentage of it reserved for priority students. Alongside it I built synthetic scenarios of 75 schools and 6,000 to 8,000 students across five capacity settings, so the mechanisms could be compared on size rather than on one particular district’s politics.

Two mechanisms, side by side. The point of the project was to compare mechanisms rather than to build one clever algorithm, so I implemented two in C++.

The first is a randomized constructive assignment. Each school holds a ticket list, and when a place opens the algorithm reaches into that list. Two adjustments decide who is at the front: students with relatives at that school are moved up, and when a school is working through its reserved capacity the priority students are moved up instead. The second is serial dictatorship, the mechanism design classic, where students are served in a random order and each simply takes the best school that still has room.

I was responsible for the implementation of these algorithms.