Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2210.01401 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915619339763712 |
|---|---|
| author | Cannon, Sarah Duchin, Moon Randall, Dana Rule, Parker |
| author_facet | Cannon, Sarah Duchin, Moon Randall, Dana Rule, Parker |
| contents | Deciding whether a political districting plan was distorted by a hidden agenda, or whether it dilutes the voting power of some group, requires a neutral baseline for comparison. Remarkably, all nine U.S. Supreme Court justices have now signed on to decisions that find that computational methods can provide key evidence. Today, the leading approaches for benchmarking districting plans are based on the use of spanning trees for sampling graph partitions. We present a new *reversible recombination* algorithm and rigorously prove its fundamental properties. Furthermore, we argue for a canonical sampling distribution called the *spanning tree distribution* that is well adapted to redistricting and provides a principled foundation for comparing and validating methods. Together with a highly efficient (and open-source) implementation that can generate and handle large datasets, this work provides the most powerful null model to date for the gerrymandering problem, meeting an urgent democratic challenge with sound scientific methodology. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2210_01401 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Spanning Trees and Redistricting: New Methods for Sampling and Validation Cannon, Sarah Duchin, Moon Randall, Dana Rule, Parker Physics and Society Computers and Society 60J10, 62P25, 05C85 Deciding whether a political districting plan was distorted by a hidden agenda, or whether it dilutes the voting power of some group, requires a neutral baseline for comparison. Remarkably, all nine U.S. Supreme Court justices have now signed on to decisions that find that computational methods can provide key evidence. Today, the leading approaches for benchmarking districting plans are based on the use of spanning trees for sampling graph partitions. We present a new *reversible recombination* algorithm and rigorously prove its fundamental properties. Furthermore, we argue for a canonical sampling distribution called the *spanning tree distribution* that is well adapted to redistricting and provides a principled foundation for comparing and validating methods. Together with a highly efficient (and open-source) implementation that can generate and handle large datasets, this work provides the most powerful null model to date for the gerrymandering problem, meeting an urgent democratic challenge with sound scientific methodology. |
| title | Spanning Trees and Redistricting: New Methods for Sampling and Validation |
| topic | Physics and Society Computers and Society 60J10, 62P25, 05C85 |
| url | https://arxiv.org/abs/2210.01401 |