t Up: Issue 16 Previous: Paper 1 Next: Paper 3

Voting matters - Issue 16, February 2003

Implementing a suggestion of Meek's

E Stensholt

Eivind Stensholt is from the Norwegian School of Economics and Business Administration

Introduction

In preferential elections voters are often assumed to have linear rankings, i.e. they rank all candidates without ties. Here the topic is STV elections where only a "complete order" is required, which means that a voter must give each candidate a rank, but may declare equal preference. Hence in a 10-candidate election a voter V may rank

PQ(ABCDE)RST

which, in Hill's notation[1], means that A, B, C, D, E share third to seventh rank.

At an iterative step in an algorithm for Meek's method a candidate P has a certain current retention factor: 1-p, which is a positive number less than or equal to 1. Voter V starts on top of his list, offers P his full vote, for which 1-p is retained and offers Q p votes, has p(1-q) retained and has w = pq votes when coming to the set of equal preferences {A, B, C, D, E}.

Meek[2] suggested to count as if there were 5! = 120 "minivoters", each with a weight of w/120 votes, with one minivoter for each possible way to split up the {A, B, C, D, E} into 5 singleton classes. With n candidates ranked equal, there are n! possible linear rankings, and the work soon becomes too much even for computers if each minivoter is considered separately. However, the counting can be systematized, so that the necessary work grows as n2. Thus there need not be a "combinatorial explosion", but the algorithm does not otherwise relate to Hill's discussion of how to cope with equality of preference.

A count with five candidates equal

One minivoter ranks ABCDE, and contributes

(1-a)w/120, a(1-b)w/120, ab(1-c)w/120, abc(1-d)w/120, abcd(1-e)w/120

to A, B, C, D, and E, respectively. Each minivoter keeps weight abcdew/120, and hence voter V keeps abcdew to influence the ranking of R, S, and T.

What is the total contribution from the 120 minivoters to candidate E? The contribution has 5 parts:

• 24 minivoters have E as number 1: 24(1-e)w/120
• 24 minivoters have E as number 2: 6(a+b+c+d)(1-e)w/120
• 24 minivoters have E as number 3: 4(ab+ac+ad+bc+bd+cd)(1-e)w/120
• 24 minivoters have E as number 4: 6(bcd+acd+abd+abc)(1-e)w/120
• 24 minivoters have E as number 5: 24(abcd)(1-e)w/120.
The total contribution from V to E is therefore

[1/5 + (a+b+c+d)/20 + (ab+ac+ad+bc+bd+cd)/30 + (bcd+acd+abd+abc)/20 + (abcd)/5](1-e)w

An efficient algorithm is possible because the factors that depend on a, b, c, and d are easily calculated as the coefficients in a polynomial:

Q(E, x) = (x+a)(x+b)(x+c)(x+d) = x4 + (a+b+c+d)x3 + (ab+ac+ad+bc+bd+cd)x2 + (bcd+acd+abd+abc)x + abcd.

How much computational effort is involved in calculating Q(E, x)? Writing

Q(E, x) = [x3 + (a+b+c)x2 + (bc+ca+ab)x + abc](x+d)

= [x4 + (a+b+c)x3 + (bc+ca+ab)x2 + (abc)x] + [dx3 + (a+b+c)dx2 + (bc+ca+ab)dx + (abc)d],

we see that the factor (x+d) involves first 3 multiplications of two real numbers with d as a factor and then 3 additions of two real numbers to get the coefficients of x3, x2, and x. Multiplying (x+a)(x+b) needs one multiplication and one addition, and (x+a)(x+b)(x+c) is calculated with two more of each. Hence Q(E,x) requires 1+2+3 = 6 multiplications and 1+2+3 = 6 additions. Moreover, the contribution formula contains 6 multiplications, 4 additions, and 1 subtraction.

The general case

In general, consider n candidates, C1, ..., Cn, with retention factors 1-p(1), ... , 1-p(n). Consider the polynomials

Q(Ci, x) = [x+p(1)][x+p(2)] . . . . . [x+p(n)]/[x+p(i)] = B(0)xn-1 + B(1)xn-2 + B(2)xn-3 + .... + B(n-1)

