Gerrymander North Carolina

Question

The challenge

How well can you gerrymander North Carolina into 13 voting districts?

In this challenge, you use the following files to draw different maps for Republicans and Democrats.

File 1: NC_2016_presidential_election.csv

File 2: NC_county_adjacency.csv

File 1 gives county-level voting data from the 2016 presidential election (based on this and that), while File 2 gives adjacency information between counties (based on this). For File 2, the first entry of each row is adjacent to the other entries in that row. For example, Alexander is adjacent to Alexander, Caldwell, Catawba, Iredell and Wilkes. (Note that every county is adjacent to itself.)

Admissibility

Your code should be written in a way that can gerrymander arbitrary maps. In particular, your code must take each of the following as inputs:

• A set \$C\$ of counties and a set \$P\$ of parties.

• Weights \$(v_{cp})\$ that count voters in county \$c\in C\$ who vote for party \$p\in P\$. (E.g., File 1.)

• A connected graph \$G\$ with vertex set \$C\$. (E.g., File 2.)

• A number of districts \$k\$.

• A party \$p^\star\in P\$ to gerrymander in favor of.

The output must be an assignment of counties to districts such that the counties in each district induce a connected subgraph of \$G\$. For example, for the counties in Files 1 and 2 (listed in alphabetical order), the following is one of 13! sequences that specify the partition of counties into districts pictured below:

3,5,5,10,5,5,13,11,10,8,9,12,1,12,13,13,3,9,3,12,13,12,9,8,13,10,13,13,4,4,8,11,11,5,7,9,11,12,11,13,4,11,7,12,12,11,1,13,4,12,7,13,3,13,9,12,12,11,12,2,12,1,1,7,8,11,13,3,13,13,8,13,3,11,9,3,10,10,3,1,9,8,10,1,5,5,12,12,13,10,11,6,11,11,5,8,5,7,5,12

(This map is loosely based on the current map of U.S. congressional districts in North Carolina.)

Scoring

Your score is determined by how your code performs for various problem instances.

Given a district assignment, let \$d\$ denote the number of districts for which party \$p^\star\$ receives the plurality of votes cast, and let \$a\$ and \$b\$ denote the minimum and maximum number of voters in a district, respectively. Then the score for the district assignment is given by

$$ \text{assignment score} = d - \frac{b}{a}. $$

For example, if \$p^\star\$ is the Republican party, then the district assignment described above has \$d=10\$, \$a=247739\$, and \$b=527337\$, leading to a score of about \$7.87\$.

To compute your score, gerrymander North Carolina (as specified in Files 1 and 2) into \$k=13\$ districts in favor of the Republican party, and then in favor of the Democratic party. Let \$S_1\$ denote the sum of these two assignment scores. Next, gerrymander 10 different modifications of North Carolina, each obtained by removing one of the following counties from Files 1 and 2:

Cleveland,Davidson,Hyde,Johnston,Madison,Montgomery,Pender,Scotland,Warren,Wilkes

(Since North Carolina is biconnected, each of these are acceptable problem instances.) For each modification, gerrymander into \$k=13\$ districts in favor of the Republican party, and then in favor of the Democratic party. Let \$S_2\$ denote the sum of these 20 assignment scores. Then the score of your submission is given by

$$ \text{submission score} = S_1+\frac{S_2}{10}. $$

In addition to your code, you are encouraged to provide an illustration of your two maps that gerrymander all of North Carolina for Republicans and for Democrats. (DRA2020 might be a helpful resource.)