College ties

Nate Silver’s fivethirtyeight blog for the New York Times applies computational statistics to U.S. presidential politics. A recent post discusses the possibility of a tie vote in the Electoral College.

If the votes on November 6 should come out according to the map above, we’ll have a 269-to-269 deadlock, leaving it to the House of Representatives to choose the next president. Silver ran 25,001 simulated elections, and the result shown above appeared 137 times. Eight other tied arrangements also turned up, though more rarely. The overall probability of an even split was about 0.6 percent. (The simulations were based on polls taken before last week’s Obama-Romney debate.)

Looking at Silver’s maps, I began to muse about a purely combinatorial question: Setting aside all considerations of political plausibility, in how many different ways can the Electoral College vote come out a tie? To put it another way, how many two-colorings of the U.S. map give each party 269 Electoral College votes?

I now have an answer to this question, which I’ll give below. But first, for the benefit of my non-U.S. readers, I should say a word about that curious institution the Electoral College. It was the wisdom of the Founders that the POTUS should not be elected directly by the people but rather by the states, with each state getting as many votes as it has senators (two each) plus members of the House of Representatives (from 1 to 53, depending on population). Since 1964 the District of Columbia (which isn’t a state, but I’m going to call it one anyway) has also had three votes. Thus there are 51 voting states, with vote allocations ranging from 3 to 55, and the total number of votes is 538.

California 55	Maryland 10	Utah 6
Texas 38	Minnesota 10	Nebraska 5
Florida 29	Missouri 10	New Mexico 5
New York 29	Wisconsin 10	West Virginia 5
Illinois 20	Alabama 9	Hawaii 4
Pennsylvania 20	Colorado 9	Idaho 4
Ohio 18	South Carolina 9	Maine 4
Georgia 16	Kentucky 8	New Hampshire 4
Michigan 16	Louisiana 8	Rhode Island 4
North Carolina 15	Connecticut 7	Alaska 3
New Jersey 14	Oklahoma 7	Delaware 3
Virginia 13	Oregon 7	District of Columbia 3
Washington 12	Arkansas 6	Montana 3
Arizona 11	Iowa 6	North Dakota 3
Indiana 11	Kansas 6	South Dakota 3
Massachusetts 11	Mississippi 6	Vermont 3
Tennessee 11	Nevada 6	Wyoming 3

Generally, each state’s votes are cast as a winner-take-all block (but see the note on Maine and Nebraska at the end of this post).

I assume here that only two parties receive Electoral College votes. Thus any partitioning of the elector list into two subsets—red and blue—is a possible election outcome. The number of distinguishable outcomes is simply the product of all these binary choices: 2⁵¹, or 2,251,799,813,685,248. We want to know how many of these cases yield exactly 269 red and 269 blue votes. It turns out there are 16,976,480,564,070 ways of arriving at a drawn election, which is roughly 0.75 percent of the total.

Let me emphasize that this number is of no political consequence; in particular, it says nothing about the probability of a tie—at least not unless the states choose their votes by flipping fair coins. I can’t see where the number holds any notable mathematical significance either. What attracted my interest was simply the challenge of computing it.

Doing it the direct and obvious way—enumerating all 2⁵¹ partitions and summing the votes for each case—is not utterly unthinkable. Amazingly enough, we live in a world where you can count to a quadrillion and live to tell the tale. But doing so would require more programming effort—or more patience or more hardware—than I’m willing to invest for the sake of idle curiosity.

It’s interesting that some bigger problems are actually easier. Suppose we keep the number of electors constant at 538 but we subdivide the states into smaller territories, each of which gets fewer votes. In the limiting case there are 538 regions with one vote each. Now the problem is immensely larger: There are 2⁵³⁸ ways of two-coloring a map with 538 regions. Nevertheless, with very little fuss we can calculate the number of tied configurations, without having to count them all one by one. The number is:

$$\binom{538}{269} = \frac{538!}{(269!)^2} \approx 3 \times 10^{160}.$$

(The exact value is 30937469012875859932471852213149074559 46754979248232932201743920079668590495281866215749684213 30476315882464242716565222046883627439960129220374560486 58575478800.)

Is there some similar mathematical magic that will solve the original Electoral College problem? Not quite so neatly, as far as I know. But the same underlying principle offers a measure of help.

Let’s focus for a moment on the eight states in the Electoral College that get three votes each. Considering just those states in isolation, they have 2⁸ = 256 possible red-blue configurations, but only nine different ways of contributing to the election outcome. If red wins none of the states, it gets zero votes. If red wins any one of the states, it gets three votes, and there are eight ways for this to happen. Winning any two of the states yields six votes, and there are \(\binom{8}{2} = 28\) combinations with this result. In the map above, red wins five of the three-vote states (Alaska, Montana, North Dakota, South Dakota and Wyoming) while blue wins three (Delaware, the District of Columbia and Vermont). This combination is one of 56 that produce a 15–9 vote split in favor of red. By weighting the vote sums according to the appropriate binomial coefficients, we can deal with just nine cases instead of 256.

