Banzhaf Power Index

The Banzhaf Power Index was introduced by John F. Banzhaf III for the purpose of analyzing block voting systems, such as the U.S. Electoral College that elects the president. Banzhaf's method and previous methods are based on probabilistic analysis of the individual voters in a block voting system.

Egads! you may be saying, if you don't have an interest in math. Well, although I include all the math, I also wrote this page to be accessible to those without a strong math background. I also wrote it to amuse myself, and I hope it amuses you too. I have gotten some positive feedback, so you might go ahead and take a chance. Live a little!

If you don't understand how the Electoral College works, I suggest reading a little more about it now. The National Archives and Records Administration Federal Register maintains a complete page on the U.S. Electoral College. Click on the Frequently Asked Questions image, then look for the "What is the Electoral College?" link in the menu just under the eagle.

The methods of Banzhaf and others before him were published in various law review journals, notably the Villanova Law Review, Winter 1968 [1]. I learned about Banzhaf's work in an article by Ian Stewart in the July 1995 issue of Scientific American [6] and recursively searched for the other articles. Here is the list of related references of which I know.


Outline

There is a separate page of references.


The Banzhaf Power Index

The basic principle upon which Banzhaf rested his method is that voting power is derived from your ability to change---or more precisely, probability of changing---the outcome of the election with your vote. Note that in a block voting system, this is a little hard to think about because you don't directly vote for a candidate. Thus Banzhaf's method first computes the probability that a citizen's vote will change the block's "decision," then determines the probability that the block's votes will change the outcome of the election.

Note:    The Electoral College system does not actually require the electors to cast their electoral votes for the candidate for whom the popular votes were cast. Aside from showing the absurdity of the system, this failure also confounds any attempt at analysis. Such things do happen, although rarely. On the NARA's Electoral College site, see the 1988, 1976, and 1972 elections, to name a few recent examples.

Mathematics of the Banzhaf Power Index

Thus there are two numbers that we need to compute the Banzhaf Power Index, the probability of an individual changing the result of a block's decision, and the probability of the block changing the election result. Banzhaf uses straightforward combinatorial analysis to arrive at the probabilities for each block. He claims (and I quote):

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

æ
ç
è
n
p
ö
÷
ø
= n !
p ! ( n - p ) !

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

Y - B < M

There are other definitions of power, discussed below under Criticisms of the Banzhaf Power Index

Finally, the probability that a citizen voter will change the outcome of the election with his/her vote is the product of the two probabilities above (i.e. the probability that both the individual changes the block's decision and the block's votes change the election). According to the laws of probability, the probability that two independent events happen at the same time is the product of the probability that each happens. So we multiply the two numbers together for each block to get the power attributed to each voter within the block. This is the Banzhaf Power Index.


Banzhaf also analyzed two commonly suggested alternatives to the Electoral College:

Banzhaf's analysis showed that the block voting system (i.e. the Electoral College) heavily favors residents of the larger blocks, while both alternate plans favor residents of smaller blocks. Banzhaf also mentioned that a direct popular election would give every voter equal power.


Banzhaf Power Index for Smaller Assemblies

If the number of blocks in the system is relatively small, then the Monte Carlo approach is not necessary. That is, you can simply generate all possible coalitions and not worry about sampling the space of possible outcomes. This is somewhat easier conceptually, and thus Stewart's description
[6] emphasizes counting more than my description above with the Monte Carlo approach in mind.

Stewart then assigns power to individual voters by simply dividing the block's power by the number of residents. Stewart also gives the example of Tompkins County, NY in 1982, which managed to create a weighted system with power per capita for each district that was within 1.8% of the others. (The table is below, but read the paragraphs between here and the table first!)

BUT WAIT!

you should be saying. Doesn't that assume that power within a block has an inverse linear relationship with the population? In other words, don't you want the power divided by the square-root-of-population to be equal amongst the districts, not power per capita (power divided by population)?

OK, maybe you weren't saying it exactly like that....

But the answer is actually 'Yes.' This is what Stewart left out of his article. Apparently, the election board of Tompkins County, New York also left out this part from their distribution of votes among blocks. Where's John Allen Paulos (author of Innumeracy - Mathematical Illiteracy and Its Consequences) when you need him?

So here's the table. Note that the numbers in the fifth column are nearly the same for each district. Stewart says that this implies that each voter in the entire election has nearly the same power. But look at the last column. This gives the ratios of power-divided-by-the-square-root-of-the-population. (That is, for each block, divide column four by the square root of column two. Then for each block, divide that number by the smallest of such numbers for each block.) Since the square-root of 2 over p in the Banzhaf Power Index cancels out in the ratios, these numbers are equal to the Banzhaf Power Ratios of each district. That is, divide the Banzhaf Power Index for each district by the Power Index for the smallest district and you get a measure of relative strength.

