  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.
