An Algorithmic Approach to Redraw US Gerrymandered District Boundaries by Minimizing Wasted Votes

Partisan gerrymandering consists of redrawing the district boundaries to give electoral advantage to a political party.In 1986, it was declared unconstitutional and justiciable by the US Supreme Court and, since then, many efforts have been done to find a standard that could be adopted by the Court to quantify gerrymandering and eventually reject a redistricting plan. In previous studies, it was concluded that notions such as quantitative measure of shape compactness and other geometric indices had many limitations,as redistricting policies take into account other constraints, and the algorithms that used those indices were highly computationally complex and made the redistricting process infeasible. Recently, Stephanopoulos and McGhee introduced Efficiency Gap, a new measure of partisan gerrymandering, which is defined as the ratio of the difference between the parties’ wasted votes (in a two-party electoral system) to the total number of votes cast in the election. This metric was found legally convincing by a US Appeals Court in a case appealed in 2017.The aim of this project is providing a local search algorithm able to "un-gerrymander" the 2012 congress district maps for Wisconsin, Virginia, Texas and Pennsylvania by bringing their efficiency gaps to acceptable levels.If the US Supreme Court upholds the decision of lower courts, our work can provide a crucial supporting hand to remove partisan gerrymandering.