Voting power (2): computation

Naive implementation of Banzhaf power indices

As we saw in the previous post, computation of the power indices can become unwieldy as the number of voters increases. However, we can very simply write a program to compute the Banzhaf power indices simply by looping over all subsets of the weights:

 1def banzhaf1(q,w):
 2    n = len(w)
 3    inds = [0]*n
 4    P = [[]]             # these next three lines creates the powerset of 0,1,...,(n-1)
 5    for i in range(n):
 6        P += [p+[i] for p in P]
 7    for S in P[1:]:
 8        T = [w[s] for s in S]
 9        if sum(T) >= q:
10            for s in S:
11                T = [t for t in S if t != s]
12                if sum(w[j] for j in T)<q:
13                    inds[s]+=1
14    return(inds)

And we can test it:

1In [1]: q = 51; w = [49,49,2]
2
3In [2]: banzhaf(q,w)
4Out[2]: [2, 2, 2]
5
6In [3]: banzhaf(12,[4,4,4,2,2,1])
7Out[3]: [10, 10, 10, 6, 6, 0

The origin of the Banzhaf power indices was when John Banzhaf explored the fairness of a local voting system where six bodies had votes 9, 9, 7, 3, 1, 1 and a majority of 16 was required to pass any motion:

1In [4]: banzhaf(16,[9,9,7,3,1,1])
2Out[4]: [16, 16, 16, 0, 0, 0]

This result led Banzhaf to campaign against this system as being manifestly unfair.

Implementation using polynomials

In 1976, the eminent mathematical political theorist Steven Brams, along with Paul Affuso, in an article "Power and Size: A New Paradox" (in the Journal of Theory and Decision) showed how generating functions could be used effectively to compute the Banzhaf power indices.

For example, suppose we have

\[ [6; 4,3,2,2] \]

and we wish to determine the power of the first voter. We consider the formal polynomial

\[ q_1(x) = (1+x^3)(1+x^2)(1+x^2) = 1 + 2x^2 + x^3 + x^4 + 2x^5 + x^7. \]

The coefficient of \(x^j\) is the number of ways all the other voters can combine to form a weight sum equal to \(j\). For example, there are two ways voters can join to create a sum of 5: voters 2 and 3, or voters 2 and 4. But there is only one way to create a sum of 4: with voters 3 and 4.

Then the number of ways in which voter 1 will be necessary can be found by adding all the coefficients of \(x^{6-4}\) to \(x^5\). This gives a value p(1) = 6. In general, define

\[ q_i(x) = \prod_{j\ne i}(1-x^{w_j}) = a_0 + a_1x + a_2x^2 +\cdots + a_kx^k. \]

Then it is easily shown that

\[ p(i) = \sum_{j=q-w_i}^{q-1}a_j. \]

As another example, suppose we use this method to compute Luxembourg's power in the EEC:

\[ q_6(x) = (1+x^4)^3(1+x^2)^2 = 1 + 2x^2 + 4x^4 + 6x^6 + 6x^8 + 6x^{10} + 4x^{12} + 2x^{14} + x^{16} \]

and we find \(b(6)\) by adding the coefficients of \(x^{12-w_6}\) to \(x^{12-1}\), which produces zero.

This can be readily implemented in Python, using the sympy library for symbolic computation.

 1import sympy as sy
 2
 3def banzhaf(q,w):
 4    sy.var('x')
 5    n = len(w)
 6    inds = []
 7    for i in range(n):
 8        p = 1
 9        for j in range(i):
10            p *= (1+x**w[j])
11        for j in range(i+1,n):
12            p *= (1+x**w[j])
13        p = p.expand()
14        inds += [sum(p.coeff(x,k) for k in range(q-w[i],q))]
15    return(inds)

Computation of Shapley-Shubik index

The use of permutations will clearly be too unwieldy. Even for say 15 voters, there are \(2^{15}=32768\) subsets, but \(1,307,674,368,000\) permutations, which is already too big for enumeration (except possibly on a very fast machine, or in parallel, or using a clever algorithm).

The use of polynomials for computations in fact precedes the work of Brams and Affuso; it was published by Irwin Mann and Lloyd Shapley in 1962, in a "memorandum" called Values of Large Games IV: Evaluating the Electoral College Exactly which happily you can find as a PDF file here.

Building on some previous work, they showed that the Shapley-Shubik index corresponding to voter \(i\), could be defined as

\[ \Phi_i=\sum_{k=0}^{n-1}\frac{k!(n-1-k)!}{n!}\sum_{j=q-w_i}^{q-1}c_{jk} \]

where \(c_{jk}\) is the coefficient of \(x^jy^k\) in the expansion of

\[ f_i(x,y)=\prod_{m\ne i}(1+x^{w_m}y). \]

This of course has many similarities to the polynomial definition of the Banzhaf power index, and can be computed similarly:

 1def shapley(q,w):
 2    sy.var('x,y')
 3    n = len(w)
 4    inds = []
 5    for i in range(n):
 6        p = 1
 7        for j in range(i):
 8            p *= (1+y*x**w[j])
 9        for j in range(i+1,n):
10            p *= (1+y*x**w[j])
11        p = p.expand()
12        B = []
13        for j in range(n):
14            pj = p.coeff(y,j)
15            B += [sum(pj.coeff(x,k) for k in range(q-w[i],q))]
16        inds += [sum(sy.Float(B[j]/sy.binomial(n,j)/(n-j)) for j in range(n))]
17    return(inds)

A few simple examples

The Australian (federal) Senate consists of 76 members, of which a simple majority is required to pass a bill. It is unusual for the current elected government (which will have a majority in the lower house: the House of Representatives) also to have a majority in the Senate. Thus it is quite possible for a party with small numbers to wield significant power.

A case in point is that of the "Australian Democrats" party, founded in 1977 by a disaffected ex-Liberal politician called Don Chipp, with the uniquely Australian slogan "Keep the Bastards Honest". For nearly two decades they were a vital force in Australian politics; they have pretty much lost all power they once had, although the party still exists.

Here's a little table showing the Senate composition in various years:

This composition in 1985 can be described as

\[ [39; 34,33,7,1,1]. \]

And now:

1In [1]: b = banzhaf(39,[34,33,7,1,1])
2        [sy.N(x/sum(b),4) for x in b]
3
4Out[1]: [0.3333, 0.3333, 0.3333, 0, 0]
5
6In [2]: s = shapley(39,[34,33,7,1,1])
7        [sy.N(x,4) for x in s]
8
9Out[2]: [0.3333, 0.3333, 0.3333, 0, 0]

Here we see that both power indices give the same result: that the Democrats had equal power in the Senate to the two major parties, and the other two senate members had no power at all.

In 2000, we have \([39;35,29,9,1,1,1]\) and:

1In [1]: b = banzhaf(39,[31,29,9,1,1,1])
2        [sy.N(x/sum(b),4) for x in b]
3
4Out[1]: [0.34, 0.3, 0.3, 0.02, 0.02, 0.02]
5
6In [2]: s = shapley(39,[31,29,9,1,1,1])
7        [sy.N(x,4) for x in s]
8
9Out[2]: [0.35, 0.3, 0.3, 0.01667, 0.01667, 0.01667]

We see here that the two power indices give two slightly different results, but in each case the power of the Democrats was equal to that of the opposition, and this time the parties with single members had real (if small) power.

By 2020 the Democrats have disappeared as a political force, their place being more-or-less taken (at least numerically) by the Greens:

1In [1]: b = banzhaf(39,[36,26,9,2,1,1,1]
2        [sy.N(x/sum(b),4) for x in b]
3
4Out[1]: [0.5306, 0.1224, 0.1224, 0.102, 0.04082, 0.04082, 0.04082]
5
6In [2]: s = shapley(39,[36,26,9,2,1,1,1]
7        [sy.N(x,4) for x in s]
8
9Out[2]: [0.5191, 0.1357, 0.1357, 0.1024, 0.03571, 0.03571, 0.03571]

This shows a very different sort of power balance to previously: the Government has much more power in the Senate, partly to having close to a majority and partly because of the fracturing of other Senate members through a host of smaller parties. Note that the Greens, while having more members that the Democrats did in 1985, have far less power. Note also that One Nation, while only having twice as many members as the singleton parties, has far more power: 2.5 times by Banzhaf, 2.8667 times by Shapley-Shubik.