Envy-Free School Redistricting Between Two Groups
This work addresses fair school redistricting for two groups, providing a practical solution with theoretical guarantees, though it is incremental as it builds on prior models for multiple groups.
The paper tackles the problem of achieving envy-free school redistricting for two demographic groups by introducing a relaxation called 1-relaxed envy-freeness, which limits capacity violations at each school to at most one, and proves that such an allocation always exists and can be found in polynomial time.
We study an application of fair division theory to school redistricting. Procaccia, Robinson, and Tucker-Foltz (SODA 2024) recently proposed a mathematical model to generate redistricting plans that provide theoretically guaranteed fairness among demographic groups of students. They showed that an almost proportional allocation can be found by adding $O(g \log g)$ extra seats in total, where $g$ is the number of groups. In contrast, for three or more groups, adding $o(n)$ extra seats is not sufficient to obtain an almost envy-free allocation in general, where $n$ is the total number of students. In this paper, we focus on the case of two groups. We introduce a relevant relaxation of envy-freeness, termed 1-relaxed envy-freeness, which limits the capacity violation not in total but at each school to at most one. We show that there always exists a 1-relaxed envy-free allocation, which can be found in polynomial time.