Problem of the Month
(November 2015)

The U.S. presidential election is a year away, but the Electoral College is already in the news. This month we investigate power indices, measures of how much power voters have when they have different numbers of votes. There are two widely-known power indices, due to Banzahf and Shapley-Shubik.

For a given index and number of votes of each voter, it is fairly easy to compute the corresponding power indices. We only consider cases in which a simple majority is needed in any vote, and there are an odd number of total votes so that no ties are possible. For example, with 1 voter, regardless of how many votes he has, the voter has all the power. With 2 voters, the voter with the larger number of votes has all the power. With 3 voters, either one voter with the majority of votes has all the power, or the voters have equal power. (To avoid the fractions, we say the power indices in these two cases are 0, 0, 1 and 1, 1, 1.)

The number of different power indices with n voters, all of which have some power, 1, 0, 1, 1, 4, 14, 114, 2335, ... is sequence 3184 of the OEIS.

1. When are the power indices of the voters the same as the number of votes?

2. For a given number of voters n, consider the ratio of the power of the most and least powerful voter who has power. What is the largest and smallest possible ratio?

3. For a positive integer R, what is the smallest number of voters so that the ratio between the power of two of the voters is R?

4. What are the power indices with a small number of voters where each voter has a distinct amount of power?

5. If two voters decide to collude and lump their votes together, their total power might change. What is the largest and smallest ratio of their combined power when colluding to when not colluding?

6. For 3 voters, the possible power indices can be naturally represented by an equilateral triangle. Each vertex represents that voter having all the votes, and each other point in the triangle represents some mixture of votes using barycentric coordinates. Coloring each point with its power index gives the following picture:

What do the tetrahedral pictures (or sets of triangular slices) for 4 voters look like for the two methods?

7. If you are one of n voters with proportion p of the votes, what is your expected proportion of power? For 3 voters, the answer can be seen from the picture above: if p>1/2 then your expected proportion of power is 1, and if p<1/2 then your expected proportion of power is (0)(1–2p)/(1–p)+(1/3)p/(1–p)=p/(3–3p). What is your expected proportion of power for 4 or more voters?

8. What other interesting questions are there about power indices?


ANSWERS

Submissions were received from Rosalie Fay.

Throughout, vectors surrounded by parentheses are votes, and those without are power indices.

1.

We only list the power indices when all voters have some power. Equal power ratios are shown in red.

Known Equal Power Indices
VotesBanzhaf
Power Ratios
Shapley-Shubik
Power Ratios
(1)11
(1,1,1)1,1,11,1,1
(1,1,1,1,1)1,1,1,1,11,1,1,1,1
(1,1,1,2,2)1,1,1,2,24,4,4,9,9
(1,1,3,3,5)1,1,3,3,52,2,7,7,12
(1,2,2,3,3,4)1,2,2,3,3,41,2,2,3,3,4
(2,2,2,2,2,5)2,2,2,2,2,52,2,2,2,2,5
(1,1,1,1,1,1,1)1,1,1,1,1,1,11,1,1,1,1,1,1
(1,1,1,2,2,2,2)1,1,1,2,2,2,26,6,6,13,13,13,13
(1,1,1,2,2,4,4)1,1,1,2,2,4,412,12,12,26,26,61,61
(1,1,1,2,6,6,10)1,1,1,2,6,6,106,6,6,13,48,48,83
(1,1,3,3,5,8,8)1,1,3,3,5,8,83,3,10,10,17,31,31
(1,1,3,4,4,7,9)1,1,3,4,4,7,96,6,20,27,27,55,69
(1,2,4,4,6,7,7)1,2,4,4,6,7,76,13,27,27,41,48,48
(1,2,4,5,5,6,8)1,2,4,5,5,6,86,13,27,34,34,41,55
(1,3,3,4,6,6,8)1,3,3,4,6,6,86,20,20,27,41,41,55
(2,2,3,4,5,7,8)2,2,3,4,5,7,813,13,20,27,34,48,55
(2,2,4,4,4,6,9)2,2,4,4,4,6,913,13,27,27,27,41,62
(3,3,3,3,3,8,8)3,3,3,3,3,8,83,3,3,3,3,10,10
(3,3,4,5,5,6,7)3,3,4,5,5,6,718,18,25,32,32,39,46
(3,3,3,3,3,10,10)3,3,3,3,3,8,83,3,3,3,3,10,10

