Gerrymandering using Constraint Programming

As the U.S. presidential election approaches, the buzz around gerrymandering grows louder. Gerrymandering—the crafty art of redrawing electoral districts to tip the scales in favor of a particular party—is as intriguing as it is controversial. But what if we could use constraint programming to simulate and understand this phenomenon? Let's embark on a computational adventure to see how this can happen!

Let's assume we know the votes of individuals based on their locations. The question is how to manipulate the electoral district boundaries to advantage a party, group, or socioeconomic class within the constituency.

As usual, I try to demonstrate it using a simplified example:

The sample population size is 50 (20 people will vote for yellow party and 30 people will vote for grey party).

There should be 5 districts (for simplicity they should be of the same size = 10)

Some ways of districting is as follows: in all these cases the grey party wins.

Is there any way we can help the yellow party win the election ?

Problem requirements

• There are 5 regions
• The number of voters in each region is 10
• Each voter only belongs to one region.
• The region is created of connected cells (vertically or horizontally)

Problem Formulation

1. Each region has only one source
2. Each region has 10 cells
3. The number of voters to each party is different in each region
4. In region r, the yellow party wins if the number of voters are higher
5. In region r, the grey party wins if the number of voters are higher
6. Each node can be the source for at most one region.
7. Each node can be assign to only one region
8. The nodal balance (for connectivity of region)
9. A node can be source of region r only if this node is in region r
10. The flow between node i and j can happen only if both cells are in the region r
11. The number of won regions by yellow party= M

Winr Binary variable region r won by yellow

Anr Binary variable assigning cell n to region r

Snr Binary variable assigning cell n to region r as the source

flow_{n,j,r} Integer variable moving from cell n to cell j to region r

Python code:

def main() -> None:
    # Creates the model.
    model = cp_model.CpModel()

    assign = {(n,r): model.NewBoolVar(f"assign_{n}_{r}") for n in nodes
              for r in regions}

    source = {(n,r): model.NewBoolVar(f"source_{n}_{r}") for n in nodes
              for r in regions}
    win = {r: model.NewBoolVar( f"win_{r}")
              for r in regions}
    flow = {(i,j,r): model.NewIntVar(0,10,f"flow_{i}_{j}_{r}") for i in nodes
              for j in nodes for r in regions if check(i,j,data)}
    for r in regions:
      expressions = [source[n,r] for n in nodes]
      model.AddExactlyOne(expressions)

      expressions_assign = [assign[n,r] for n in nodes]
      model.Add(sum(expressions_assign) == 10)

      expressions_winD = [assign[n,r] for n in nodes if data[n][2]==0]
      expressions_winR = [assign[n,r] for n in nodes if data[n][2]==1]
      model.Add(sum(expressions_winD) != sum(expressions_winR))

      model.Add(sum(expressions_winD) > sum(expressions_winR)).OnlyEnforceIf(win[r])
      model.Add(sum(expressions_winD) < sum(expressions_winR)).OnlyEnforceIf(win[r].Not())

    for n in nodes:
      expressions_nodal = [source[n,r] for r in regions]
      model.AddAtMostOne(expressions_nodal)

      expressions_assign = [assign[n,r] for r in regions]
      model.Add(sum(expressions_assign) ==1)


    for (n,r) in assign:
      model.Add( 10*source[n,r] - assign[n,r] == sum(flow[n,j,r]-flow[j,n,r] for j in nodes if check(n,j,data) ) )
      model.Add(source[n,r]<= assign[n,r])

    for (i,j,r) in flow:
      model.Add(flow[i,j,r] <= 10*assign[i,r])
      model.Add(flow[i,j,r] <= 10*assign[j,r])

    model.Add(sum(win[r] for r in regions)== 0)

    solver = cp_model.CpSolver()
    solver.parameters.subsolvers[:] = ['core', 'pseudo_costs', 'no_lp']
    solver.parameters.max_time_in_seconds = 1200
    solver.parameters.num_search_workers = 4
    status = solver.solve(model)
    print(solver.StatusName(status))
    print(solver.ObjectiveValue(), solver.BestObjectiveBound())        

Results:

Let's make the grey party winner by 3 to 2

Let's make the grey party winner by 4 to 1

Let's make the yellow party winner by 3 to 2

But what if we are now allowed to put two cells too far away in a region ?

max allowed distance = 5 cells

We can add more constraints to avoid this situation:

Gerrymandering can significantly impact election outcomes and is a topic of ongoing debate regarding its fairness and effect on democratic representation.

Gerrymandering is more than just a political strategy; it's a fascinating problem that sits at the intersection of mathematics, computer science, and ethics. By using constraint programming, we can not only understand how gerrymandering happens but also explore ways to detect and prevent it.