Automated Redistricting Simulation Using Markov Chain Monte Carlo

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 optimizat...

Full description

Saved in:
Bibliographic Details
Published in:Journal of computational and graphical statistics 2020-10, Vol.29 (4), p.715-728
Main Authors: Fifield, Benjamin, Higgins, , Michael, Imai, Kosuke, Tarr, Alexander
Format: Article
Language:English
Subjects:
Algorithms
Automation
Computer simulation
Gerrymandering
Graph cuts
Markov analysis
Markov chains
Metropolis-Hastings algorithm
Optimization
Parallel tempering
Redistricting
Simulated tempering
Simulation
Source code
Swendsen-Wang algorithm
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1061-8600
1537-2715
DOI:10.1080/10618600.2020.1739532