2.

The smallest possible ratio for n≥3 voters is 1 for both methods, when n is odd.

The largest possible ratio in power for n≥3 voters is 2n–1–1 for the Banzhaf Power Ratios.

Rosalie Fay conjectured the smallest possible ratio for the Banzhaf Power Ratios for n=4k voters is smaller than k2k+1 / (k+1)2k-1, and for n=4k+2 voters is smaller than k2k+3 / (k+1)2k-1.

Power Ratios of
Most to Least Powerful
 Banzhaf
Power Ratios
Shapley-Shubik
Power Ratios
nMinMaxMinMax
31111
43333
51716
67/3155/213
7131136
825/13
(RF)
63??
911271?
1091/51
(RF)
255??
1115111?
12301/181
(RF)
1023??

3.

Two Voters with Power Ratio R
with Smallest Number of Voters
RBanzhaf
Power Ratios
Shapley-Shubik
Power Ratios
11,1,11,1,1
21,1,1,2,21,2,2,3,3,4
1,1,1,1,2,4
1,1,3,6,6,13
1,3,3,5,8,10
2,2,2,6,9,9
2,2,4,4,7,11
31,1,1,31,1,1,3
41,1,1,3,3,41,1,1,1,2,4
1,1,4,4,4,16
1,2,2,3,3,4
51,1,3,3,51,3,3,5,8,10
1,5,5,5,7,7
61,1,1,2,2,61,1,1,1,6
2,2,7,7,12
71,1,1,1,71,5,5,5,7,7
2,2,2,5,5,14
81,1,4,4,5,7,8
1,3,3,4,6,6,8
1,2,3,3,6,7,8
1,1,1,1,7,8,8
1,2,4,5,5,6,8
1,1,3,3,5,8,8
1,2,2,2,7,7,8
1,1,1,8,8,11
1,3,3,5,8,10
91,1,1,7,7,9
1,3,3,5,7,9
3,3,5,5,5,9
1,2,3,4,5,6,9
101,1,2,3,5,6,10
1,2,3,3,4,6,10
1,3,3,4,4,5,10
1,1,1,2,6,6,10
1,2,2,4,5,5,10
1,1,1,1,1,10
111,1,3,5,5,11
3,3,3,3,5,11
1,1,1,8,8,11
121,2,2,3,3,4,12
1,1,1,3,4,4,12
1,2,2,3,4,6,12
131,1,3,3,3,131,1,3,6,6,13
141,1,1,2,2,2,141,1,1,3,5,5,14
151,1,1,1,1,151,1,1,1,1,1,15
2,2,2,2,30,30,37
3,3,10,17,45,45,87
3,3,38,38,38,45,45
3,7,24,24,45,45,52
3,10,31,31,38,45,52
3,17,17,24,24,45,80
4,4,4,11,11,11,60
4,11,25,25,39,46,60
4,11,11,11,46,60,67
6,6,13,13,41,41,90
161,1,1,1,1,15,16,16 (RF)1,1,4,4,4,16
171,5,7,9,11,11,17
1,1,1,1,15,15,17
1,3,7,7,11,13,17
1,1,7,7,9,15,17
1,3,5,5,11,15,17
1,3,3,3,13,15,17
?
181,4,6,6,6,11,11,18 (RF)?
191,7,7,9,9,9,19
1,3,5,7,9,13,19
1,1,3,3,13,13,19
1,1,5,5,11,13,19
1,5,5,9,9,11,19
?
201,1,7,7,8,8,9,20 (RF)?
211,7,7,7,7,9,21 (RF)?
221,1,6,6,6,7,9,22 (RF)?
231,5,5,5,7,9,23 (RF)?
241,1,1,1,7,8,8,24 (RF)?
251,1,1,7,7,7,25 (RF)?
261,4,4,4,4,5,5,26 (RF)?
271,1,3,5,5,5,27 (RF)?
281,1,1,3,4,4,4,28 (RF)?
291,1,3,3,3,3,29 (RF)?
301,1,1,2,2,2,2,30 (RF)?
311,1,1,1,1,1,31 (RF)?
321,1,1,1,1,1,31,32,32 (RF)?
331,1,1,1,1,31,31,33 (RF)?

