Redistricting Explained: Fair Representation Through Algorithms

Every ten years, the United States goes through a process called reapportionment. This is when states may gain or lose seats in the House of Representatives based on changes in population. If a state has more than one representative, it needs to redraw the lines for its congressional districts. This is known as Redistricting.

When redistricting, lines must be drawn to divide the state into a certain number of districts, matching the number of congressional seats available. To do this, the state can be represented as a graph, where the areas within the state (like counties or voting precincts) are turned into points, called vertices. The connections between these points represent shared borders, called edges. Each area that needs to be assigned to a district is called a tabulation block (TB), which can represent counties, voting precincts, or a combination of them.

While drawing these lines, there are a few important rules to follow. First, the districts must be connected, meaning there should be no gaps between them. Second, the shape of the districts should be as compact as possible. Lastly, the populations in each district should be approximately equal. This ensures fair representation of people in Congress.

To check if a districting plan meets these rules, there are several measures to determine how compact a district is. A common method used is called the Convex Hull measure. It compares the area of a district to the area of the smallest shape that can contain it. A good district should have a population close to the total population of the state divided by the number of districts.

While redistricting is essential for proper representation, it can also be misused to favor one political group over another. This manipulation is known as Gerrymandering. In some cases, politicians can choose their voters instead of letting voters choose their representatives.

Gerrymandered districts often have strange shapes, like long and winding districts. These shapes can be identified using compactness measures. However, not all gerrymanders are obvious. To address this issue, various algorithms have been proposed to create districting plans that minimize political bias. By generating a lot of districting plans without bias and analyzing the expected election results, it's possible to spot unfairly drawn districts.

#Approaches to Districting

Most computer-based methods for redistricting fall into two categories: sampling and optimization. Some problems related to redistricting have been shown to be quite complex, meaning they are not easy to solve quickly (these are referred to as NP-Complete problems).

Sampling methods focus on quickly generating many district plans. These methods often start with randomly chosen points and build districts from there. However, this can sometimes lead to situations where some TBs cannot be assigned to any district, resulting in enclaves. To avoid this, some variations of the basic sampling method grow districts simultaneously, which can help maintain consistent shapes.

The second type of method is based on optimization. This approach tries to find the best districting plan according to some criteria. Two common optimization categories are clustering and heuristics. Clustering algorithms assign TBs to centers while minimizing distances. Care must be taken to ensure that these methods do not break up any existing TBs, which is necessary for legal compliance.

Heuristic algorithms often use mathematical models to create an optimal districting plan. They can use various methods to find solutions, such as Local Searches or genetic algorithms. While these methods can yield good results, it's crucial to decide what to optimize for, whether it's minimizing edge cuts or balancing populations.

Another approach is to use random walks to explore the set of districting plans. These methods rely on starting points that can help navigate the problem space. Combining random walks with sampling or optimization can enhance the exploration process.

#Our Methodology

We use a special algorithm called K-medoids to tackle the problem of drawing districting plans. This method starts by representing the state as a graph and follows a specific procedure to build districts. Unlike traditional methods, which build districts in a set order, our approach allows for a flexible construction pattern.

The K-medoids method involves starting with a set number of TBs as initial district centers. Then, we alternate between assigning TBs to the nearest centers and recalculating the centers for each district. This is similar to K-means clustering but uses graph distances instead of physical distances.

After obtaining an initial districting plan, we use local search strategies to fine-tune the results and reduce population disparities between districts. These strategies involve looking at small changes that can be made to the plan, such as switching the assignment of TBs between districts.

We also use a process called coarsening to work with fewer TBs, making calculations faster. Once we have a rough plan, we gradually return to the original number of TBs to refine the solution further.

The coarsening process starts with combining neighboring TBs until we have fewer vertices. To restore the original graph, we follow an uncoarsening method, which splits combined vertices back into their original forms while keeping their populations and district assignments intact.

#Local Search Techniques

To improve our districting plan further, we use local search methods. These methods explore nearby districting plans to find variations that have better population balance. We focus on three types of neighborhood functions: Flip, Swap, and Combination Search (CMB).

The Flip function changes the assignment of one TB to a different district. The Swap function changes two TBs between districts. The CMB method looks at both the Flip and Swap functions and picks the best outcome. These functions help generate new districting plans based on small changes.

As we explore neighboring plans, we want to avoid getting stuck in cycles of repeating changes. To help with this, we maintain a tabu list that prevents us from making the same move repeatedly within a set number of iterations.

#Coarsening and Uncoarsening Strategy

As we mentioned earlier, states can have many TBs, leading to a very complex graph. This can slow down the algorithm significantly. By coarsening the graph, we can simplify our calculations.

During the coarsening process, we combine neighboring TBs until we achieve a manageable number of vertices. Each combined vertex keeps the connections of its parents, and the population is summed. This continues until we reach the desired number of vertices.

To restore the original graph, we reverse the coarsening process by splitting the combined vertices while maintaining their district assignments. We repeat this until we return to the original graph structure.

#Testing and Results Analysis

To evaluate our method, we have chosen to apply it to Iowa and Florida. Iowa serves as a straightforward example due to its smaller number of TBs. In contrast, Florida presents more complexity with many TBs.

We start by testing different parameter setups to find which ones yield the best results. We go through various neighborhood functions and local search iteration numbers. After identifying effective parameters, we run our algorithm multiple times on both states to gather average results.

For Iowa, our algorithm quickly discovers plans that meet or exceed the legal population deviation requirements. Including local search strategies can lower the mean deviation even more, approaching the maximum allowed threshold.

In Florida, our method is less consistent due to the complicated nature of the state. While local search helps lower mean deviation values, our plans still lag behind those generated with more detailed data.

By incorporating the discovery of multiple districting plans during the process, we can generate additional good plans beyond the first attempt. This allows us to find more districting options with acceptable deviations.

#Comparison to Other Methods

In addition to our algorithm, we tested a similar approach from previous research to see how it stacks up. Since our method allows coarsening, we can apply more local searches. To ensure a fair comparison, we adjusted the iterations for the alternative method.

Results show that our method consistently produces lower deviation levels than the competing approach. Even though the alternative method might create slightly more compact districts, our method better balances time and deviation.

The official districting plans for Iowa and Florida from the latest census serve as benchmarks. While our plans achieve acceptable deviations, they do not always meet the compactness of official plans. The differences arise from the varying levels of detail used in the tabulation blocks.

#Conclusion and Future Directions

Our algorithm effectively produces valid districting plans, especially in simpler scenarios like Iowa. For more complex states like Florida, additional research can address challenges in achieving low deviation results.

Moving forward, there are many potential avenues to explore. We aim to expand our method to include other states and updated census data. Enhancements could involve improved local search strategies, focusing on maintaining political and demographic integrity while drawing districts.

In future work, special attention may also be given to creating districts that reflect the needs of minority populations as required in certain states. This could involve merging TBs representing communities to create fairer, majority-minority districts.

Overall, our method showcases a blending of established techniques with new strategies to effectively approach the complex problem of districting, providing a fresh perspective in the ongoing conversation about fair representation in government.