On the Complexity of Sampling Redistricting Plans

2022/06/10 by Moses Charikar, Charikar, Moses, Paul Liu +5 · 4 citations
Mathematics · Economics, Econometrics and Finance · #Census and Population Estimation #Markov Chains and Monte Carlo Methods #Game Theory and Voting Systems

paper · pdf · doi:10.48550/arxiv.2206.04883

Abstract

A crucial task in the political redistricting problem is to sample redistricting plans i.e. a partitioning of the graph of census blocks into districts. We show that Recombination [DeFord-Duchin-Solomon'21]-a popular Markov chain to sample redistricting plans-is exponentially slow mixing on simple subgraph of ℤ₂. We show an alternative way to sample balance, compact and contiguous redistricting plans using a "relaxed" version of ReCom and rejection sampling.

Cited by

• The Marked Edge Walk: A Novel MCMC Algorithm for Sampling of Graph Partitions
• A Cycle Walk for Sampling Measures on Spanning Forests for Redistricting
• Sampling tree-weighted partitions without sampling trees
• Balanced spanning trees of the 2-by-N grid

Related

• Recombination: A family of Markov chains for redistricting
• Compact Redistricting Plans Have Many Spanning Trees
• A Uniformly Random Solution to Algorithmic Redistricting
• Empirical Sampling of Connected Graph Partitions for Redistricting
• Multiscale Parallel Tempering for Fast Sampling on Redistricting Plans