The same trick works for the five states that get four votes apiece, the three states that have five votes each, and so on. A neat way of organizing the computation is to count through all the possible values of a mixed-radix number (where each digit has its own radix, independent of its neighbors). For the Electoral College data, the mixed-radix number has a digit for each set of states that are allocated the same number of votes; the radix of this digit is one more than the number of states in the set. The number of 19 digits overall, with radices ranging from 2 to 9.

We can survey the full spectrum of election outcomes by cycling through all the values of this number, starting at 0000000000000000000 and counting up to 1122121111443236358. For each value we calculate the corresponding vote total s:

$$s = \sum_i k_i m_i$$

Then we use s as an index into an array H where we keep track of how many ways the total s can be achieved. We increment H_s by the appropriate number of combinations:

$$H_s = H_s + \prod_i \binom{r_i}{k_i}$$

With this algorithm, the number of configurations for which we need to sum up the votes is 6,270,566,400, which is a lot less than 2⁵¹. Even allowing for the extra work of calculating binomial coefficients, the mixed-radix strategy reduces the size of the computation by a factor of 10,000 or so. For a Lisp program running on a laptop, it becomes a job of hours rather than years.

Since I was riffling through all of those 6,270,566,400 configurations anyway, I figured I might as well record not just the number of ties but the full spectrum of vote totals. It’s no surprise that the result looks like a binomial distribution:

What did surprise me a little is the smoothness of the curve. I was expecting a bit of lumpiness because of the minimum allocation of three votes and because a few states constitute large, indivisible blocks of votes. If you zoom in on the extreme tails of the distribution, there is indeed some jaggedness:

   votes:        0  1  2  3  4  5   6   7   8    9   10
   combinations: 1  0  0  8  5  3  34  43  36  122  201

There’s just one way that a party can receive zero votes; winning either one or two votes is impossible; seven votes are more likely than either six or eight. But fluctuations of this kind become undetectable toward the middle of the distribution.

Is there some other approach that would improve on the mixed-radix algorithm? Almost surely. But I would bet against the possibility of a polynomial-time algorithm. Counting Electoral College ties is a variation on another problem for which I harbor a special fondness, called the number partitioning problem (NPP). I was introduced to the NPP by my friend Stephan Mertens, and I wrote about it in a 2002 American Scientist column. The NPP asks whether a set of positive integers has at least one partitioning into two sets that have the same sum. In this form, the problem is NP-complete. The counting version of the problem is surely no easier.

Finally, I have to confess that I haven’t really computed all the ways that the Electoral College can wind up with a tied vote. The snag is that pesky pair of states Maine and Nebraska, which do not necessarily award all their votes to the winner of the state contest. Instead they allocate one elector to the winner in each Congressional district, with the two senatorial electors going to the winner of the entire state. Thus Maine could be viewed as comprising three voting territories with allocations of 1, 1 and 2 electoral votes; Nebraska breaks down into four districts with 1, 1, 1 and 2 votes. This fragmentation of the vote expands the combinatorial challenge of counting ties. Another complication is even more troublesome: The intrastate voting territories are not independent. Unless vote counting is even more treacherous than it seems, you can’t lose all of a state’s Congressional districts but win the state overall. In my calculations I’ve simply ignored the possibility of split votes in Maine and Nebraska; perhaps someone else would like to patch this up.

Yet another caveat is that the Electoral College is not just a mathematical artifice but also a human institution. The electors are people who pledge to vote according to the mandate of their state, but they are not compelled to do so. An elector who ignores his or her instructions and votes for Mickey Mouse may well be punished after the fact, but the vote for Mickey stands, nonetheless.

Update 2012-10-10: I wrote: “Is there some other approach that would improve on the mixed-radix algorithm? Almost surely.” Well, I got that right, and I’ve never felt quite so chagrinned about being correct. An anonymous commenter suggested trying dynamic programming, and soon after that Iain Murray posted an elegant, terse Python program based on that principle. His program answers the how-many-ties? question in milliseconds. It’s hard to fathom how I could have spent several days noodling over the tie-counting problem and missed a solution that’s so clearly superior. Especially since I’d seen it before. I mentioned above that Stephan Mertens introduced me to the number-partitioning problem. His lovely book The Nature of Computation (co-authored with Cristopher Moore) includes a detailed discussion of a dynamic-programming algorithm for the NPP.

One final point: Although Murray’s program is fast, it is not polynomial-time (nor does he make any claims to that effect). The anonymous commenter correctly states that the running time of the algorithm is proportional to the product of the number of states and the number of electors. But the size of the input is the logarithm of this number. Thus the running time is an exponential function of the number of bits in the input.