Automated Redistricting Simulation Using Markov Chain Monte Carlo
Automated Redistricting Simulation Using Markov Chain Monte Carlo
复制标题
DOI：
10.1080/10618600.2020.1739532
复制
发表时间：
2020-05-07
影响因子：
2.4
通讯作者：
Tarr, Alexander
中科院分区：
文献类型：
--
作者：
Fifield, Benjamin;Higgins, Michael;Tarr, Alexander
立法重新划分是代表民主的关键要素。许多政治科学家使用模拟方法在各种限制下对重新分配计划进行了对其对党派和代表的其他方面的影响进行采样。但是，尽管已经提出了许多优化算法，但出乎意料的是，已发表的奖学金中很少有模拟方法。此外，标准算法没有理论上的理由，缩放较差，并且无法纳入对现实世界中重新分配过程所需的基本约束。为了填补这一空白，我们将重新划分为剪图问题，并且在文献中首次提出了基于马尔可夫链蒙特卡洛的新自动重新分配模拟器。所提出的算法可以同时融合邻近性和相等的种群约束。我们应用模拟和并行的回火来改善所得马尔可夫链的混合。通过一项小规模验证研究，我们表明所提出的算法比标准算法更准确地近似目标分布。我们还将提出的方法应用于宾夕法尼亚州的数据，以证明我们的算法对现实世界重新分配问题的适用性。可以使用开源软件包，以便研究人员和从业人员可以实施所提出的方法。本文可在线获得。
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. for this article are available online.