CAM Colloquium: David Shmoys (ORIE/CS, Cornell) - Fairmandering: A column generation heuristic for fairness-optimized political districting

Description

Abstract:
The American winner-take-all congressional district system empowers politicians to engineer electoral outcomes by manipulating district boundaries. Existing computational solutions mostly focus on drawing unbiased maps by ignoring political and demographic input, and instead simply optimizing for compactness. We claim that this is a flawed approach because compactness and fairness are orthogonal qualities, and introduce a scalable two-stage method to explicitly optimize for arbitrary piecewise-linear definitions of fairness. The first stage is a randomized divide-and-conquer column generation heuristic which produces an exponential number of distinct district plans by exploiting the compositional structure of graph partitioning problems. This district ensemble forms the input to a master selection problem to choose the districts to include in the final plan. Our decoupled design allows for unprecedented flexibility in defining fairness-aligned objective functions. The pipeline is arbitrarily parallelizable, is flexible to support additional redistricting constraints, and can be applied to a wide array of other regionalization problems. In the largest ever ensemble study of congressional districts, we use our method to understand the range of possible expected outcomes and the implications of this range on potential definitions of fairness.

This is joint work with Wes Gurnee.

Bio:
David Shmoys is the Laibe/Acheson Professor in the School of Operations Research and Information Engineering, and the Department of Computer Science, and is Director of the Center for Data Science for Enterprise & Society at Cornell University; e also serves as a Research Consultant to Lyft. His research interests center on algorithms for optimization problems, with applications including scheduling, inventory theory, network design, and computational sustainability. Most recently, his work has focused on issues in mobility and the sharing economy, with particular attention to the development of algorithmic tools to design and support bike-sharing systems.

Zoom Link Access:
The link is emailed to the CAM Seminar listserv the week of the talk. If you are not on the listserv, please contact Erika Fowler-Decatur to request the link.