Eivind Stensholt is from the Norwegian School of Economics and Business Administration
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.
(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:
[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.
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.
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.
(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.