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 *n*^{2}. 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:

- 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.

[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*) =
* x*^{4} + (*a*+*b*+*c*+*d*)*x*^{3} +
(*ab*+*ac*+*ad*+*bc*+*bd*+*cd*)*x*^{2} +
(*bcd*+*acd*+*abd*+*abc*)*x* + *abcd*.

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

Q(E, *x*) = [*x*^{3} + (*a*+*b*+*c*)*x*^{2} + (*bc*+*ca*+*ab*)*x* + *abc*](*x*+*d*)

= [*x*^{4} + (*a*+*b*+*c*)*x*^{3} + (*bc*+*ca*+*ab*)*x*^{2} + (*abc*)*x*]
+ [*dx*^{3} + (*a*+*b*+*c*)*dx*^{2} + (*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 *x*^{3},
*x*^{2}, 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(C*i*, *x*) = [*x*+*p*(1)][*x*+*p*(2)] . . . . . [*x*+*p*(*n*)]/[*x*+*p*(*i*)]
= B(0)*x ^{n}*

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, ..., C*n* 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 C*i*, i.e. the
votes to C*i* 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 C*i* as number *t*+1. The *t*
candidates ranked ahead of C*i* can be permuted in *t*! ways. The
*n*-*t*-1 candidates ranked after C*i* 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
C*i* and they offer the same support to candidate C*i*. The total
revenue collected by C*i * 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(C*i*,*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)*x ^{n}* + A(1)

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)*x ^{n}*+A(1)

[B(0)*x ^{n}*

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(C*i*,*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 3*n*(*n*-1)/2 multiplications and
3*n*(*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
*n*^{2} additions/subtractions associated with the use of the
contribution formula for n candidates, and so we arrive at
*n*(5*n*-1)/2 multiplications and *n*(5*n*-3)/2
additions/subtractions.

Further small savings are obviously possible, e.g. by keeping
Q(C*n*,*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 x^{9} + 6.30 x^{8} + 17.5920 x^{7} + 28.576800 x^{6} + 29.75937888 x^{5} + 20.60302608 x^{4} + 9.482569153 x^{3} + 2.797730344 x^{2} + 0.4801360978 x + 0.03651691196.

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

1 x^{8} + 5.44 x^{7} + 12.9136 x^{6} + 17.471104 x^{5} + 14.73422944 x^{4} +7.93158876 x^{3} + 2.661402819 x^{2} + 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.

- I D Hill, Difficulties with equality of preference,
*Voting matters*, Issue 13, April 2001, pp8-9. - B L Meek, Une nouvelle approche du scrutin transferable
(fin),
*Mathématiques et sciences humaines*, 9 no.29 pp 33-39. 1970 - B L Meek, A new approach to the Single Transferable
Vote,
*Voting matters*, Issue 1, March 1994, pp1-11.