Locally Fair Partitioning
Abstract
We model the societal task of redistricting political districts as a partitioning problem: Given a set of n points in the plane, each belonging to one of two parties, and a parameter k, our goal is to compute a partition P of the plane into regions so that each region contains roughly s = n/k points. P should satisfy a notion of "local" fairness, which is related to the notion of core, a well-studied concept in cooperative game theory. A region is associated with the majority party in that region, and a point is unhappy in P if it belongs to the minority party. A group D of roughly s contiguous points is called a deviating group with respect to P if majority of points in D are unhappy in P. The partition P is locally fair if there is no deviating group with respect to P. This paper focuses on a restricted case when points lie in 1D. The problem is non-trivial even in this case. We consider both adversarial and "beyond worst-case" settings for this problem. For the former, we characterize the input parameters for which a locally fair partition always exists; we also show that a locally fair partition may not exist for certain parameters. We then consider input models where there are "runs" of red and blue points. For such clustered inputs, we show that a locally fair partition may not exist for certain values of s, but an approximate locally fair partition exists if we allow some regions to have smaller sizes. We finally present a polynomial-time algorithm for computing a locally fair partition if one exists.
Cite
Text
Agarwal et al. "Locally Fair Partitioning." AAAI Conference on Artificial Intelligence, 2022. doi:10.1609/AAAI.V36I5.20401Markdown
[Agarwal et al. "Locally Fair Partitioning." AAAI Conference on Artificial Intelligence, 2022.](https://mlanthology.org/aaai/2022/agarwal2022aaai-locally/) doi:10.1609/AAAI.V36I5.20401BibTeX
@inproceedings{agarwal2022aaai-locally,
title = {{Locally Fair Partitioning}},
author = {Agarwal, Pankaj K. and Ko, Shao-Heng and Munagala, Kamesh and Taylor, Erin},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2022},
pages = {4752-4759},
doi = {10.1609/AAAI.V36I5.20401},
url = {https://mlanthology.org/aaai/2022/agarwal2022aaai-locally/}
}