Applied

Every map of twenty-five voters

Put twenty-five voters on a five-by-five grid, thirteen red and twelve blue, and divide them into five districts of five connected squares. There are exactly 4,006 ways to do it, and the same votes give red one seat, two, three or four depending on which map is drawn. Listing every map turns the accusation of gerrymandering into a measurement: how unusual a given map is among all the maps that could have been drawn — and the answer depends on where the voters live as much as on how many there are.
14 min read 6 figures Decided by exhaustionSmall cases lie

Worth reading first: Five rules and five winners · A party that loses every issue can win.

Five rules and five winners counted one set of ballots five ways and got five different winners: the rule, not the voters, decided the result. A legislature elected from districts has a second choice hidden in it that is just as decisive and much less visible. Before anyone votes, somebody draws the lines that divide the voters into districts, each electing one member by majority. The votes are counted the same way in every district; the lines decide which votes are counted together.

Drawing the lines to favour one party is gerrymandering, named after a Massachusetts district of 1812 shaped, a cartoonist thought, like a salamander, and approved by Governor Elbridge Gerry. Its two techniques have names too. Packing puts the other party’s voters into a few districts it wins overwhelmingly, wasting their surplus; cracking spreads the rest thinly across many districts it narrowly loses. Both work, and the question for anyone judging a map is not whether it helps somebody — every map helps somebody — but whether it helps them unusually. That needs a list of the maps that could have been drawn. On a small enough grid the list can be made complete, and this essay makes it.

One set of votes, three maps

Thirteen votes in twenty-five, and 1 to 4 seats. clustered voters: seats over 4006 maps from 1 to 4.
Fig. 1 The same 25 voters — 13 red, 12 blue — divided into five districts of five connected squares in three ways. One set of votes gives red 4, 3 or 1 seats.

Twenty-five voters stand on a five-by-five grid, one to a square. Thirteen are red and twelve blue; red lives mostly on the left. The grid is to be divided into five districts of five squares each, every district a connected block — squares joined edge to edge, no district in two pieces — and each district elects whichever party has at least three of its five voters. Equal populations and contiguity are the two rules real districting law imposes almost everywhere, and here they are the only rules.

The figure draws three legal maps. On the left, red wins four of the five seats: its votes are split four, three, three, three and none, so it wins four districts, three of them with nothing to spare, and concedes the fifth entirely to blue. In the middle red wins three, the proportional answer for 52% of the vote. On the right red wins only one: blue has packed red’s voters into one district red wins five to nothing, and cracked the rest so that red loses four districts two to three. The voters are identical in all three maps. Red’s seat count ranges from a fifth of the legislature to four fifths on the strength of where the lines go.

The arithmetic of the extremes is general. A party with vv voters in districts of five needs three to win a district, so it can win at most ⌊v/3⌋\lfloor v/3 \rfloor districts, and with thirteen voters that is four; the other party, with twelve, can likewise win at most four, which leaves red at least one. Whether the extremes are reachable depends on geometry — on whether districts with exactly the right mixtures can be drawn as connected blocks — and for these voters both are.

How many maps there are

How many maps a small grid has. 2: 2, 3: 10, 4: 117, 5: 4006, 6: 451206
Fig. 2 The number of ways to divide an n × n grid into n connected districts of n, every map enumerated: 2, 10, 117, 4,006 and 451,206 for n=2n = 2 to 6, with one map of each size drawn.

To judge one map it has to be compared with the others, so the first task is to list them. The enumeration is a search. Take the first square not yet in a district, list every connected block of five free squares containing it in which it is the first square, and for each such block, assign it and repeat. Every legal map is found exactly once, because the first free square’s district is determined by the map. On the five-by-five grid the search finds 4,006 maps.