Note that the Banzhaf Power Ratios are not all that close to each other. As Banzhaf noted in general, the voters in larger districts have more power than those in smaller districts. For example, the voters of the district of Lansing have approximately 1.33 times the power of voters in the district of Dryden West. The one exception is between the two districts with an equal number of votes. Then the voters in the district with 10 extra people have slightly less power, which makes sense.

Block              Pop.  Weight   Power  Power/Pop  Norm. Power/Sqrt(Pop) =
                         (Votes)                      Banzhaf Power Ratio
--------           ----  -------  -----  ---------  -----------------------
Lansing            8317     404    4734      0.569                 1.335714
Dryden_East        7604     333    4402      0.579                 1.298965
Enfield_Newfield   6776     306    3934      0.581                 1.229748
Ithaca_3           6550     298    3806      0.581                 1.210087
Ithaca_4           6002     274    3474      0.579                 1.153852
Ithaca_SE          5932     270    3418      0.576                 1.141931
Ithaca_1           5630     261    3218      0.572                 1.103571
Ithaca_2           5378     246    3094      0.575                 1.085621
Ithaca_NE          5235     241    3022      0.577                 1.074743
Groton             5213     240    3006      0.577                 1.071306
Caroline_Danby     5203     240    3006      0.578                 1.072335
Ithaca_5           5172     238    2978      0.576                 1.065526
Ithaca_West        4855     224    2798      0.576                 1.033288
Ulysses            4666     214    2666      0.571                 1.004283
Dryden_West        4552     210    2622      0.576                 1.000000


Criticisms of the Banzhaf Power Index

Robert J. Sickels objected to Banzhaf's method, preferring a previously published method known as the Shapley-Shubik method. Sickels claims

Responses to the Criticisms

I'm now going to attempt to respond to Sickels on behalf of Banzhaf, in part by quoting Banzhaf. First, just because the Banzhaf method has two stages is not a reason to criticize it. After all, a block voting system is inherently two-stage. The block effect is not counted twice in Banzhaf's equations; it is one of two factors. Second, I don't see what is wrong with assigning critical status to multiple members of a majority coalition. It is true that if the coalition has a majority by, say, 18-15, then anyone with at least two votes is critical to the coalition holding. Sickels appears to want to define "critical" as "the one who happens to place the coalition over a simple majority," and give every one a chance to be that person, while Banzhaf defines "critical" as "anyone who holds enough votes to change the coalition from a winner to a loser, or vice-versa." I much prefer Banzhaf's definition.

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!


Alternatives and Recent Work

Neither of these two indices (Banzhaf and Shapley-Shubik) were the only measures that existed in the 1960s, and there have been extensions and alternatives proposed since then. See the
references for a listing of a few recent articles. Most of the recent work is in the field of Game Theory, which is not a subject with which I am intimately familiar. This does mean that the recent articles are very mathematical and academic, whereas Stewart's introduction is very accessible to those without a mathematical background. Of course, Stewart's article is incomplete in its description and very misleading about what to do.

Also, the discussion up to this point has assumed that a winning coalition requires only a simple majority. However, voting assemblies sometimes require more than a simple majority in order to pass a measure. The Banzhaf Power Index can be adjusted to this case quite easily by simply changing the number of votes required to form a winning coalition. All the other mechanics of the computations remain the same, as does the definition of "critical." I have modified my code to allow the number of votes required to form a winning coalition to be input by the user. Thanks to Elaine Garcia for pointing this case out to me. Even if it was because she needed the code to compute that case.... :-)


Implementation of Banzhaf Power Index

I have written a C program to compute the Banzhaf Power Index for any size assembly. It takes a description of the assembly and the respective populations of the blocks, and outputs the Banzhaf Power Index for each. The input format is quite simple. The first line of the input contains a single number that gives the number of voting blocks. Following this line is one line for each voting block, with three fields: the name of the block, the population of the block, and the number of votes the block has. The files test.dat and TompkinsCountyNY.dat are from the Stewart article, while usa.dat corresponds to the 1990 census configuration of the Electoral College and usa1960.dat to the 1960 Electoral College.

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.

For "large" numbers of blocks, the program uses the Monte Carlo method, which means that the banzhafNextCoalition() function in banzhaf.c has an if statement that basically divides it into two different functions. For either "large" or "small" numbers of blocks, the equations listed above under Mathematics of the Banzhaf Power Index for the power of each voter to change the block's decision are used to compute that factor. The two factors are put together in banzhafComputeRatios().

