Envy-Free School Redistricting Between Two Groups
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915876645634048 |
|---|---|
| author | Shibatani, Daisuke Yamaguchi, Yutaro |
| author_facet | Shibatani, Daisuke Yamaguchi, Yutaro |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_19701 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Envy-Free School Redistricting Between Two Groups Shibatani, Daisuke Yamaguchi, Yutaro Computer Science and Game Theory Data Structures and Algorithms 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. |
| title | Envy-Free School Redistricting Between Two Groups |
| topic | Computer Science and Game Theory Data Structures and Algorithms |
| url | https://arxiv.org/abs/2603.19701 |