Automated Redistricting Simulation Using Markov Chain Monte Carlo

Abstract

Legislative redistricting is a critical element of representative democracy. A number of political scientists have used simulation methods to sample redistricting plans under various constraints to assess their impact on partisanship and other aspects of representation. However, while many optimization algorithms have been proposed, surprisingly few simulation methods exist in the published scholarship. Furthermore, the standard algorithm has no theoretical justification, scales poorly, and is unable to incorporate fundamental constraints required by redistricting processes in the real world. To fill this gap, we formulate redistricting as a graph-cut problem and for the first time in the literature propose a new automated redistricting simulator based on Markov chain Monte Carlo. The proposed algorithm can incorporate contiguity and equal population constraints at the same time. We apply simulated and parallel tempering to improve the mixing of the resulting Markov chain. Through a small-scale validation study, we show that the proposed algorithm can approximate a target distribution more accurately than the standard algorithm. We also apply the proposed methodology to data from Pennsylvania to demonstrate the applicability of our algorithm to real-world redistricting problems. The open-source software package is available so that researchers and practitioners can implement the proposed methodology. Supplementary materials for this article are available online.

Keywords:

• Gerrymandering
• Graph cuts
• Metropolis–Hastings algorithm
• Parallel tempering
• Simulated tempering
• Swendsen–Wang algorithm

Supplementary Materials

In the supplementary materials, we provide proofs of the theorems presented in the article, as well as additional empirical examples.

Acknowledgments

We thank Jowei Chen, Jacob Montgomery, and seminar participants at Chicago Booth, Dartmouth, Duke, Microsoft Research, and SAMSI for useful comments and suggestions. We thank James Lo, Jonathan Olmsted, and Radhika Saksena for their advice on computation. The replication archive for this article is available in Fifield, Higgins, et al. (2019). The open-source R package redist for implementing the proposed methodology is available in Fifield, Tarr, and Imai (2015). Replication materials can be found in Dataverse at https://doi.org/10.7910/DVN/VCIW2I.

ORCID

Benjamin Fifield http://orcid.org/0000-0002-2247-0201

Michael Higgins http://orcid.org/0000-0003-4969-2733

Kosuke Imai http://orcid.org/0000-0002-2748-1022