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

Share on:

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:

def all_subsets(X):
    T = [[]]
    for x in X:
	T += [t+[x] for t in T]
    return(T)

def is_subset(A,B):
    out = True
    for a in A:
	if B.count(a) == 0:
	    out = False
	    break
    return(out)

def mwc(q,S,T):
    if len(T) == 0:
	return(S)
    else:
	if sum(T[0]) >= q:
	    S += [T[0]]
	    temp = T.copy()
	    for t in temp:
		if is_subset(T[0],t):
		    temp.remove(t)
	    return(mwc(q,S,temp))
	else:
	    return(mwc(q,S,T[1:]))
def prod(A):
    m = len(A)
    n = len(A[0])
    p = 1
    for i in range(m):
	for j in range(n):
	    p *= A[i][j]
    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:

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

[[10, 9], [10, 6], [9, 6, 5]]

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

def dpi(q,wts):
    m = mwc(q,[],all_subsets(wts)[1:])
    dp = []
    for w in wts:
	d = 0
	for x in m:
	    d += x.count(w)/len(x)
	dp += [d]
    return(dp)

And as an example:

>>> wts = [10,9,6,5]
>>> q = 16
>>> dpi(q,wts)

[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:

using Combinatorics

function wcs(q,w)
    S = powerset(w)
    out = []
    for s in S
	if sum(s) >= q
	    append!(out,[s])
	end
    end
    return(out)
end

function mwc(q,out,wc)
    if isempty(wc)
	return(out)
    else
	f = wc[1]
	popfirst!(wc)
	temp = []   # temp finds all supersets of f = wc[1]
	for w in wc
	    if issubset(f,w)
		append!(temp,[w])
	    end
	end
	return(mwc(q,append!(out,[f]),setdiff(wc,temp)))
    end
end

Now we can try it out:

julia> q = 16;
julia> w = [10,9,6,5];
julia> cs = wcs(q,w)

7-element Array{Any,1}:
 [10, 9]
 [10, 6]
 [10, 9, 6]
 [10, 9, 5]
 [10, 6, 5]
 [9, 6, 5]
 [10, 9, 6, 5]

julia> mwc(q,[],cs)

3-element Array{Any,1}:
 [10, 9]
 [10, 6]
 [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:

julia> q = 30;
julia> w = [28,16,5,4,3.1,3];
julia> cs = wcs(q,w);
julia> ms = mwc(q,[],cs)

6-element Array{Any,1}:
 [28.0, 16.0]
 [28.0, 5.0]
 [28.0, 4.0]
 [28.0, 3.1]
 [28.0, 3.0]
 [16.0, 5.0, 4.0, 3.1, 3.0]

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

julia> dp = []
       for i = 1:6
	   x = 0//1
	   for m in mw
	       x = x + count(j -> j == w[i],m)//length(m)
	   end
	   append!(dp, [x])
       end

julia> print(dp)

Any[5//2, 7//10, 7//10, 7//10, 7//10, 7//10]

julia> print([x/sum(dp) for x in dp])

Rational{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).