If you find a bug in my code or have your own implementation, please send me mail. Feel free to use the code here to help get you started. Please give credit to me if you do.


Results of my Implementation

I ran my implementation on the 1990 U.S. census distribution of the Electoral College. I used 4.29 billion samples in the Monte Carlo estimation of the probability for the states to be critical by Banzhaf's definition. The program took a little under 25 hours to complete. Here are the results.

StatePopulationEV PR
  
StatePopulationEV PR
CA 29760021 54 3.344 LA 4219973 9 1.308
NY 17990455 33 2.394 MS 2573216 7 1.302
TX 16986510 32 2.384 SC 3486703 8 1.278
FL 12937926 25 2.108 IA 2776755 7 1.253
PA 11881643 23 2.018 AZ 3665228 8 1.247
IL 11430602 22 1.965 KY 3685296 8 1.243
OH 10847115 21 1.923 OR 2842321 7 1.239
MI 9295297 18 1.775 NM 1515069 5 1.211
NC 6628637 14 1.629 AK 550043 3 1.205
NJ 7730188 15 1.617 VT 562758 3 1.192
VA 6187358 13 1.564 RI 1003464 4 1.190
GA 6478216 13 1.529 ID 1006749 4 1.188
IN 5544159 12 1.524 NE 1578385 5 1.186
WA 4866692 11 1.490 AR 2350725 6 1.167
TN 4877185 11 1.489 DC 606900 3 1.148
WI 4891769 11 1.486 KS 2477574 6 1.137
MA 6016425 12 1.463 UT 1722850 5 1.135
MO 5117073 11 1.453 HI 1108229 4 1.132
MN 4375099 10 1.428 NH 1109252 4 1.132
MD 4781468 10 1.366 ND 638800 3 1.118
OK 3145585 8 1.346 WV 1793477 5 1.113
AL 4040587 9 1.337 DE 666168 3 1.095
WY 453588 3 1.327 NV 1201833 4 1.087
CT 3287116 8 1.317 ME 1227928 4 1.076
CO 3294394 8 1.315 SD 696004 3 1.071
MT 799065 3 1.000
The states (plus Washington, DC, which has Electoral Votes of its own) are listed by two-letter postal abbreviations. Population is for 1990 and from the 1992 Information Please Almanac. The number of Electoral Votes (EV) is according to the 1990 redistribution of votes. PR is the power ratio, as defined by Banzhaf. This is the strength of each voter in the given state relative to the strength of the voters with the weakest voting strength. Again, as defined by Banzhaf and demonstrated above, voting strength is the probability of changing the outcome of the election with your vote. With the current distribution and latest population, a voter in Montana is the least likely to change outcome of the election, and thus the Power Ratio for Montana is 1.000. A voter in California is 3.344 times more likely to change the outcome of the election. Note that the actual probabilities (not given) are miniscule in either case (not surprising given that there are some 260 million U.S. citizens, though I don't know how many of those are eligible or registered to vote), but this is still a good measure of a priori voting strength.

I have run the program on the 1964 data (1960 census data) for which Banzhaf published figures. You can click on the file of results from that simulation below.

The numbers do not agree exactly; both are probably slightly off from the "true" answers according to the definitions above. Banzhaf's original numbers will be slightly off because of the approximation he made so as to avoid lengthy computational processing in the 1960s (a wise decision). Maybe someday I will update this page with a description of what he did; I have spoken to him about this. My numbers will be off because Monte Carlo numbers are probably always slightly off, and I'm not really able to generate enough samples with the standard numerical precision that is supported in this implementation. But repeat runs were really, really close, so I doubt the errors are large.

Some details, for the geeks among you: I computed 4.29 billion coalitions using an SGI Onyx^2 with an R10000 processor. That took 24 hours, 49 minutes to run on the 1990 data.

Let me take this opportunity to climb on my soapbox for a moment and plead with everyone (especially in the U.S., where voter turnout is so low) to vote in each and every election. It is never difficult to register (not in the U.S., at least), and it does matter to you who is elected, whether or not you can see it in your daily life. It may seem from these numbers that it doesn't matter, but it does. Also note that if you do not vote, you have ZERO voting strength. Don't throw away what you could use to affect your government.

That's enough of the soapbox for today. :-)





Things Available for Download


You Mean There's More?!?

There's always more! -my Mom

Ewww!!! And It's Mathematical Analysis, Too!

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

1 + 1
12 N

æ
ç
è
1
2
+ 1
6 N
ö
÷
ø
æ
ç
è
1
2
+ 1
6 N
ö
÷
ø
which after a little algebraic manipulation and some eyeballing, I'll claim is bounded by 4. (The numerator and denominator are both quadratic in N because of the constant terms and quadratic denominator of the fraction nested within the denominator of the "outer" fraction. Then apply L'Hôpital's rule . Rinse. Repeat.) So I'm guessing that even in the worst case for the samples I've got, the error is something less than 1.82e-05.

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.


Several days later....
Now, I actually did write that claim on this page and then I reran the simulations. (Of course, I reran them immediately, so I could only have been a fool for a short amount of time. :-) Fortunately, however, my calculations were quite accurate.) For the 1960 data, all but four of the 51 blocks had the same power ratio to within four significant figures; the other four were off by one in the fourth significant digit. For the 1990 data, all but six of the 51 blocks had the same power ratio to within four significant figures; the other six were off by one in the fourth significant digit. Some of those ten that were off were high and some were low. I don't know how close they were in the two trials. I did notice that those that were off tended to be larger blocks; the difference in the two trials could be due to a small change in the smallest block's raw power computed.

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.


