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 in order 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 is available for implementing the proposed methodology.

Replication Archive

https://doi.org/10.7910/DVN/VCIW2I

Software

redist: redist: Simulation Methods for Legislative Redistricting — CRAN / GitHub

Related Papers

McCartan, Cory, Christopher Kenny, Tyler Simko, Emma Ebowe, Michael Zhao, and Kosuke Imai ``Redistricting Reforms Reduce Gerrymandering by Constraining Partisan Actors.'' American Political Science Review, Forthcoming.

Kenny, Christopher T., Brian Zhou, Tyler Simko, and Kosuke Imai (2026). ``Weakening the Voting Rights Act reduces minority representation and electoral competition.''

O'Sullivan, Philip, Kosuke Imai, and Cory McCartan (2026). ``Generalized Sequential Monte Carlo Sampling for Redistricting Simulation.''

Miyazaki, Sho, Kento Yamada, and Kosuke Imai (2025). ``Estimating the Partisan Bias of Japanese Legislative Redistricting Plans Using a Simulation Algorithm.''

Jasny, Ethan, Christopher T. Kenny, Cory McCartan, Tyler Simko, Melissa Wu, Michael Y. Zhao, Aneetej Arora, Emma Ebowe, Philip O'Sullivan, Taran Samarth, and Kosuke Imai (2025). ``Gerrymandering and geographic polarization have reduced electoral competition.''

McCartan, Cory and Kosuke Imai (2023). ``Sequential Monte Carlo for Sampling Balanced and Compact Redistricting Plans.'' Annals of Applied Statistics, Vol. 17, No. 4 (December), pp. 3300-3323.

Kenny, Christopher T., Cory McCartan, Tyler Simko, Shiro Kuriwaki, and Kosuke Imai (2023). ``Widespread Partisan Gerrymandering Mostly Cancels Nationally, but Reduces Electoral Competition.'' Proceedings of the National Academy of Sciences, Vol. 120, No. 25, e2217322120.

Kenny, Christopher T., Shiro Kuriwaki, Cory McCartan, Evan Rosenman, Tyler Simko, and Kosuke Imai (2023). ``Comment: The Essential Role of Policy Evaluation for the 2020 Census Disclosure Avoidance System.'' Harvard Data Science Review, Special Issue 2: Dierential Privacy for the 2020 U.S. Census (January).

McCartan, Cory, Christopher T. Kenny, Tyler Simko, George Garcia III, Kevin Wang, Melissa Wu, Shiro Kuriwaki, and Kosuke Imai (2022). ``Simulated redistricting plans for the analysis and evaluation of redistricting in the United States.'' Scientific Data, Vol. 9, No. 689, pp. 1-10.

Kenny, Christopher T., Shiro Kuriwaki, Cory McCartan, Evan T.R. Rosenman, Tyler Simko, and Kosuke Imai (2021). ``The Use of Differential Privacy for Census Data and its Impact on Redistricting: The Case of the 2020 U.S. Census.'' Science Advances, Vol. 7, No. 7 (October), pp. 1-17.

Fifield, Benjamin, Kosuke Imai, Jun Kawahara, and Christopher T. Kenny (2020). ``The Essential Role of Empirical Validation in Legislative Redistricting Simulation.'' Statistics and Public Policy, Vol. 7, No. 1, pp 52-68.