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 maps having consequences to multiple stakeholders. Even though districting as an optimization problem has been well-studied, existing models primarily rely on non-political fairness measures such as the compactness of districts. This paper introduces optimization models for districting with political fairness criteria. The criteria considered are based on fundamental fairness principles such as vote-seat proportionality (efficiency gap), partisan (a)symmetry, and competitiveness. Given the large sizes of practical instances, a multilevel algorithm is presented, which first reduces instance sizes by a series of graph contractions, and then solves an exact multi-objective problem at the inner level using the $\epsilon-$constraint method. The non-linearity of the partisan asymmetry objective is efficiently tackled with the branch-and-cut method. Case studies on congressional districting in Wisconsin are presented. The results demonstrate that district plans constituting the Pareto-front are equitable, symmetric, competitive, and compact, and that a multi-objective approach is integral to paving the way towards a holistic districting process that addresses all the stakeholders.
Citation
Swamy, R., King, D.M., Jacobson, S.H. (in press). Multi-Objective Optimization for Politically Fair Districting: A Scalable Multilevel Approach. Operations Research.
Article
View Multi-Objective Optimization for Politically Fair Districting: A Scalable Multilevel Approach