for i from 1 to n. Clearly B(0) = 1 while the other B(k) depend on i. They are the elementary symmetric polynomials in the p(j) where j /= i. The multiplication of n - 1 factors of type [x + p(j)] involves 1 + 2 + 3 + ... + (n-2) = (n-1)(n-2)/2 multiplications of two real numbers and equally many additions.

Suppose the candidates C1, ..., Cn form an equal preference set for voter V, who has weight w left after contributing to the higher ranked candidates. The contribution from V to candidate Ci, i.e. the votes to Ci from n! minivoters, is given by the contribution formula Rev(i) =

[K(n-1,0)B(0) + K(n-1,1)B(1) + ... + K(n-1,t)B(t) + ... + K(n-1,n-1)B(n-1)][1-p(i)]w

where the K(n-1,t) are determined as follows: There are n! minivoters, with weight w/(n!) each. Among them, (n-1)! have candidate Ci as number t+1. The t candidates ranked ahead of Ci can be permuted in t! ways. The n-t-1 candidates ranked after Ci can be permuted in (n-t-1)! ways. Thus t!(n-t-1)! of the (n-1)! minivoters have the same t candidates ahead of Ci and they offer the same support to candidate Ci. The total revenue collected by Ci from these (n-1)! minivoters is t!(n-t-1)! B(t) [1-p(i)]w/(n!). Thus K(n-1,t) = t!(n-t-1)! /(n!), i.e.

K(n,t) = t!(n-t)! /((n+1)!).

For the use of the contribution formula, it is practical to tabulate the coefficients K(n-1,t).

If each Q(Ci,x) is calculated as a product with n-1 factors, i from 1 to n, the total requirement is n(n-1)(n-2)/2 multiplications of two real numbers and n(n-1)(n-2)/2 additions. Thus the work grows with the third power of n. Here we leave out the n+1 multiplications and n-1 additions and 1 subtraction that must be performed each time the contribution formula is used.

However, with n>5 one may reduce the work by first calculating Q(x) =

[x+p(1)][x+p(2)] ... [x+p(n)] =

A(0)xn + A(1)xn-1 + A(2)xn-2 + ... +A(n)

by means of n(n-1)/2 multiplications and n(n-1)/2 additions, and then for each i perform the division with [x+p(i)]:

A(0)xn+A(1)xn-1+A(2)xn-2 +...+ A(n) =

[B(0)xn-1+B(1)xn-2+B(2)xn-3 +...+B(n-1)][p(i)+x]

leads to A(0) = B(0) = 1 and

A(1) = B(0)p(i) + B(1),

A(2) = B(1)p(i) + B(2), ... ,

A(n-1) = B(n-2)p(i) + B(n-1).

Hence Q(Ci,x) is calculated as follows:

B(1) = A(1) - B(0)p(i) ,

B(2) = A(2) - B(1)p(i) , ... ,

B(n-1) = A(n-1) - B(n-2)p(i).

The division with [x+p(i)] requires n-1 multiplications with p(i) as a factor and n-1 subtractions. All the divisions for i from 1 to n require n(n-1) multiplications and n(n-1) subtractions. Thus it is enough to perform 3n(n-1)/2 multiplications and 3n(n-1)/2 additions/subtractions instead of n(n-1)(n-2)/2 of each.

There are of course also n(n+1) multiplications and n2 additions/subtractions associated with the use of the contribution formula for n candidates, and so we arrive at n(5n-1)/2 multiplications and n(5n-3)/2 additions/subtractions.

Further small savings are obviously possible, e.g. by keeping Q(Cn,x) as an intermediate result from the calculation of Q(x) instead of dividing Q(x) by [x+p(n)], but they do perhaps not justify the extra programming.

A program for calculating the contributions

Here is a Maple routine for calculating the contribution from a voter with weight 1 to each candidate in an equal preference set of n candidates 1, 2, ... , n, with given retention factors. The total number of candidates is denoted by C.

Set n = number of candidates ranked equally by the voter:

> n:=9;

n := 9

Set p(i) for candidates 1, 2, ... , n, so that 1-p(i) is the current retention factor for candidate i.

> for i from 1 to n do p(i):=0.5+0.04*i; od;

