A k-medoids approach to exploring districting plans

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. This algorithm follows a k-medoids process and builds districting plans selecting an initial seed political unit for each district. The districts grow by expanding out from their seed, adding neighboring political units until the are no more units to add. Following the creation of this initial districting plan, the middle (or medoid) of each district is found. Then the process of growing the districts is repeated from these middle points. This process of assignment of all political regions to districts and reassignment of medoids is repeated iteratively until convergence criteria are reached. Afterwards I use some heuristic search techniques to adjust the districting plans until all districts have roughly equal 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 < 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 ~ 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.