The counts grow ferociously. A two-by-two grid has two ways into two dominoes; a three-by-three grid has 10 ways into three trominoes; a four-by-four has 117 into four tetrominoes; five-by-five has 4,006; six-by-six, which takes the search a quarter of a minute, has 451,206. The count is growing faster than exponentially in the number of squares, and for a real state — thousands of census blocks into dozens of districts — the number of legal maps is far beyond any list. That is why the method this essay uses exactly is used in practice by sampling: a random walk through the space of maps, each step reassigning a few blocks between neighbouring districts, of the kind a walk that samples a distribution built, run until it has forgotten where it started.

Every map, with red living together

Every map, with red living together. clustered: seats histogram 0,13,1561,2399,33,0
Fig. 3 All 4,006 maps and how many seats each gives the red party, which has 13 of the 25 votes. In 1,574 of the maps the blue party, with fewer votes, wins a majority of the seats.

With every map in hand, the question “is this map unusual?” has an exact answer. The figure takes the clustered voters of the first figure and counts, over all 4,006 maps, how many seats each gives red. Thirteen maps give red one seat, 1,561 give it two, 2,399 give it three and 33 give it four. No map gives red none or all five.

So the four-seat map of the first figure is extreme: only 33 of 4,006 maps, under 1%, are as good for red. The one-seat map is more extreme still, 13 maps, a third of 1%. If an independent commission were to choose a map at random from the legal ones, red would win three seats 60% of the time, and a map giving red one seat would be a striking outlier — exactly the kind of evidence a court can weigh. This is the ensemble method: compare the map that was drawn with the whole distribution of maps that could have been drawn, and ask where it falls. Jonathan Mattingly and his collaborators used sampled ensembles of this kind in litigation over North Carolina’s congressional maps from 2017 onwards.

The histogram also says something less comfortable. In 1,574 of the maps — 39.3% — blue, with fewer votes, wins a majority of the seats. No one need intend this. A map drawn at random, by a procedure blind to the voters, gives the minority party control of the legislature two times in five, simply because red’s voters live together and red wastes votes in the districts it wins heavily. A party that loses every issue can win found majorities reversed by the way votes were aggregated across issues; here they are reversed by the way they are aggregated across space.

The same count, with the voters mixed

Every map, with the colours mixed. mixed: seats histogram 0,0,56,3930,20,0
Fig. 4 The same 4,006 maps for 13 red and 12 blue voters arranged in a checkerboard. Almost every map gives red three seats.

Change only where the voters live. Put the same thirteen red and twelve blue voters in a checkerboard, every red voter surrounded by blue and every blue by red, and count again. Now 3,930 of the 4,006 maps give red exactly three seats; 56 give it two and 20 give it four. A random map gives red a majority 98.6% of the time, and the extremes are barely reachable.

The difference between the two histograms is the whole difficulty of judging maps. Gerrymandering is possible because voters are not evenly mixed: when like voters live together, a map-drawer can choose which concentrations to split and which to keep, and the spread of possible outcomes is wide. When voters are mixed, every district looks like the whole state and almost every map gives the same answer. The same vote count admits very different ranges of results depending on geography, and so the fairness of a map cannot be read from the votes and the seats alone. It has to be read against the maps that the same geography permits — which is what the ensemble provides and a simple comparison of vote share with seat share does not.

How many seats a share of the votes can buy

How many seats a share of the votes can buy. 5: 0.00-0.91 mean 0.19 [0,1]; 6: 0.00-1.47 mean 0.36 [0,2]; 7: 0.00-1.88 mean 0.57 [0,2]; 8: 0.00-2.00 mean 0.81 [0,2]; 9: 0.00-2.70 mean 1.15 [0,3]; 10: 0.02-3.00 mean 1.48 [0,3]; 11: 1.00-3.00 mean 1.89 [1,3]; 12: 1.00-3.86 mean 2.29 [1,4]; 13: 1.13-4.00 mean 2.70 [1,4]; 14: 2.00-4.00 mean 3.12 [2,4]; 15: 2.02-4.95 mean 3.50 [2,5]; 16: 2.31-5.00 mean 3.86 [2,5]; 17: 3.00-5.00 mean 4.16 [3,5]; 18: 3.10-5.00 mean 4.42 [3,5]; 19: 3.56-5.00 mean 4.66 [3,5]; 20: 4.10-5.00 mean 4.82 [4,5]
Fig. 5 For each number of red voters from 5 to 20 of 25, 200 random arrangements of the voters and every one of the 4,006 maps: dots are the average seats over all maps, the band runs from the fewest to the most seats some map gives.