p(1) := 0.54

p(2) := 0.58

p(3) := 0.62

p(4) := 0.66

p(5) := 0.70

p(6) := 0.74

p(7) := 0.78

p(8) := 0.82

p(9) := 0.86

As an example we use these equidistant values for the p(i). The routine consists of a "preparation" and two instructions. The preparation is used only once per run of the election program. It sets the coefficients K(i,j) = j!(i-j)!/(i+1)! by first calculating the binomial coefficients " i - choose - j " = i!/(j!(i-j)!).

Preparation. Set the table of constants. Let C be the total number of candidates:

> C:=20: for i from 0 to C-1 do K(i,0):=1.0; od: for j from 1 to C-1 do K(0,j):=0.0; od: for i from 1 to C-1 do for j from 1 to C-1 do K(i,j):=K(i-1,j-1)+K(i-1,j); od: od: for i from 1 to C-1 do for j from 0 to i do K(i,j):=1.0/((i+1)*K(i,j)); od: od:

Instruction 1. Calculate the polynomial of degree n:

> A(0):=1.0: B(0):=1.0: for j from 1 to n do A(j):=0.0; od: for j from 1 to n do for i from 0 to j-1 do A(j-i):= A(j-i-1)*p(j) + A(j-i); od; od;

Instruction 2. Calculate the polynomial of degree n-1 for candidate s and simultaneously set Rev(s) = the revenue for candidate s, s=1, 2, ..., n:

> for s from 1 to n do Pr:=K(n-1,0): q:=p(s): for j from 1 to n-1 do B(j) := A(j)-B(j-1)*q; Pr:=Pr+B(j)*K(n-1,j); od: Rev(s):=Pr*(1-q); od:

Another instruction shows the revenue Rev(s) collected by candidate s from all n! "minivoters" :

> for s from 1 to n do Rev(s):=Rev(s); od;

Rev(1) := .171708815169

Rev(2) := .154311932284

Rev(3) := .137512907077

Rev(4) := .121258700936

Rev(5) := .105503965732

Rev(6) := .0902095328389

Rev(7) := .0753412681397

Rev(8) := .0608691895186

Rev(9) := .0467667763417

These contributions sum to 0.963483088037.

The voter keeps p(1) p(2) ... p(n) = 0.036516911963.

What happens in the example above?

Consider 9 candidates sharing ranks 1 to 9 in a vote, and assume the retention factors are as above. The preparation has calculated a table including (K(8,0), ..., K(8,8)) =

(0.1111111111, 0.01388888889, 0.003968253968, 0.001984126984, 0.001587301587, 0.001984126984, 0.003968253968, 0.01388888889, 0.1111111111)

With the p(i) above, instruction 1 gets the polynomial of degree n = 9,

Q(x)= [x+0.54] [x+0.58][x+0.62] [x+0.66] [x+0.70] [x+0.77] [x+0.78] [x+0.82] [x+0.86] =

1 x9 + 6.30 x8 + 17.5920 x7 + 28.576800 x6 + 29.75937888 x5 + 20.60302608 x4 + 9.482569153 x3 + 2.797730344 x2 + 0.4801360978 x + 0.03651691196.

Then for s=9, instruction 2 gets Q(C9,x) = Q(x)/[x+0.86] =

1 x8 + 5.44 x7 + 12.9136 x6 + 17.471104 x5 + 14.73422944 x4 +7.93158876 x3 + 2.661402819 x2 + 0.508923920 x + 0.0424615266,

and at the same time it calculates the contribution from the voter with weight 1 to candidate 9:

[1 × 0.1111111111 + 5.44 × 0.01388888889 + 12.9136 × 0.003968253968 +17.471104 × 0.001984126984 + 14.73422944 × 0.001587301587 + 7.93158876 × 0.001984126984 + 2.661402819 × 0.003968253968 + 0.508923920 × 0.01388888889 + 0.0424615266 × 0.1111111111] × (1- 0.86)

= 0.3340484026 × (1- 0.86) = 0.04676677636.

Acknowledgement

The author is grateful to two referees for suggestions that have made the presentation clearer.

References

Up: Issue 16 Previous: Paper 1 Next: Paper 3