How Does Fairness Affect the Complexity of Gerrymandering?

Gerrymandering is a common way to externally manipulate districtbased elections where the electorate is (artificially) redistricted with an aim to favour a particular political party to win more districts in the election. Formally, given a set of 𝑚 possible locations of ballot boxes and a set of 𝑛 voters (with known preferences) is it possible to choose 𝑘 specific locations for the ballot boxes so that the desired candidate wins in at least 𝑙 of them? Lewenberg et al. [AAMAS '17] and Eiben et al. [AAAI '20] studied the classical and fine-grained complexity (respectively) of the gerrymandering problem. In recent years, the research direction of studying the algorithmic implications of introducing fairness in computational social choice has been quite active. Motivated by this, we define two natural fairness conditions for the gerrymandering problem and design a near-optimal algorithm. Our two new conditions introduce an element of fairness in the election process by ensuring that: • the number of voters at each ballot box is not unbounded, i.e., lies in the interval [lower, upper] for some given parameters lower, upper • the margin of victory at each ballot box is not unbounded, i.e., lies in the interval [margin low , margin up ] for some given parameters margin low , margin up For the real-life implementation of redistricting, i.e., when voters are located in R 2 , we obtain the following upper and lower bounds for this fair version of the gerrymandering problem: • There is an algorithm running in (𝑚+𝑛) 𝑂 (√ 𝑘) •|C| (upper+lower+ margin up +margin low) time where C is the set of candidates par