A group of us at UCI have been trying to understand algorithmic problems in political redistricting (with the goal of finding methods that are fair, difficult to gerrymander, and efficient to calculate). Although the real goal is political fairness (a difficult concept to define let alone optimize for), there are other important criteria in redistricting: districts should be close to equal in population, and should be geographically compact.

In a post last year I linked to some interesting work from Yuval Peres and others at Microsoft Research on Voronoi diagrams defined from stable marriages rather than closest distances. This method takes a region of the plane (the unit square, say) and a collection of center points within the region, and divides the region into equal-area subregions that are (mostly) close to their centers; an example is shown below, with colors distinguishing the different subregions from each other. We thought this might make a good abstraction to the redistricting problem: if the centers represent voting places, and units of area represent numbers of voters (so the voters are uniformly spread around the square) then it will give us subregions for each voting place that are of equal population and near their voting place. More specifically, by definition, there should be no pair \((v,p)\) where \(v\) is a voter whose assigned polling place is \(p\) and \(p\) is a polling place whose assigned voters include people farther than \(v.\)

900 x 900 stable grid matching

Our new preprint, “Algorithms for Stable Matching and Clustering in a Grid” (arXiv:1704.02303, to appear at IWCIA) starts by looking at efficient algorithms for this problem. It turns out that the fact that the preferences are symmetric (both voters and voting places prioritize each other by the same distances) really helps. One could use a dynamic nearest-neighbor data structure to repeatedly find and match voters to places until each voter has a place and each place has enough voters, but one can do even better than that by applying the nearest-neighbor chain algorithm to repeatedly find mutual nearest neighbors of unplaced voters and not-yet-full voting places, avoiding the overhead of nearest neighbors. Based on this idea, we show that constructing images such as the one above by matching an \(n\times n\) grid of pixels to some smaller number of centers can be performed in time \(O(n^2\log^5 n).\) This is the first application I’m aware of outside of hierarchical clustering for nearest-neighbor chains. But the underlying nearest neighbor data structures used in these algorithms are still too complicated to be practical, so instead we implemented and experimented with simpler heuristics that nevertheless obtain significant speedups over naive stable marriage algorithms.

Choosing the voting places (the centers of each region) uniformly at random tends not to work too well. Random fluctuation causes some parts of the grid to have too many centers and others too few, and when that happens the centers in the dense regions have to reach out a long distance to find voters in the sparse regions who can be assigned to them. We end up getting disconnected regions with very high radius. (In the above image, the boundaries are straight lines and circular arcs centered on the voting places, so you can find these bad regions by looking for high-radius curved boundaries.) We thought we would be able to fix these problems by using a variant of Lloyd’s algorithm adapted for this kind of Voronoi diagram: alternate between steps that compute the stable matching and that move the centers to a more central point within their region. But although it did lead to better-behaved subdivisions, it didn’t entirely eliminate the problems.

Of course, actual voters must deal with road distance not straight-line distance. For instance, Lucia, California and King City, California had very different road distances and straight line distances, even before the recent bridge outage on Highway 1 making it essentially impossible to get from one to the other. And populations are not evenly distributed by area. So, beyond the question of finding an equal-area stable subdivision, turning this into a usable redistricting algorithm will require additional research.