Fair redistricting is hard

Creators: Kueng, Richard; Mixon, Dustin G.; Villar, Soledad

Abstract

Gerrymandering is a long-standing issue within the U.S. political system, and it has received scrutiny recently by the U.S. Supreme Court. In this note, we prove that deciding whether there exists a fair redistricting among legal maps is -hard. To make this precise, we use simplified notions of "legal" and "fair" that account for desirable traits such as geographic compactness of districts and sufficient representation of voters. The proof of our result is inspired by the work of Mahanjan, Minbhorkar and Varadarajan that proves that planar k-means is -hard.

Additional Information

© 2019 Elsevier B.V. Received 27 August 2018, Revised 6 February 2019, Accepted 15 April 2019, Available online 28 May 2019. The main ideas in this paper were conceived while the authors were attending an Oberwolfach workshop on "Applied Harmonic Analysis and Data Processing" in March 2018. The authors thank Boris Alexeev and Ruth Greenwood for reading a preliminary version of this paper and providing helpful comments. RK was supported in part by Joel A. Tropp under ONR Award No. N00014-17-12146 and also acknowledges funding provided by the Institute of Quantum Information and Matter, an NSF Physics Frontiers Center (NSF Grant PHY-1733907). DGM was partially supported by AFOSR F4FGA06060J007 and AFOSR Young Investigator Research Program award F4FGA06088J001. SV was partially supported by the Simons Algorithms and Geometry (A&G) Think Tank. The views expressed in this article are those of the authors and do not reflect the official policy or position of the United States Air Force, Department of Defense, or the U.S. Government.

Attached Files

Submitted - 1808.08905.pdf

Files

1808.08905.pdf

Files (582.2 kB)

Name	Size	Download all
1808.08905.pdf md5:cff1e13c0335015180e4ab94ecae0efc	582.2 kB	Preview Download

Additional details

	All versions	This version
Views	0	0
Downloads	0	0
Data volume	0 Bytes	0 Bytes