Theory Seminar

  • Distinguished Professor
  • Department of Computer Science
  • University of California at Irvine

Fighting Gerrymandering with Algorithmic Fairness

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.)

Professor Michael Goodrich received his B.A. in Mathematics and Computer Science from Calvin University in 1983 and his PhD in Computer Science from Purdue University in 1987. He is a Distinguished Professor at the University of California, Irvine, where he has been a faculty member in the Department of Computer Science since 2001. He was a professor in the Department of Computer Science at Johns Hopkins University from 1987-2001.

Dr. Goodrich's research is directed at the design of high performance algorithms and data structures with applications to information assurance and security, the Internet, machine learning, and geometric computing. He has led research on efficient algorithms for a number of fundamental problems, including geometric optimization problems, sorting, convex hull construction, nearest-neighbor searching, linear programming, privacy-preserving data access, network traceback, and data authentication.

For More Information, Please Contact: