2026-07-26T04:38:47Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20090 2024-06-10T05:20:53Z ddc:004 open_access

Drawing Competitive Districts in Redistricting Chuang, Gabriel Hanguir, Oussama Stein, Clifford Redistricting Computational Complexity Algorithms 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Gabriel Chuang and Oussama Hanguir and Clifford Stein 2024 Is Part Of LIPIcs, Volume 295, 5th Symposium on Foundations of Responsible Computing (FORC 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FORC.2024.7 urn:nbn:de:0030-drops-200902 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2024.7 eng https://creativecommons.org/licenses/by/4.0/legalcode