Left as an Exercise to the Reader

First, let me offer you my profound congratulations and thanks for the ego-stroking if you've actually read this entire page. As long as you're in this far, send me mail and tell me about it!

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!

  1. Using the Shapley-Shubik definition of power

    This is by far the most likely alternative to make any difference in the computed numbers, and thus (I think) the most interesting of the ideas I list here. I gave the definition in the section on criticisms to Banzhaf's definition. I noted that Banzhaf said the two will yield basically the same results and gave at least one intuitive reason why. And, from the way I understand what Banzhaf said, Shapley helped him prepare his numbers, so I assume that Shapley did not balk at the claim that the two methods yielded similar results. But I can only assume.... At any rate, you could make the change. I strongly suggest that you decrease the sample size and implement a parallelization scheme if you are going to do this. Read the note about number of samples you would need under Responses to the Criticisms and the idea for parallelizing the code cleanly in item 3 below.

  2. Increasing sample size

    I'm still only sampling a very small percentage of the possible outcomes for coalitions. There are 2.2518 x 1015 possible, I only sample 4.29 x 1012 of them, or less than 0.2%. That's a much smaller percentage than would normally be used in a Monte Carlo simulation, from what I read in my glancing through the literature looking for the formula for variance. But more would require some fancier handling of the arithmetic and/or parallelizing the code, I believe.

  3. Parallelizing the code

    I also thought about splitting the sample space up by allowing the user to enter a prefix to be prepended to the random bit stream. Using three prefix bits, for example, would also offer easy eight-way parallelism of the code (8=23) by simply running eight processes with the eight possible three-bit prefixes. That might make it more tolerable to generate more samples.

    Assuming that each of the subprocesses uses the same (large) number of samples, you could simply average the resulting power ratios from each process to get the final values. That assumes that the raw power computed for the smallest block is always the same, and that each process decides that the same block has the least power. With large sample sizes in each process, that seems rather likely. If you don't want to make that assumption, then have the program print out the power indices, which can always be averaged.

    The nice thing about the prefix strategy for parallelization is that it guarantees that no two processes will create the same coalition, since they are guaranteed to have a difference in at least one of the first three assignments of blocks to coalitions (in or out). Of course, it can not guarantee that a single process will not generate a coalition twice.

  4. Improving Stirling's approximation

    It might be interesting to see how a better version of Stirling's approximation would affect the final computed power ratios. I've already said that I expect the answers not to change by more than four in the fourth significant digit, though.

  5. Increasing the precision

    I can't see that more decimal places would mean anything, but arbitrary-precision libraries are available on the 'net. I used double-precision.

I would like to hear of anything interesting that you do with this code or if you link to this page. Please send me email.


Other Pages


Acknowledgements

My thanks to Ofer Melnik of Brandeis University who noted the missing numbers from my original code, which prompted me to re-read the original sources and get it right. I also want to thank the other people who have taken the time to comment on this page (specifically, Prof. Chase and his math students at Messiah College, Elaine and Jayne Garcia who did some analysis of the European Union with my code, and especially Melissa the math major from Penn State - but I already knew that I rocked!). It's nice to know that people are reading it, enjoying it, and--gasp--maybe even learning a little.


Mark Livingston
Dept. of Computer Science
Univ. of North Carolina

Last modified: 14 April 2003
This document is: <http://www.cs.unc.edu/~livingst/Banzhaf/index.html>