Setting up Hexapolis

[mcmcclur]

The NYTimes posted a fun, educational game to illustrate gerrymandering. The game deals with an imaginary state called Hexapolis - a map of which looks something like so:

The map consists of 135 hexagonal precincts with equal population 1. Each precinct belongs to one of two parties; there are 60 yellow precincts and 75 purple. In addition, 41 of the precincts belong to a minority with some legal protection; those precincts are indicated with a bold border on its inner hexagon.

To play the game, you must partition the map into 9 districts of 15 precincts each. By law, two of your districts must be more than 50% minority. Note that

\frac{60}{135} = \frac{4}{9} \approx 44.4\%.

Thus, we might expect a fair map to consist of 4 predominantly yellow districts and 5 predominantly purple. On the other hand, we’d say that the partition is skewed purple if there are more than 5 purple districts, and we’d say that the partition is skewed yellow if there are more than 4 purple districts.

The objective of the game is to see how far you can skew the partition in one direction or the other. You can earn bonus points by keeping your districts relatively compact. The objective of this notebook is to set the game up so that programmers can try their hand at writing gerrymandering software on Observable.

---

According to information you get from the NY Times after playing, it’s possible to partition Hexapolis so that all districts lean purple. They also indicate it’s possible to partition Hexapolis so that 7 districts lean yellow, but not 8.

This paper on the ArXive describes some gerrymandering algorithms at a fairly high level. Using the techniques they call Flood Fill to set up some initial districts followed by a Flip Step Walk to improve them, I found it pretty easy to 8 purple districts and 6 yellow. I’ve not achieved the maxima just yet, though.

---

All of the above is pretty much exactly the following notebook (of course, the notebook has code, though):

Setting up Hexapolis

[visnup]

I had a feeling I’d find something if I searched boardgamegeek: Mapmaker: The Gerrymandering Game | Board Game | BoardGameGeek

[mcmcclur]

I did get a few likes on the setup notebook but no one pushed it further, as far as I know. While I’ve still not been able to achieve the optimum results algorithmically, I have been able to generate a lot of maps! Here are 538 distinct partitions of Hexapolis, from almost all purple to mostly yellow:

[Fil]

Thank you for setting up the board so we can have fun with it.

I found a purple solution I explored a bit by hand, by taking your best purple map and doing two permutations involving each 3 points, rather than two.

The red and the green permutations each trade a yellow for a purple for the yellow district, which then becomes purple.

I don’t think I’ve seen such 3-points permutations among the operations listed in the algorithms paper?

I haven’t tried to implement any algorithm, but my intuition is that these pathways open more expressive possibilities than the swaps across a border. They allow exchanges between two neighbors by involving a third one. The combinatorics is not astronomic, since this can only be done between three neighbors, which means we can explore the possibilities (maybe not all of them, but most of them) by listing the tripoints, which are less than a dozen on a valid map. (?)

PS. I realize that I didn’t check for the minorities constraint, and my solution is invalid. Would have been too easy :)… Anyway, it’s a first step. It would be nice to check that constraint visually.

[mcmcclur]

I’m glad you like it! This notebook (which is not at all ready to be released) allows you to pick some compact districts by hand. Once picked, you can click on two hexagons on the border of neighboring districts to swap them. My plan is to update the displayed info (like minority_cnt) so that you can see what’s going on. I really built all this stuff to share with my Intro Stats class and it’s a lot easier to explain it in person.