Rig the election with math!

This Riddler problem is about gerrymandering. How to redraw borders to sway a vote one way or another.

Below is a rough approximation of Colorado’s voter preferences, based on county-level results from the 2012 presidential election, in a 14-by-10 grid. Colorado has seven districts, so each would have 20 voters in this model. In each district, the party with the most votes will win. The districts must be non-overlapping and contiguous (that is, each square in a district must share an edge with at least one other square in the district). What is the most districts that the Red Party could win? What about the Blue Party? (Assume ties within a district are considered wins for the party of your choice.)

Two boards are provided, a test 5×5 grid and the larger 14×10 grid:
gerry_combo

Here is a first solution, using some simple logic and intuition:
[Show Solution]

And here is a computational approach, using integer programming:
[Show Solution]

4 thoughts on “Rig the election with math!”

  1. Since ties can be counted to your advantage, you don’t need two different solutions. The best solution for the party with fewer squares is automatically the best for the other party as well since it is to the advantage of both parties to go for maximum ties. Your solution for ‘most blue wins’ also works for ‘most red wins’. Right?

    1. I’m not sure I understand your comment — maximizing the number of districts where blue wins is different from maximizing the number of districts where red wins… Of course, the problems are similar in the sense that we could just swap red and blue and one problem becomes the other… but still for a particular voting map, you definitely get different results depending on whether you maximize red or blue.

  2. I also tried integer programming for this, but I handled the contiguity constraint differently. In each district, I assigned one random county as the “seat” of that district. I introduced the decision variables y_ij to assign the seat of each district (it equals 1 if cell i is the seat of district j). Contiguity was added by requiring each cell to have at least one neighbor that was closer to the district seat. This required me to use quadratic constraints (there were y*x terms), but Gurobi handles that easily and was able to solve the 5-by-5 in less than a second.

    Unfortunately, I couldn’t get an answer for the 14-by-10 either, despite running for several hours.

    1. I wish I had tried this before, but I just now tried selecting 7 random cells to be district seats, and it can find an answer in around 5 seconds for most guesses. For bad choices, it keeps running, quickly finding district lines that win 4/7 seats, but spending what I assume would be hours or days proving that those lines are optimal given that choice of seats.

      If I had a more rigorous way of pre-selecting the district seats, I would have a pretty robust solver for this problem.

Leave a Reply

Your email address will not be published. Required fields are marked *