Algorithms for Fair Redistricting

Abstract

Redistricting is the act of dividing land into geographic regions, called districts, for political or administrative purposes. The most notable---and contentious---example comes from the United States House of Representatives, where seats are apportioned among states according to their respective populations following a decennial census, then assigned to political districts, with each district holding a separate election for a single representative. Political redistricting occurs periodically at other state and local levels, alongside other forms of redistricting for non-political purposes, such as the determination of school attendance zones. In all of these settings, there is a vast space of possible outcomes to consider and a compelling need for fairness and transparency. In this thesis, we design algorithms for various redistricting tasks and provide theoretical underpinnings for existing algorithms. We begin by considering the initial task of seat apportionment, exploring the space of randomized allocation methods satisfying strong fairness guarantees while eliminating unwanted correlations across states. We then turn to the task of drawing redistricting maps that are provably fair, using ideas and results from the Cake-Cutting model in fair division. Finally, we contribute new algorithms and theory for the task of sampling random redistricting maps, with the aim of building robust statistical tests for assessing partisan fairness.