Multiobjective Optimization for Politically Fair Districting: A Scalable Multilevel Approach

Political districting in the United States is a decennial process of redrawing the boundaries of congressional and state legislative districts. The notion of fairness in political districting has been an important topic of subjective debate, with district plans affecting a wide range of stakeholders, including the voters, candidates, and political parties. Even though districting as an optimization problem has been well studied, existing models primarily rely on nonpolitical fairness measures such as the compactness of districts. This paper presents mixed integer linear programming (MILP) models for districting with political fairness criteria based on fundamental fairness principles such as vote-seat proportionality (efficiency gap), partisan (a)symmetry, and competitiveness. A multilevel algorithm is presented to tackle the computational challenge of solving large practical instances of these MILPs. This algorithm coarsens a large graph input by a series of graph contractions and solves an exact biobjective problem at the coarsest graph using the ϵ − constraint method. A case study on congressional districting in Wisconsin demonstrates that district plans constituting the approximate Pareto-front are geographically compact, as well as efficient (i.e., proportional), symmetric, or competitive. An algorithmically transparent districting process that incorporates the goals of multiple stakeholders requires a multiobjective approach like the one presented in this study. To promote transparency and facilitate future research, the data, code, and district plans are made publicly available.