Envy-Free School Redistricting Between Two Groups

Computer scientists Daisuke Shibatani and Yutaro Yamaguchi have introduced a novel algorithmic solution to the politically charged problem of school redistricting. Their research, published in a March 2026 arXiv paper, focuses specifically on creating fair district boundaries between two demographic groups. The core innovation is a relaxation of the strict envy-freeness condition, termed '1-relaxed envy-freeness.' This model allows a mathematically guaranteed fair allocation by permitting each school to accept at most one student beyond its official capacity, a minimal and practical concession.

This work builds upon but significantly advances prior research by Procaccia, Robinson, and Tucker-Foltz from SODA 2024. Their earlier model could find an almost proportional allocation but required adding a total of O(g log g) extra seats across the entire district, where 'g' is the number of groups. More critically, they proved that for three or more groups, achieving fairness without adding a significant number (o(n)) of extra seats is generally impossible. Shibatani and Yamaguchi's breakthrough for the two-group case sidesteps this complexity, proving a solution always exists and, most importantly, can be computed efficiently in polynomial time.

The practical implication is a tractable, algorithmically sound framework for policymakers. Instead of the combinatorial nightmare of perfectly balanced districts, their method provides a clear, implementable standard: no school is overloaded by more than a single student to achieve envy-freeness between two communities. This represents a major step in applying computational fair division theory to real-world civic problems, offering a data-driven alternative to often contentious and gerrymandered redistricting processes.