How Does Fairness Affect the Complexity of Gerrymandering?

Sandip Banerjee, Rajesh Chitnis, Abhiruk Lahiri

Research output: Chapter in Book/Report/Conference proceedingConference contribution

70 Downloads (Pure)

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 languageEnglish
Title of host publicationAAMAS '23
Subtitle of host publicationProceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems
PublisherAssociation for Computing Machinery (ACM)
Pages2869-2871
Number of pages3
ISBN (Electronic)9781450394321
DOIs
Publication statusPublished - 30 May 2023
Event22nd International Conference on Autonomous Agents and Multiagent Systems - London, United Kingdom
Duration: 29 May 20232 Jun 2023

Publication series

NameProceedings of International Conference on Autonomous Agents and Multiagent Systems
ISSN (Electronic)2523-5699

Conference

Conference22nd International Conference on Autonomous Agents and Multiagent Systems
Abbreviated titleAAMAS 2023
Country/TerritoryUnited Kingdom
CityLondon
Period29/05/232/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.

Fingerprint

Dive into the research topics of 'How Does Fairness Affect the Complexity of Gerrymandering?'. Together they form a unique fingerprint.

Cite this