Mathematical models of political districting for more representative governments

Political Districting, the problem of partitioning a geographical region into sub-regions as electoral districts for political seat assignment, has been widely studied by researchers of both social and mathematical sciences. In the US, one Congressional representative is elected for each such district, and the Constitution requires compactness, geographical contiguity, and population balance for any such district. Gerrymandering, i.e., misuse of redistricting once every 10 years (after each new census) to benefit a particular political party or current incumbent(s), has been practiced for decades, and political strongholds for individual parties have been formed. The vast majority, if not all, of the current literature and proposed software tools on political districting focus on how to achieve the non-political constitutional requirements. Election and re-districting are political processes; we believe that software tools are needed to achieve political purposes. In this paper, we present two mathematical optimization models to implement two new political criteria: fairness and competitiveness. Fairness aims to ensure fair allocation of seats to political parties considering the distribution of voters. Competitiveness aims to maximize the number of competitive districts to prevent districting solutions that provide clear advantage to one political party. We show that the feasibility problem associated with each of the two optimization models is NP-complete. Both models are implemented with a case study of South Carolina. The numerical results of six scenarios demonstrate their effectiveness and efficiency. A strategy is proposed to deal with the issue of computational complexity associated with a state that is partitioned into a large number of indivisible area/population units, e.g., census tracks, as building blocks of electoral districts. The two models can be extended or modified to address fairness and competitiveness issues in some political systems with three or more political parties.