The two arrangements so far were chosen by hand. The figure takes many arrangements at random. For each number of red voters from 5 to 20, it scatters them over the grid two hundred times, and for each scattering it runs through all 4,006 maps, recording the fewest seats any map gives red, the most, and the average. The dots are the averages and the band runs between the average fewest and the average most.

The average seats track the votes closely, near the dashed line of exact proportionality: 2.70 seats for 13 voters against a proportional 2.6. Over all maps of a random arrangement, districting is roughly fair on average. The band is what a map-drawer has to work with, and it is wide. With thirteen voters of twenty-five, a typical arrangement allows anything from 1.13 to 4.00 seats on average; with ten voters, a minority of 40%, it allows from almost none to three — a majority of the legislature for a minority of the voters. Only at the extremes of the vote share does the band close up, and even with eighteen voters, 72%, some arrangement and some map hold red to three seats of five.

Real districts have hundreds of thousands of voters, not five, and the arithmetic of large districts is gentler: a district’s majority is decided by the local balance of opinion, which varies less from one district to the next when districts are large. But the principle survives the scaling, and a vote worth a square root showed in a different way how much a two-tier vote can change the weight of a voter: the boundaries decide which local majorities exist, and local majorities are all a district election counts.

Nine voters of twenty-five can hold a majority

The band’s upper edge hides a sharper fact. With nine red voters out of twenty-five — 36% — the most favourable arrangement and map give red three seats of five, a majority. The arithmetic is the same as before: three districts with exactly three red voters each, and two districts with none. Districting is a two-stage majority vote, a majority of majorities, and a two-stage majority can be won with just over a quarter of the votes: a bare majority of the voters in a bare majority of the districts. With districts of dd voters and kk districts, that is ⌈(d+1)/2⌉⋅⌈(k+1)/2⌉\lceil (d+1)/2 \rceil \cdot \lceil (k+1)/2 \rceil voters, which for large districts approaches a quarter of the electorate.

That is the same structure how few voters any majority needs studied from the other side — how few voters it takes to produce any given pattern of majorities — and it is the structure in which a share of the votes is not a share of the power measured voting power: in a body that votes by majorities of blocs, a voter’s influence depends on how the blocs are formed, not only on how many voters there are. A map is a choice of blocs. The nine-voter majority needs the most favourable arrangement as well as the most favourable map, and on the clustered and mixed arrangements above it is not available; but the enumeration finds arrangements of nine red voters for which some legal map delivers it, and the band records them.

There is no fair rule hiding behind all this, and the reason is older than any map. Four conditions, and no rule that has all of them proved that no way of aggregating rankings satisfies a short list of reasonable demands at once, and districting is an aggregation in two stages with an extra free parameter — the map — that the voters do not choose. Arrow’s theorem does not apply to it directly, since each district’s vote is a simple majority between two parties, which is the one case where majority rule is beyond reproach, as the majority that goes in a circle noted when it needed three candidates to produce its cycle. The trouble comes entirely from the second stage: two honest majorities, composed, can say the opposite of one.

Wasted votes measure the seats, not the map

Wasted votes measure the seats, not the map. 3 seats: gap -0.08; 2 seats: gap 0.16; 1 seats: gap 0.40; 4 seats: gap -0.32
Fig. 6 For every map of the 13 red and 12 blue voters, the efficiency gap: votes wasted by red minus votes wasted by blue, as a share of all votes. With equal districts it depends only on how many seats red wins.

