For an individual voter to be able to cast a critical vote, the other voters in the group must be equally divided. The formula for the number of combinations which can be formed by M persons divided into two equal groups is M ! æ ç è M 2 ! ö ÷ ø æ ç è M 2 ! ö ÷ ø

This expression comes from the standard combinatorial formula for the numbers of ways you can choose p items (in this case, voters who for vote candidate #1) from n total items (i.e. total voters). That quantity is the combination (n,p) and is given by

Banzhaf continues:

... In calculating the number of times each person can cast a critical vote, the function must be multiplied by 2 to account for votes for the two different candidates. ... Consider a group made up of N+1 citizen-voters, where N is an even number. The total number of ways in which each citizen-voter could vote for either of the two principal candidates is 2^(N+1) which is equal to 2 x 2^N. Each would be able to cast a critical vote only where the other N citizen-voters were equally divided into two groups; N/2 voting yea and N/2 voting nay. This, as previously indicated, can happen in 2 N ! æ ç è N 2 ! ö ÷ ø æ ç è N 2 ! ö ÷ ø ways. Thus, an individual citizen-voter would be critical in determining the outcome of a vote in the following fraction of combinations. 2 N ! æ ç è N 2 ! ö ÷ ø æ ç è N 2 ! ö ÷ ø      ¸   ( 2 ·2N )

You might think that the probability has an inverse linear relationship to the population of the block. However, as Banzhaf and others have shown, this is not correct. The probability is related to the inverse square root of the block's population. This is rather surprising at first glance, but you can either accept the equations below as proof, or do it yourself and see.

So Banzhaf continues by simplifying the expression and using Stirling's approximation for factorial of large numbers to arrive at the final probability of an individual voter being critical in determining the block's decision. This gives the inverse-square-root-relationship.

... The factorial of large numbers may be very closely approximated by the following formula which is known as Stirling's formula. [ For those unfamiliar with mathematical notation, the wavy equal sign means "approximately equals." ] m ! » e-m mm   æ Ö 2 pm   Substituting this value into the previous formula by allowing N/2 to equal m, the function becomes e-2m (2m)2m   æ Ö 4 pm   22m e-m mm    æ Ö 2 pm    e-m mm    æ Ö 2 pm   which equals   æ Ö 2     æ Ö p N

So that's the first factor in Banzhaf's Power Index. (inhale, exhale)

The next factor really cannot be computed directly with a simple (ahem) formula like Stirling's approximation. Or at least, I don't know of one (and aren't you glad). Apparently, neither did Banzhaf. He did say in a footnote (rather dryly, if I might editorialize momentarily)

... Naturally there are certain shortcuts in the calculations which can be made in practice, either when the calculations are done by hand or with the use of an electronic computer. They are, however, beyond the scope of this article. [5]

On another occasion, Banzhaf said slightly more about what he did.

The calculations for [this] step of the analysis of the [1960] Electoral College were actually done in two slightly different ways, using two essentially similar techniques. The first was performed by Lloyd S. Shapley and Irwin Mann (both of whom assisted [Banzhaf] in formulating the material in [1]).

The words in [square brackets] in the above quote are my attempts to have Banzhaf's words be clear references in the context of this web page. There is no change to what Banzhaf means with these changes.

So the question is now, "What did Shapley and Mann do to compute their numbers?" Well, they had a slightly different definition of power of a block in a block voting system, but that's not really important for the current purpose. What is important was that they used a very general approach to computing probabilities over large possible outcome sets which is known as the Monte Carlo approach. This will surprise few mathematicians and computer scientists.

For those unfamiliar with the Monte Carlo technique, the brief description is that you sample the possible outputs some number of times and count the number of times that the event in question occurs. Then you assume that your sampling was unbiased, so that the true probability of the event is simply the number of occurrences you saw divided by the number of samples you took. Obviously, you need to cover a significant portion of the possible outcomes before this will give accurate results. Monte Carlo simulation is a large topic, and I won't go in to it any further here. I searched for Monte Carlo simulation on a search engine and came up with some 22,000 web pages. Most are very applied to a particular topic, although the topics range from economics to applied physics. Find one to which you can relate if you want to know more. One interesting note is that we can only hope that the pseudo-random number generator doesn't give us the exact same combination more than once in a particular simulation.

So I wrote some code that would generate a coalition from amongst the blocks in the input. It then determines which, if any, of the blocks are critical according to Banzhaf's definition, which means that they have power in that coalition. They get a point for that trial of the Monte Carlo simulation. After some number of trials, you divide the points that each block has accumulated by the number of trials and that gives you the second factor in the Banzhaf Power Index.

Banzhaf's definition of power was as follows. A given block has power in a given coalition if and only if the block, by leaving the coalition, can turn it from a winning coalition into a losing coalition. (Clearly, leaving a losing coalition does not affect the outcome, since there are no negative weights.) Thus if the current number of 'yea' votes is Y and it requires at least M votes to win, a block with B votes is critical if and only if

• that Banzhaf counts the block effect twice--squaring the (assessed) advantage--due to the two-stage process. In step 1, Banzhaf measures the way a state could affect the outcome by changing its block of votes. In step 2, Banzhaf measures the way an individual can affect a state's "choice."
• that Banzhaf ignores combinations with more than a simple majority.
• that Banzhaf should not assign critical status to more than one member of a majority at a time. The Shapley-Shubik method assigns power to only one member of the majority, and computes the probability of each voter being the one to put the candidate "over the top," over all permutations.

I don't think that Banzhaf ignores combinations with more than simple majority as much as he discounts the extra votes as being non-critical, then gives every voter within the block the opportunity to be the critical voter in that block, and identifies every block as a critical block that has enough votes to change the election. This strikes me as being nearly identical to Sickels' description of the Shapley-Shubik method (above). In fact, Banzhaf noted that his method and the Shapley-Shubik method

" ... yield substantially similar results for large numbers of voting units. Indeed, the differences between these two sets of calculations were at most a few percent."

The difference really only comes in to play when the election is a landslide (or at least is not close). Banzhaf does not assign critical status to anyone when the election is a landslide, while Shapley and Shubik do. I think that Banzhaf's definition is more correct, since power in a landslide is basically non-existent from an intuitive sense. I mean, should anyone be considered to be critical (i.e. to have power) in an election decided by 525-13 (e.g. the 1984 U.S. Presidential election)? Also, one can see why the difference is "at most a few percent," since by definition, only a few percent of coalitions form a landslide.

It would be relatively easy to modify my program (see below) to compute the Shapley-Shubik index, although I believe the program would not be quite as efficient because Shapley-Shubik only assigns power to the one district that puts the coalition over the majority. That means order of voting is important in each trial, and then every block is given the opportunity to be the "crucial" block. But this strategy would require generating many more coalitions, since now there are not only N coalitions, but also R orders in which that coalition can be achieved. And R is a big number for systems as large as the U.S. Electoral College. R = B! (B factorial), where B is the number of blocks. 51! is approximately 2.6 x 10^(66) -- yes, that's a 67-digit number. In Monte Carlo methods such as what I use to compute the solution for a system as large as the Electoral College, there is a minimum percentage of the possible output space you should sample (i.e. minimum number of trials). Even with Banzhaf's definition, I'm probably not sampling enough. And now I'm supposed to multiply the number of samples (and length of time) by a 67-digit number?!? No, thank you!

My code uses the brute-force method (i.e. counting the total number of coalitions and the number in which each block is critical) when the number of blocks is below a pre-defined constant. There's nothing magical about the number, but I do not recommend raising it high enough to try the brute-force method on a sample as large as the U.S. Electoral College (51 blocks). It may not finish in your lifetime. It should be possible to run the program on a few not-too-small samples for timing data, then pick an appropriate constant for your machine, using the fact that there are 2^n combinations of n objects, when each has a yes/no choice.

Of course, any time you present an analysis of this type, you really ought to compute the variance of your numbers. (For the non-mathematical, variance says how far away the answer could be, and implicitly assumes that you know what the probability distribution between the stated estimate and the possible values are. Hmmm, maybe that wasn't the best description for the non-mathematical either. Sigh.) What follows here is very much a "back-of-the-envelope" calculation, but this should give the average person some idea of the accuracy of the numbers in the outputs above without undertaking such heroic effort as looking in a math book. Gasp!

For the Monte Carlo approach, one expects the error to be bounded by 3v/(sqrt(N)), where N is the number of trials and v is the variance for each trial. N for the sample outputs I have above is 4.29 billion. I haven't actually calculated v, but it would go something like this. Variance is defined as the expected value of ( x - u )^2, where u is the mean. In this case, the mean is the probability for the particular block. Of course, these are unknown a priori. But they are bounded by 0<=u<=1. I think that in the worst case, we're looking at a variance for each trial of 1.0. That's a variance of no worse than 4.48e-05 for the probabilities computed for each block.

For Stirling's approximation, there are numerous variations. I used the one Banzhaf used, given above. The error in this approximation is bounded by 1/(12 * N). N here is the number of people in the block, so we're looking at numbers that range from around 450,000 to 29.76 million for the 1990 data, 226,000 to 16.78 million for the 1960 data. So, let's approximate all such numbers with 1/220000, or an error of around 4.55e-06. That is, the approximations using Stirling's approximation should be off by no more than that number, and actually are better for all the 1990 data, and larger states have more accurate values than smaller states.

Next, we plug this error in each approximation to a large-number factorial into the equation given above for probability of an individual being the deciding vote in the block. Recall (or scroll up and see) that that equation has three such factorials, all of which theoretically need to be approximated. In fact, Banzhaf plugged the approximation symbolically and then simplified. But note that the two factorials in the denominator are half the size of the factorial in the numerator. So the worst thing that could happen is an error that looks like

The upshot of all this is that I expect (unless the pseudo-random number generator did something really evil) that both factors in the power computed for each block have 4 significant figures (i.e. meaningful decimal places to begin the answer, not including consecutive zeros between the decimal point and the significant digits). In other words, I expect that if I run the simulation again (or if you run your own), the numbers will agree through four significant digits. But that's in the raw power computed. What I'm showing you (and what Banzhaf published) are ratios between the smallest computed power and the other blocks. That division by a rather small number has the potential to introduce error, although given that the highest ratio is only 3.345, it should introduce no more than 3.6e-03 amount of error by a change that does not affect the third decimal place (which is the fourth significant digit once the ratios are computed) when the answers are rounded as I have done here (and in my program, i.e. I don't look at more digits than I'm showing you here). So this could introduce a variation of three or four in the fourth significant digit. A variation that large is not likely, of course. I've been generous with the error estimates I'm giving here, so the real values are somewhat less and thus the variation is almost surely less than four in the fourth significant digit.

So I expect that another simulation will indeed give exactly the same numbers for the power ratios to within the three decimal places I show.

I would classify that as a successful test and I firmly believe that you won't see a variation of more than four in the last decimal place from the numbers I have here. You probably won't see a variation of more than one in the fourth decimal place. By all means, tell me if you do and I'll put it on this page. That should include any changes to improve the accuracy of Stirling's approximation or an increase in the number of samples. Obviously, if you decrease the number of samples or the accuracy of Stirling's approximation, then this claim would not apply.

Apparently, it also does not apply if you try to use each bit of the pseudo-random number as an independent variable, a change I introduced into the code in order to squeeze some more speed out of the computations. It did yield better speed (24:49 hours:minutes versus 38:46), but it changed some of the numbers in the third significant digit. Thus it has introduced some inaccuracy into the computations that might be problematic. I think the problem would be most severe for voting systems that just surpass the threshold for which the exact computations are done. I have not tested this, however. I have left both blocks of code in the C program, and you can use either one by compiling in the version you like. (There's a preprocessor directive you should define or undefine.) The default was at one time the faster, less accurate version, but is now the slower, more accurate version.

And if you've skipped down from the top, stop cheating!

Second, let me muse about things I might try differently if I were to do this again. Yeah, right!