Fighting Gerrymandering with Algorithmic Fairness

Michael Goodrich, University of California, Irvine

In this talk, we review the mathematics and algorithmics of gerrymandering and we introduce an approach for solving the political districting problem based on an algorithmic definition of fairness. In particular, we describe an approach to defining geographic districts in road networks and geometric regions using stable matching. In this approach, each geographic district is defined in terms of a center, which identifies a location of interest, such as a polling place, and all other points must be labeled with the center to which they are associated. We focus on defining geographic districts that are equitable, in that every district has the same number of points and the assignment is stable in terms of geographic distance. That is, there is no unassigned point-center pair such that both would prefer each other over their current assignments. We solve this problem using a version of the classic stable matching problem, called symmetric stable matching, in which the preferences of the elements in both sets obey a certain symmetry. We also show that by coupling this approach with a k-means clustering algorithm for placing polling places the resulting districts can be reasonably shaped. 

(Joint work with Gill Barequet, David Eppstein, and Nil Mamano.)

Refreshments precede the talk at 3:30 p.m. in NH 282.