Voting power (5): The Deegan-Packel and Holler power indices

We have explored the Banzhaf and Shapley-Shubik power indices, which both consider the ways in which any voter can be pivotal, or critical, or necessary, to a winning coalition.

A more recent power index, which takes a different approach, was defined by Deegan and Packel in 1976, and considers only minimal winning coalitions. A winning coalition \(S\) is minimal if every member of \(S\) is critical to it, or alternatively, that \(S\) does not contain any winning coalition as a proper subset. It is easy to see that these are equivalent, for if \(i\in S\) was not critical, then \(S-\{i\}\) would be a winning coalition which is a proper subset.

Given \(N=\{1,2,\ldots,n\}\), let \(W\subset 2^N\) be the set of all minimal winning coalitions, and let \(W_i\subset W\) be those that contain the voter \(i\). Then we define \[ DP_i=\sum_{S\in W_i}\frac{1}{|S|} \] where \(|S|\) is the cardinality of \(S\).

For example, consider the voting game \[ [16;10,9,6,5] \] Using the indicies 1 to 4 for the voters, the minimal winning coalitions are \[ \{1,2\},\{1,3\},\{2,3,4\}. \] and hence

\begin{align*} DP_1 &= \frac{1}{2}+\frac{1}{2} = 1 \\cr DP_2 &= \frac{1}{2}+\frac{1}{3} = \frac{5}{6} \\cr DP_3 &= \frac{1}{2}+\frac{1}{3} = \frac{5}{6} \\cr DP_4 &= \frac{1}{3} \end{align*}

and these values can be normalized so that their sum is unity: \[ [1/3,5/18,5/18,1/9]\approx [0.3333, 0.2778,0.2778, 0.1111]. \] In comparison, both the Banzhaf and Shapley-Shubik indices return \[ [0.4167, 0.25, 0.25, 0.0833]. \]

Allied to the Deegan-Packel index is Holler's public-good index, also called the Holler-Packel index, defined as \[ H_i=\frac{|W_i|}{\sum_{j\in N}|W_j|}. \] In other words, this index first counts the number of minimal wining coalitions that contain \(i\), and then normalises those values for the sum to be unity.

In the example above, we have voters 1, 2, 3 and 4 being members of 2, 2, 2, 1 minimal winning coalitions respectively, and so the power indices are

\[ [2/7, 2/7, 2/7, 1/7] \approx [0.2857,0.2857,0.2857,0.1429]. \]

Implementation (1): Python

We can implement the Deegan-Packel in Python, either by using itertools, or simply rolling our own little functions:

 1def all_subsets(X):
 2    T = [[]]
 3    for x in X:
 4        T += [t+[x] for t in T]
 5    return(T)
 6
 7def is_subset(A,B):
 8    out = True
 9    for a in A:
10        if B.count(a) == 0:
11            out = False
12            break
13    return(out)
14
15def mwc(q,S,T):
16    if len(T) == 0:
17        return(S)
18    else:
19        if sum(T[0]) >= q:
20            S += [T[0]]
21            temp = T.copy()
22            for t in temp:
23                if is_subset(T[0],t):
24                    temp.remove(t)
25            return(mwc(q,S,temp))
26        else:
27            return(mwc(q,S,T[1:]))

1def prod(A):
2    m = len(A)
3    n = len(A[0])
4    p = 1
5    for i in range(m):
6        for j in range(n):
7            p *= A[i][j]
8    return(p)

Of the three functions above, the first simply returns all subsets (as lists); the second tests whether one list is a subset of another (treating both as sets), and the final routine returns all minimal winning coalitions using an elementary recursion. The function starts off considering all subsets of the set of weights, and goes through the list until it finds one whose sum is at least equal to the quota. Then it removes all other subsets which are supersets of the found one. The calls the routine on this smaller list.

For example:

1>>> wts = [10,9,6,5]
2>>> T = all_subsets(wts)[1:]
3>>> q = 16
4>>> mwc(q,[],T)
5
6[[10, 9], [10, 6], [9, 6, 5]]

It is an easy matter now to obtain the Deegan-Packel indices:

1def dpi(q,wts):
2    m = mwc(q,[],all_subsets(wts)[1:])
3    dp = []
4    for w in wts:
5        d = 0
6        for x in m:
7            d += x.count(w)/len(x)
8        dp += [d]
9    return(dp)

And as an example:

1>>> wts = [10,9,6,5]
2>>> q = 16
3>>> dpi(q,wts)
4
5[1.0, 0.8333333333333333, 0.8333333333333333, 0.3333333333333333]

and of course these can be normalized so that their sum is unity.

Implementation (2): Julia

Now we'll use Julia, and its Combinatorics library. Because Julia implements JIT compiling, its speed is generally faster than that of Python.

Just to be different, we'll develop two functions, one which first produces all winning coalitions, and the second which winnows that set to just the minimal winning coalitions:

 1using Combinatorics
 2
 3function wcs(q,w)
 4    S = powerset(w)
 5    out = []
 6    for s in S
 7        if sum(s) >= q
 8            append!(out,[s])
 9        end
10    end
11    return(out)
12end
13
14function mwc(q,out,wc)
15    if isempty(wc)
16        return(out)
17    else
18        f = wc[1]
19        popfirst!(wc)
20        temp = []   # temp finds all supersets of f = wc[1]
21        for w in wc
22            if issubset(f,w)
23                append!(temp,[w])
24            end
25        end
26        return(mwc(q,append!(out,[f]),setdiff(wc,temp)))
27    end
28end

Now we can try it out:

 1julia> q = 16;
 2julia> w = [10,9,6,5];
 3julia> cs = wcs(q,w)
 4
 57-element Array{Any,1}:
 6 [10, 9]
 7 [10, 6]
 8 [10, 9, 6]
 9 [10, 9, 5]
10 [10, 6, 5]
11 [9, 6, 5]
12 [10, 9, 6, 5]
13
14julia> mwc(q,[],cs)
15
163-element Array{Any,1}:
17 [10, 9]
18 [10, 6]
19 [9, 6, 5]

Repeated elements

Although both Julia and Python work with multisets, this becomes tricky in terms of the power indices. A simple expedient is to change repeated indices by small amounts so that they are all different, but that the sum will not affect any quota. If we have for example four indices which are the same, we can add 0.1, 0.2, 0.3 to three of them.

So we consider the example

\[ [30;28,16,5,4,3,3] \]

given as an example of a polynomial method in the article "Computation of several power indices by generating functions" by J. M. Alonso-Meijide et al; you can find the article on Science Direct.

So:

 1julia> q = 30;
 2julia> w = [28,16,5,4,3.1,3];
 3julia> cs = wcs(q,w);
 4julia> ms = mwc(q,[],cs)
 5
 66-element Array{Any,1}:
 7 [28.0, 16.0]
 8 [28.0, 5.0]
 9 [28.0, 4.0]
10 [28.0, 3.1]
11 [28.0, 3.0]
12 [16.0, 5.0, 4.0, 3.1, 3.0]

From here it's an easy matter to compute the Deegan-Packel power indices:

 1julia> dp = []
 2       for i = 1:6
 3           x = 0//1
 4           for m in mw
 5               x = x + count(j -> j == w[i],m)//length(m)
 6           end
 7           append!(dp, [x])
 8       end
 9
10julia> print(dp)
11
12Any[5//2, 7//10, 7//10, 7//10, 7//10, 7//10]
13
14julia> print([x/sum(dp) for x in dp])
15
16Rational{Int64}[5//12, 7//60, 7//60, 7//60, 7//60, 7//60]

and these are the values obtained by the authors (but with a lot less work).