4.

Smallest Known
Distinct Power Indicies
nBanzhaf
Power Ratios
Shapley-Shubik
Power Ratios
111
7(1,2,3,4,5,6,8) 1,2,3,4,5,6,9 (RF)
(1,2,3,4,5,7,9) 1,3,5,7,9,13,19 (RF)
(2,3,4,5,6,7,8) 3,5,7,9,11,13,15 (RF)
1,2,3,4,5,6,9
3,10,17,24,31,52,73
9,16,23,30,37,44,51

For Banzhaf power indices, Rosalie Fay found 267 cases for 8 voters, and 52,410 cases for 9 voters!

Rosalie Fay also pointed out that for 5 voters with (1,2,3,4,5) votes and 9 votes necessary to pass a measure, then the Banzhaf power indices are 1,3,5,7,9.

5.

Smallest and Largest Known Ratios when Colluding
 Banzhaf
Power Ratios
Shapley-Shubik
Power Ratios
nMinMaxMinMax
3 1
(1,1,3)→(1,4)
0,0,1→0,1
3/2
(1,1,1)→(1,2)
1,1,1→0,1
1
(1,1,3)→(1,4)
0,0,1→0,1
3/2
(1,1,1)→(1,2)
1,1,1→0,1
4 1
(1,1,1,4)→(1,1,5)
0,0,0,1→0,0,1
3/2
(1,2,2,2)→(1,2,4)
0,1,1,1→0,0,1
1
(1,1,1,4)→(1,1,5)
0,0,0,1→0,0,1
3/2
(1,2,2,2)→(1,2,4)
0,1,1,1→0,0,1
5 11/12
(1,1,1,1,3)→(1,1,2,3)
1,1,1,1,7→1,1,1,3
7/4
(1,1,1,2,2)→(1,1,1,4)
1,1,1,2,2→0,0,0,1
5/6
(1,1,1,1,3)→(1,1,2,3)
1,1,1,1,6→1,1,1,3
5/3
(1,1,1,2,2)→(1,1,1,4)
4,4,4,9,9→0,0,0,1
6 10/11
(1,1,1,1,1,4)→(1,1,1,2,4)
1,1,1,1,1,15→1,1,1,1,7
7/4
(1,2,2,2,4,4)→(1,2,2,2,8)
0,1,1,1,2,2→0,0,0,0,1
3/4
(1,1,1,1,1,4)→(1,1,1,2,4)
1,1,1,1,1,10→1,1,1,1,6
5/3
(1,1,1,1,2,3)→(1,1,1,1,5)
1,1,1,1,2,4→0,0,0,0,1
7 7/8
(2,2,2,2,3,3,9)→(2,2,2,2,6,9)
3,3,3,3,5,5,27→3,3,3,3,5,11
31/16
(1,1,1,1,1,3,3)→(1,1,1,1,1,6)
3,3,3,3,3,8,8→0,0,0,0,0,1
7/10
(1,1,1,1,1,1,6)→(1,1,1,1,2,6)
1,1,1,1,1,1,15→1,1,1,1,1,10
7/4
(1,1,1,1,1,3,3)→(1,1,1,1,1,6)
3,3,3,3,3,10,10→0,0,0,0,0,1
8 ? ? ? ?


If you can extend any of these results, please e-mail me. Click here to go back to Math Magic. Last updated 11/1/15.