The best-known numerical test for gerrymandering is the efficiency gap, proposed by Nicholas Stephanopoulos and Eric McGhee in 2014. A vote is wasted if it is cast for a loser, or for a winner beyond the bare majority the winner needed. A map that packs and cracks one party makes that party waste many votes, so the difference between the two parties’ wasted votes, as a share of all votes, is offered as a measure of partisan unfairness; a gap above about 7% was suggested as a warning sign.

The figure computes the gap for every one of the 4,006 maps, and finds that it takes only four values — one for each possible number of seats. That is not a feature of this grid. When every district has the same number of voters, the wasted votes can be added up district by district, and everything cancels except the totals: here the gap is exactly (2v−6s−10)/25(2v - 6s - 10)/25, where vv is red’s 13 votes and ss its seats. In general it is a linear function of the vote share and the seat share alone. So the efficiency gap is not a measurement of the map at all. It is a statement that the seat share should be about twice the vote share’s excess over a half, plus a half — a particular target for the relation between seats and votes, with any map hitting it judged fair and any missing it judged unfair, whatever the geography allows.

That does not make it useless, but it makes it a different kind of test from the ensemble. The efficiency gap compares the result with a fixed rule; the ensemble compares the map with the alternatives. For the clustered voters, the ensemble says a three-seat map is entirely typical; the efficiency gap gives it −8%-8\%, a warning in red’s favour. For the checkerboard voters the two agree. Where voters cluster, the two tests disagree, and the disagreement is exactly the question of whether the geography itself is to be held against a party.

What the enumeration cannot show

Every number here is exact for its grid: the maps are listed completely, every map’s seats are counted, and the counts of maps are checked against each other at every size. What the grid cannot show is a state. Real districts must have equal populations only to within a tolerance, must often respect county lines and communities, and are built from irregular census blocks rather than squares; the ensemble method handles all of this by sampling, and its conclusions depend on the sampling having run long enough, which is a question about the convergence of a Markov chain that a complete list on twenty-five squares never has to face.

And the model’s voters vote for their colour regardless of the map, which no real electorate does. Turnout, candidates and campaigns respond to districts, and a map drawn to crack a party’s voters may produce a different election from the one the map-drawer forecast. The enumeration shows what the lines can do to a fixed set of votes; it does not show what the votes would have been.

Still open: what a fair map is

The mathematics settles what maps exist and what each does; it does not settle which outcome is fair, and the candidates conflict. Proportionality asks that seats track votes, which the clustered voters’ maps mostly fail and which a perfectly neutral process need not produce. The ensemble asks that a map be typical of the legal maps, which accepts whatever bias the geography builds in. Measures based on symmetry ask that the parties would be treated alike if their vote shares were swapped, which is a statement about a hypothetical election. Each has been proposed in court and none is accepted as the definition; the United States Supreme Court held in 2019 that partisan gerrymandering claims are not for the federal courts to decide, leaving the choice to states and legislatures. Which of these criteria can be satisfied together, on which geographies, is itself an open combinatorial question, and seats to parties and places at once found the same kind of incompatibility between two reasonable demands in apportionment.

Lines are a vote too

On a five-by-five grid there are exactly 4,006 ways to draw five connected districts of five, and the same thirteen red and twelve blue voters win red one, two, three or four seats depending on the map. When red lives together, two maps in five give blue, the minority, a majority of the seats, and the most extreme maps are a fraction of a per cent of all the maps — which is how the ensemble method recognises a gerrymander. When the colours are mixed, nearly every map gives the same answer. The efficiency gap, computed for every map, turns out to depend only on the seats, not on the map. The voters decide the votes; the lines decide which votes are counted together, and that is a decision with as many outcomes as there are maps.

Shares its objects with

Essays that name at least two of the same things, and that neither author linked.

Named objects

A dashed tag is an object no other essay names yet.

ApportionmentEnumerationExhaustive searchMajority ruleMonte CarloVoting rule