Algorithmic Tools for Congressional Districting: Fairness via Analytics

Thursday, September 30, 2021 - 4:15pm to 5:15pm

Event Calendar Category


Speaker Name

David Shmoys


Cornell University

Building and Room number



The American winner-take-all congressional district system empowers politicians to engineer electoral outcomes by manipulating district boundaries. To date, computational solutions mostly focus on drawing unbiased maps by ignoring political and demographic input, and instead simply optimize for compactness and other related metrics. However, we maintain that this is a flawed approach because compactness and fairness are orthogonal qualities; to achieve a meaningful notion of fairness, one needs to model political and demographic considerations, using historical data.

We will discuss two papers that explore and develop this perspective. In the first (joint with Wes Gurnee), we present a scalable approach to explicitly optimize for arbitrary piecewise-linear definitions of fairness; this employs a stochastic hierarchical decomposition approach to produce an exponential number of distinct district plans that can be optimized via a standard set partitioning integer programming formulation. This enables the largest-ever ensemble study of congressional districts, providing insights into the range of possible expected outcomes and the implications of this range on potential definitions of fairness. In the second paper (joint with Nikhil Garg, Wes Gurnee, and David Rothschild), we study the design of multi-member districts (MMDs) in which each district elects multiple representatives, potentially through a non-winner-takes-all voting rule (as currently proposed in H.R. 4000). We carry out large-scale analyses for the U.S. House of Representatives under MMDs with different social choice functions, under algorithmically generated maps optimized for either partisan benefit or proportionality. We find that with three-member districts using Single Transferable Vote, fairness-minded independent commissions can achieve proportional outcomes in every state (up to rounding), and this would significantly curtail the power of advantage-seeking partisans to gerrymander. We believe that this work opens up a rich research agenda at the intersection of social choice and computational redistricting.


David Shmoys is the Laibe/Acheson Professor and Director of the Center for Data Science for Enterprise & Society at Cornell University. He obtained his PhD in Computer Science from the University of California at Berkeley in 1984, and held postdoctoral positions at MSRI in Berkeley and Harvard University, and a faculty position at MIT before joining the faculty at Cornell University. He was Chair of the Cornell Provost’s “Radical Collaborations” Task Force on Data Science and was co-Chair of the Academic Planning Committee for Cornell Tech. His research has focused on the design and analysis of efficient algorithms for discrete optimization problems, with applications including scheduling, inventory theory, computational biology, computational sustainability, and most recently, data-driven decision-making in the sharing economy. His work has highlighted the central role that linear programming plays in the design of approximation algorithms for NP-hard problems. His book (co-authored with David Williamson), The Design of Approximation Algorithms, was awarded the 2013 INFORMS Lanchester Prize and his work on bike-sharing (joint with Daniel Freund, Shane Henderson, and Eoin O’Mahony) was awarded the 2018 INFORMS Wagner Prize. David is a Fellow of the ACM, INFORMS, and SIAM, and was an NSF Presidential Young Investigator.