Graph theory models and algorithms for political districting: an approach to inform public policy

Operations research;Political districting;Plane graph theory;Local search

King, Douglas

关键词: Operations research;    Political districting;    Plane graph theory;    Local search;   

Others  :  https://www.ideals.illinois.edu/bitstream/handle/2142/30931/King_Douglas.pdf?sequence=1&isAllowed=y

美国|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

Political districting is an intractable problem with significant ramifications for political representation. Districts are often required to satisfy some legal constraints, but these are typically not very restrictive, allowing decision-makers to influence the composition of these districts without violating relevant laws. For example, while districts must often comprise a single contiguous area, a vast collection of acceptable solutions (i.e., sets of districts) remains. Choosing the best set of districts from this collection can be treated as a (planar) graph partitioning problem. Such problems are typically intractable, and hence, heuristics such as local search have been adopted to generate good (though suboptimal) solutions in a reasonable time-frame. When districts must be contiguous, effectively applying local search requires an efficient computational method for evaluating contiguity constraints in each iteration; common methods for assessing contiguity can require significant computation as the problem size grows. Practical districting problems, such as those encountered when designing United States Congressional Districts, may need to allocate a very large number of census blocks among a relatively small number of districts, leading to significant computation when assessing contiguity.This dissertation introduces the geo-graph, a new graph model that ameliorates the computational burdens associated with enforcing contiguity constraints in planar graph partitioning when each vertex corresponds to a particular region of the plane called a unit. Through planar graph duality, the geo-graph provides a scale-invariant method for enforcing contiguity constraints in local search. Furthermore, geo-graphs allow district holes (which are typically considered undesirable) to be rigorously and efficiently integrated into the partitioning process. These benefits are realized by exploiting unused facets of the underlying structure of districting problems by both (1) integrating knowledge about the duality between unit boundaries and unit adjacencies, and (2) integrating zone-level knowledge into unit-level decisions through a rigorous link that exists between holes and contiguity. The geo-graph provides fast algorithms that assess zone holes and zone contiguity during local search; the time complexities of these algorithms depend only on the number of zones being created and the number of units whose boundaries share at least one point with the boundary of the unit that local search seeks to transfer in the current iteration. These factors do not necessarily increase with the number of units under consideration, and hence, these algorithms are scale invariant from a theoretical perspective. Moreover, this dissertation finds that these factors scale well in several practical problem instances, suggesting that benefits of the geo-graph can be significant in real-world districting problems.