Abstract
Gerrymandering is a common way to externally manipulate district-based 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 m possible locations of ballot boxes and a set of n voters (with known preferences) is it possible to choose k specific locations for the ballot boxes so that the desired candidate wins in at least l 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 [marginlow, marginup for some given parameters marginlow, marginup
For the real-life implementation of redistricting, i.e., when voters are located in ℝ2, we obtain the following upper and lower bounds for this fair version of the gerrymandering problem:
•There is an algorithm running in (m + n)O(√k)⋅| C| (upper+ lower+ marginup + marginlow) time where C is the set of candidates participating in the election.
•Under the Exponential Time Hypothesis (ETH), we obtain an almost tight lower bound by ruling out algorithms running in &402;(k,n, upper, lower)⋅ mo(√k) time where ƒ is any computable function. The lower bound holds even when marginlow = 1 = marginup, k = l and there are only 2 candidates.
Original language | English |
---|---|
Title of host publication | AAMAS '23 |
Subtitle of host publication | Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems |
Publisher | Association for Computing Machinery (ACM) |
Pages | 2869-2871 |
Number of pages | 3 |
ISBN (Electronic) | 9781450394321 |
DOIs | |
Publication status | Published - 30 May 2023 |
Event | 22nd International Conference on Autonomous Agents and Multiagent Systems - London, United Kingdom Duration: 29 May 2023 → 2 Jun 2023 |
Publication series
Name | Proceedings of International Conference on Autonomous Agents and Multiagent Systems |
---|---|
ISSN (Electronic) | 2523-5699 |
Conference
Conference | 22nd International Conference on Autonomous Agents and Multiagent Systems |
---|---|
Abbreviated title | AAMAS 2023 |
Country/Territory | United Kingdom |
City | London |
Period | 29/05/23 → 2/06/23 |
Bibliographical note
Acknowledgments:Sandip Banerjee acknowledges the support by Polish National Science Centre (NCN) Grant 2020/39/B/ST6/01641. Abhiruk Lahiri’s research is funded in part by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – project number 416767905.