ABSTRACT
The American winner-take-all congressional district system empowers politicians to engineer electoral outcomes by manipulating district boundaries. To date, most computational solutions 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 a series of papers that explore and develop this perspective. We first 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 a large-scale 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. Further work extending this shows that many additional real-world constraints can be easily adapted in this framework (such as minimal county splits as was recently required in Alabama legislation in response to the US Supreme Court decision Milligan v. Alabama). In addition, one can adapt the same framework to heuristically optimize for other fairness-related objectives, such achieving a targeted number of majority minority districts (and in taking this approach, achieving stronger results than obtained by a prominent randomized local search approach known as “short bursts”).
We also show that our optimization infrastructure facilitates the study of the design of multi-member districts (MMDs) in which each district elects multiple representatives, potentially through a non-winner-takes-all voting rule (as was proposed in H.R. 4000 in an earlier session of Congress). 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.
This is joint work with Wes Gurnee, Nikhil Garg, David Rothschild, Julia Allen, Cole Gaines, David Domanski, Rares-Stefan Bucsa, and Daniel Brous.
BIO
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 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. He was awarded the 2022 INFORMS Optimization Society Khachiyan Prize, the 2023 INFORMS Morse Lectureship, and the 2024 INFORMS Kimball Medal. 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.
