Mathematical models of political districting for more representative governments. (February 2020)

• Record Type: Journal Article
• Authors: Liu, Hongrui; Erdogan, Ayca; Lin, Royce; Tsao, H.-S. Jacob
• Is Part Of: Computers & industrial engineering. Volume 140(2020)
• Publication Date: 2020-02
• Subjects: Political districting -- Math modeling -- Optimization -- Fairness -- Competitiveness; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2019.106265
• Languages: English
• ISSNs: 0360-8352

Abstract

Highlights: Binary linear programs formulated for fair & competitive elections of two parties. Ease of understanding by & implementation for redistricting-commission staff. NP-hardness for the two optimization problems and a strategy to overcome it. Timely contribution to redistricting after 2020 US Census and in other democracies. Promising numerical experiments and results for the state of South Carolina. Abstract: 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 re-districting 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.