Drawing Competitive Districts in Redistricting
<|reference_start|>Drawing Competitive Districts in Redistricting: In the process of redistricting, one important metric is the number of competitive districts, that is, districts where both parties have a reasonable chance of winning a majority of votes. Competitive districts are important for achieving proportionality, responsiveness, and other desirable qualities; some states even directly list competitiveness in their legally-codified districting requirements. In this work, we discuss the problem of drawing plans with at least a fixed number of competitive districts. In addition to the standard, ``vote-band'' measure of competitivenesss (i.e., how close was the last election?), we propose a measure that explicitly considers ``swing voters'' - the segment of the population that may choose to vote either way, or not vote at all, in a given election. We present two main, contrasting results. First, from a computational complexity perspective, we show that the task of drawing plans with competitive districts is NP-hard, even on very natural instances where the districting task itself is easy (e.g., small rectangular grids of population-balanced cells). Second, however, we show that a simple hill-climbing procedure can in practice find districtings on real states in which all the districts are competitive. We present the results of the latter on the precinct-level graphs of the U.S. states of North Carolina and Arizona, and discuss trade-offs between competitiveness and other desirable qualities.<|reference_end|>
@article{chuang2024drawing,
    title={Drawing Competitive Districts in Redistricting},
    author={Gabriel Chuang, Oussama Hanguir, and Clifford Stein},
    journal={arXiv preprint arXiv:2404.10964},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.10964},
    primaryClass={cs.DS cs.CY}
}