A k-medoids approach to exploring districting plans
Creators: name: Grove, Jared T.
Publisher: name: University of Iowa
Year: 2022
Subjects: subject: gerrymandering
subject: k-medoids
subject: redistricting
subject: public abstract
subject: Political Science
subject: FOS: Political science

description: Every ten years the United States goes through a reapportionment process, where states may gain or lose seats in the House of Representatives based on population changes. States with more than one representative may need to redistrict or redraw the lines for their congressional districts based on how the populations have shifted within the state or because the number of representatives for that state changed. When a state redistricts, smaller political regions (such as counties or voter tabulation districts) are assigned to k districts – where k is the number of congressional seats – creating a new districting plan. These districting plans must follow rules to related to contiguity (no part of the district can be separated from the whole), compactness (districts must be as square or circular as possible), and population equality (populations ~1\% of each other). These rules help ensure that each person is fairly represented. However, this process can be corrupted. Gerrymandering is the act of drawing a districting plan in order to retain political power, take power away from opponents, or to further various other political goals. To help combat gerrymandering I propose an algorithm for computer generation of districting plans, taking the process out of the hands of politicians. Representing a state as a graph, with the geographic units (counties, census blocks, voter tabulation districts) as vertices and shared geographical borders as edges, allows the redistricting process to be approached using graph algorithms. The algorithm presented follows a k-medoids process and builds districting plans by randomly selecting k vertices to be medoids, or district seeds. The districts are expanded using a simultaneous Breadth First Search (BFS) procedure until all vertices have been assigned to districts. Following the creation of this initial districting plan, new medoids are selected as the middle vertices of the current districts. This process of assignment of all vertices to districts using BFS and reassignment of medoids is repeated iteratively until convergence criteria are reached. Afterwards I use Flip, Swap, Combination, Multi-Object Move, and Merge and Cut neighborhood functions as local search methods to explore the space of districting plans and find plans with roughly equal district populations. To help with the large number of political regions many states have I also introduce a coarsening process that combines adjacent regions into a single piece. I use this method to generate districting plans for both Iowa and Florida. My method generates an average of 10 districting plans for Iowa with a deviation of &lt;1% and a mean compactness of 0.76 in less than 3 seconds per plan. For Florida, my method can generate districting plans with deviation as low as 4.3% and a mean compactness of 0.72 while only splitting 7 out of 67 counties across more than one district, but generally takes more than 8 minutes to run. If I don't require that any county boundaries remain in tact, the my method is able to achieve a deviation of &lt;1% with a mean compactness of 0.67, but this comes at a cost of more computational time. Comparisons to another recent computational method as well as the official 2021 districting plans for Iowa and Florida show that my method more efficiently generates plans that more closely fit legal requirements than other available methods. Future work for further improvement is also discussed.