Page 1

Smith

2005.8.6

multiwinner

Reweighted range voting . new multiwinner voting method

Warren D. Smith

.

August 6, 2005

Abstract . Reweighted range voting (RRV), a new mul-

tiwinner voting scheme, is defined and its main properties

elucidated. Compared with good quality single transfer-

able vote (STV) schemes, RRV is algorithmically simpler,

grants voters greater expressivity (RRV votes are real vec-

tors), is monotonic, and is less vulnerable to painful tied

and near-tied elections. RRV also seems less chaotic

than STV in its operation and seems to encourage voter

honesty to a greater degree (although I have no precise

definition of exactly what these things mean). RRV re-

duces to .range voting,. the experimentally best 1-winner

scheme, in the 1-winner case. Like good quality STV

schemes and my previous .asset voting,. RRV obeys a

proportionality theorem and offers good immunity both to

.candidate cloning. election-manipulation attempts, and

to the .wasted vote. strategic problem that plagues 3-

candidate plurality elections.

We also reexamine some fundamental issues about multi-

winner elections, such as .why is proportionality a good

thing? And what is the chance an STV election will be

nonmonotonic? And we prove a new fundamental impos-

sibility theorem.

1 Proportionate versus dispropor-

tionate representation

Many sources, ranging from the early thinkers [5] to more

modern texts [8][9][6], took it for granted that proportional

representation.in parliaments is a good goal. Instead, we now

genuinely examine the question.

If party A has 3 times as many votes as party B, does that

mean it should get 3 times as many seats?

Perhaps you think minorities tend to be oppressed and hence

deserve a little extra help, so A should only get 2 times as

many seats. Or perhaps you think minorities are going to

lose anyway, so it is better for society to accelerate their loss,

so they should be granted a little less power, so that (say)

A should get 4 times as many seats. These all initially seem

defensible points of view.

So suppose you think getting X times as many votes entitles

you to F(X) times as many seats, for some increasing smooth

function F(X) with F(0) = 0 and F(1) = 1, but you are not

sure what F should be. We can narrow down the choices:

F(a)F(b) = F(ab)

(1)

is required for self-consistency of your view. (This is by con-

sidering 3 parties P

1

, P

2

, P

3

where P

2

has a times as many

votes as P

1

and P

3

has b times as many as P

2

and hence ab

times as many as P

1

.)

Fact 1 (All self-consistent kinds of representation).

The only self-consistent smooth monotonic F(x) with F(1) =

1 and F(0) = 0 are: F(x) = x

P

where P is any constant

positive power.

If P = 1 we get proportional representation. But if P = 1,

P > 0 then we get disproportionate representation: a fraction

X of the population will get a number of seats proportional

to X

P

. Call this P-power representation.

Fact 2 (Effect of chained elections on P). If the popu-

lation elects a subpopulation of representatives using P-power

representation, then that subpopulation elects a subsubpopu-

lation using Q-power representation, then the characteristic

powers P in the two elections will multiply: the net effect is

PQ-power representation.

Now, why is it that, for the good of society, we should prefer

P = 1? Suppose there is some yes/no question that needs

to be decided. Presumably, the best attainable decision for

the population as a whole would be reached if the entire pop-

ulation (after having studied the issue) voted yes or no on

it.

Fact 3 (Subsampling and binary choices). The same

yes/no vote-percentages would happen (in expectation) if a

random subsample of the population were selected (instead of

the whole population), they studied the issue, and they voted

on it.

That is exactly the effect that is approximated by having a

proportional representation parliament. But:

Theorem 4 (Subsampling and binary choices). Any

disproportionate subsample of the population would in expec-

tation vote with different percentages, on some binary issue

B, than the whole population, and furthermore B may be cho-

sen so that the two percentages are above and below 50%.

Proof sketch: Make B be the following yes/no question: If

you are a type-X person, then say yes with probability p, oth-

erwise say yes with probability q. where X is chosen so that

type-X people are disproportionately represented in the sam-

ple, and the numerical values of p and q are chosen to cause

vote percentages above and below 50% (since this is two lin-

ear equations in two variables, it is not hard to see there are

.

Sep 2004

1

1. 0. 0

Smith

typeset 11:37 6 Aug 2005

multiwinner

always suitable p, q with 0 . p, q . 1, indeed p . q . 1/2).

Q.E.D.

Theorem 4 and fact 3 are a valid basis for claiming that pro-

portional representation is better for society than dispropor-

tional representation.

Another advantage of proportional representation is this.

Suppose there is a country which is divided into districts. If

each district chose representatives via a truly proportionate

scheme, with the number of representatives from each dis-

trict truly proportional to its population, then (at least if we

may ignore rounding-to-integer effects) the composition of the

parliament could not be altered by evil attempts to redraw

district boundaries. That would not be true if the districts

employed disproportionate representation.

Many so-called.proportional.representation governments ac-

tually involve cutoffs in which, e.g., parties with below 5% of

the vote get zero seats. Theorem 4 indicates that such cutoffs

are a bad idea.

The USA.s legislative bodies are elected via a system which

makes little or no attempt to provide proportionate represen-

tation. As of August 2004, the total number of women in

the US House is 62 out of 435 total members, and the total

number of women in the 100-member Senate is 13. The total

number of blacks in the US House is 38 and in the Senate is

zero,

1

so that the black percentage (7%) of House and Senate

members is approximately half their percentage (12.3%) in the

US population as a whole. In the entire history of the USA,

there have been only 5 black Senators. To my knowledge, no

atheist has ever won a US House or Senate seat.

In 1929, the UK.s Liberal party got 23.4% of the vote but

less than 10% of the seats, as a result of the highly dispropor-

tional voting system used. This caused most voters to give

up on the Liberal party as a probable wasted vote. So in

the next election, it got only 7% of the votes. The net effect

was, essentially, to destroy that party.

Moral: Proportional representation is a good goal, but one

not achieved in 2004 USA or 1929 UK.

2 A note on notation

We will use a few notations which the less-mathematical

among our readers may not know about. The floor function

.x. (pronounced floor of x.) is the greatest integer I with

I . x. For example .5.72. = .5. = 5. Similarly the .ceiling.

function .x. rounds upward, so .5.72. = .6. = 6. A N-vector

is an N-tuple of numbers. Variable names which are vectors

are commonly written with a little arrow above them, in or-

der to distinguish them from ordinary variables (.scalars.).

For example z = (0, 5, 7) would be a 3-vector, while q = 2

would be a scalar. Vectors of the same size can be added:

(3, 4, 7) + (1, 0, 9) = (4, 4, 16). Vectors also may be multiplied

by scalars, e.g. the product qz of the scalar q and the 3-vector

z we just defined would be qz = (0, 10, 14).

3 STV, asset, and range voting

I believe the two most meritorious previously proposed mul-

tiwinner election methods are .Hare/Droop STV. (single

transferable vote) and .asset voting.. Actually these each

really are a family of methods, comprising many variants of

the same sort of idea, and I have no clear understanding of

which variant is the best.

Short descriptions: Let there be N candidates from whom

the voters must select W winners, 0 < W < N.

Asset voting [11]: each vote is an N-vector of nonnegative

reals whose entry-sum is 1. The ith coordinate of the sum of

the vote-vectors is the amount of an.asset.that gets awarded

to candidate i. The candidates then .negotiate.; any subset

of the candidates can agree to redistribute the asset among

themselves. After negotiations end, the W candidates with

the most assets win. (Variants constrain the possible negoti-

ations in various ways.)

STV: is too complicated to explain here in full detail. (A 20-

line pseudocode procedure is given on page 7 of [11], and see

ch.7 of [9] and [12].) But we shall explain it in the simplest

case W = 1 where there is a single winner. Each vote is a

preference ordering of the N candidates. The election pro-

ceeds in rounds. Each round the candidate top-ranked by the

fewest votes is eliminated and erased from all preference or-

derings. We continue until only one remains; he is the winner.

(Variants allow each preference ordering also to express indif-

ference or ignorance, and there are various possible .quota.

and .reweighting. schemes in the multiwinner case.)

Both these families have members which provably cause repre-

sentation to obey some kind of .proportionality.[12][11] (un-

der certain assumptions about constituencies of voters and

candidates and how they will act). Specifically (the following

theorem is stated more precisely, and proved, in [11]):

Theorem 5 (STV/Asset proportionate representa-

tion). Suppose there are disjoint kinds of people. Specifically,

in a V -voter, N-candidate, W-winner election, let the num-

ber of voters of type t be V

t

, the number of candidates of type

t be N

t

, and the number of winners of type t be W

t

. Fur-

ther suppose that each type-t voter prefers each type-t can-

didate to every candidate of any other type, and says so in

their Hare/Droop-STV vote. Define the .Droop Quota. Q by

Q = .V/(W + 1). + 1. Then: W

t

. .V

t

/Q. if N

t

. .V

t

/Q..

Under asset voting (if each type-t voter allocates all of his

votes to type-t candidates and candidates of the same type

agree to help each other), W

t

. .V

t

(W + 1 . .)/V . where

. is any positive real, no matter how small, and provided

N

t

. .V

t

(W + 1 . .)/V ..

In other words, by running enough candidates and voting for

them, each constituency

2

can guarantee getting at least a

number of representatives essentially proportional to its mem-

bership.

Nevertheless, both STV and asset voting have disadvantages.

Range voting is experimentally the best 1-winner scheme for

mapping votes to the identity of a single winner.

3

It is this:

1

The confidences that these Senate black and female percentages are not mere statistical fluctuations are 99.9997% and 1 . 10

.14

respectively.

2

I use the word .constituency. in the same sense as Tideman [12] and the online WordIQ dictionary: .A constituency is any cohesive ... body

[of people] bound by shared structures, goals or loyalty..

3

My paper [10] is by far the largest, and perhaps the only, experimental and theoretical study of range voting in comparison with other voting

systems. But I am not the inventor of range voting; it has been used in the Olympics.

Sep 2004

2

3. 0. 0

Smith

typeset 11:37 6 Aug 2005

multiwinner

each voter provides a real N-vector, each entry of which lies in

the unit interval [0, 1], as his vote (any other fixed range could

be used instead). The vectors are summed and the index of

the largest coordinate in the sum-vector is the winner.

So it is distressing that neither STV nor asset voting reduce

to range voting in the 1-winner case.

Not coincidentally, STV is non-monotonic [3][4], i.e. giving a

candidate your maximum possible vote can actually cause him

to lose! Consequently STV voters can be motivated to express

dishonest preferences in their votes . even in 3-candidate 1-

winner elections . whereas [10] voters are never motivated to

range vote in a manner whose .-order relations are incom-

patible with their true opinion of the 3 candidates.

Another trouble with STV is that votes are preference or-

derings with no way for voters to describe the intensities of

their preferences. In contrast, in both range and asset voting,

the votes are vectors of continuously variable real numbers,

allowing much more voter expressivity. Finally, asset voting

is unconventional in that it is not a map from a set of votes

to a set of winners at all . rather, the votes merely are used

to provide variable amounts of an .asset. to each candidate,

giving them more or less power in the later negotiation. Many

people do not like this .negotiation. idea.

Our purpose in this paper is to present (in .5) a new multi-

winner voting method without any of those disadvantages.

4 The probability of nonmonotonic-

ity in STV 3-candidate 1-winner

elections

STV elections can be nonmonotonic [3][4], i.e., voting for a

candidate can actually cause him to lose. This is a major

criticism of STV ([3]: .goes entirely against all principles of

democracy.) and, if this pathology is common enough, it is a

major reason to replace it with the new system, RRV, that

we shall describe in .5.

So how common is this? Crispin Allard [1] made an inexact

geometric estimate of the probability of nonmonotonicity in a

3-candidate single-winner STV election and got 0.00025, sug-

gesting this is not a problem in practice. However, his work

had errors.

4

We will now redo and correct Allard.s estimate.

Let the three candidates be A, B and C.

Definition. A single-winner STV election will be said to be

.nonmonotonic. if B wins, but if some subset of the voters,

solely by changing their top-rankings away from A, can cause

A to win.

The conditions for a STV monotonicity failure are:

1. A is ahead of B who is ahead of C in the first-place vote

counts;

2. When C is eliminated, his transfers move B ahead of A

so B is elected;

3. If some number of voters switch their top preference

from A to C, so that both A and C are ahead of B,

then when B is eliminated, A goes ahead of C, so that

A is elected: nonmonotonicity!

Mathematically, these conditions are:

1. a > b > c.

2. a < b + .c,

3. Some x > 0 exists so that a . x > b, c + x > b, and

a > c + 2x + .b where . = T

CB

. T

CA

, . = T

BC

. T

BA

where T

ij

is the proportion of i.s votes which transfer

to j if i is eliminated.

Assuming a > b > c, by letting x slightly exceed b . c we find

that these conditions are equivalent to

a < b + .c, a + c > 2b, a + c > (2 + .)b.

(2)

So we now can say the following.

Theorem 6 (Nonmonotonicity probability P). Let P be

the probability of nonmonotonicity in a 1-winner 3-candidate

STV election, assuming that all vote fractions arise from a

subdivision of the unit interval arising by placing an appro-

priate number of random-uniform points inside it. Then P is

equal to the probability that if 7 real variables a, b, c, u, w, y, z

are chosen uniformly from the following 4-dimensional subset

of R

7

a + b + c = y + z = u + w = 1, u, w, y, z > 0, a > b > c > 0

(3)

and . = y . z and . = u . w, that the conditions in EQ 2 all

will be satisfied.

So far, we have simply intentionally followed Allard.s reason-

ing, although we have cleaned it up somewhat and corrected

Allard.s mistake of forgetting to demand a > b > c > 0 in EQ

3, which made him off by a factor of 6. Aside from that, we

both got the same result, which is that P is expressible as the

4-volume of a certain set. Now Allard attempted to estimate

that volume and made errors while doing so. We instead take

the simplest and most direct approach to computing volumes

and to estimating probabilities: computer Monte Carlo inte-

gration.

5

For those who know the computer language C, the

core of the Monte Carlo program is the following:

Count=0;

for(i=0; i<N; i++){

y = rand01(); z = 1.0-y;

u = rand01(); w = 1.0-u;

do{

a=rand01(); b=rand01(); c=rand01();

s = a+b+c;

}while(s>1.0 || s==0.0);

if(a<b){ t=a; a=b; b=t; }

if(b<c){ t=b; b=c; c=t; }

if(a<b){ t=a; a=b; b=t; }

assert(a>b); assert(b>c);

a /= s; b /= s; c /= s;

assert(a+b+c < 1.01);

assert(a+b+c > 0.99);

4

M.A.E.Dummett in his book [6] had already attacked Allard.s estimate as likely to be erroneously too small, although he gave no evidence to

back that accusation up.

5

The computer program I used to do this may be downloaded from http://math.temple.edu/.wds/homepage/works.html #78. It might be

possible for a more dedicated mathematician than I to compute an exact closed form for P by doing the integral.

Sep 2004

3

4. 0. 0

Smith

typeset 11:37 6 Aug 2005

multiwinner

beta = y-z;

alpha = u-w;

if( a < b + alpha*c ){

if( a+c > 2*b ){

if( a+c > (2+beta)*b ){

Count++;

}}}

}

which performs N Monte Carlo experiments, of which Count

are nonmonotonic, leading to the estimate P . Count/N.

My 10

9

Monte Carlo experiments resulted in 10498423 mono-

tonicity failures, which combined with a jackknife error esti-

mate yields:

Fact 7. P = (1.050 . 0.001)%.

Allard had underestimated P by two orders of magnitude. In

STV elections with more than 3 candidates, nonmonotonicity

can also happen in other ways and hence should be even more

likely.

In other words, at least about one STV election in 95 would

be nonmonotonic. There were 659 MPs in the UK House

of Commons in 2001. So if the UK used STV single-winner

(. 3)-candidate elections to choose them, we would expect 7

nonmonotonic elections. That means 7 very angry and fairly

powerful robbed-winners, all demanding the blood of those

fools who had advocated STV! Those who prefer to avoid

that scenario are advised to advocate the (fully monotonic)

RRV system proposed next section.

5 Reweighted range voting

Our new voting system, .reweighted range voting. (RRV),

attempts to combine the advantages of range voting and

Hare/Droop STV.

Let there be N candidates from whom V voters are to select

W winners, 0 < W < N, 0 < V .

procedure Reweighted-Range-Vote

1:

Each voter k supplies an N-vector x

k

as his vote, each

entry of which is a real number in [0, 1]. The Cth entry

of this vector expresses that voter.s opinion of candidate

C (i.e. 1=great, 0.5=middling, 0=terrible);

2:

Each N-vector vote has associated with it, a .weight.

w

k

. [0, 1].

3:

for r = 1 to W do

4:

for k = 1 to V do

5:

Let the weight of vote k be w

k

= 1/(X+1), where the

sum of vote x

k

.s winner-entries is X. (Thus, initially,

there are no winners and all weights are 1.)

6:

end for

7:

Compute the weighted-vote-sum vector s =

V

k=1

w

k

x

k

(actually, this step would be best programmed as com-

bined into step 5, but we have written it separately to

enhance clarity);

8:

The candidate C with the largest s-entry (among can-

didates who have not yet been declared .winners.) is

declared to be the rth winner.

9:

end for

In the 1-winner case, RRV reduces to range voting [10], i.e.,

it simply adds up all the vote vectors s =

V

k=1

x

V

k=1

x

k

and then

declares the winner to be the index of the largest entry in

s. The first RRV winner in fact is always the same as the

range-voting winner, but the second RRV winner is not nec-

essarily the same as the candidate range voting would say was

in second-place. That is because the reweightings cause the

supporters of the first winner to have diminished influence on

the choice of the second.

Here is a list of good properties of RRV:

1. No .negotiation. is needed, unlike in asset voting [11].

2. RRV grants each voter greater freedom of expression

than STV.

3. RRV is monotonic in the sense that top-ranking a can-

didate in your vote (or more generally simply increasing

your vote for him) cannot hurt his chances of winning.

4. The weighting scheme seems to force fairly pro-

portional representation.

E.g.

if 51% of voters

vote (1,1,1,1,1,0,0,0,0,0) (.Republican.) and 49% vote

(0,0,0,0,0,1,1,1,1,1) (.Democrat.) in a N = 10, W = 5

election, then the weightings will cause alternate elec-

tions of Republicans and Democrats.

Here is another example, worked out by John Hodges

(whom we quote):

1000 fully-polarized voters, 10 seats, 20

candidates, two parties R and D, with

70% and 30% of the vote respectively.

Then RRV gives the seats sequentially to

R,R,D,R,R,D,R,R,tie, and whoever wins the

tie loses the next one, so with ten seats the

R.s get 7 and the D.s 3. Great.

When W is small, how does this compare

with the Droop Quota? With 2 seats, under

Droop you would need 33% of the vote to get

a seat, with 5 seats you would need 16.666%,

with 8 seats 11.111%, so the above sequence of

wins compares OK in fairness with the Droop

Quota.

We will in fact prove a proportionality theorem below.

5. Consequently there is considerable immunity to at-

tempts to manipulate the election via candidate

.cloning.. (Manipulability by cloning is a well known

deficiency of plurality voting.)

6. RRV has no .wasted vote. problem (also a well known

defect of plurality voting) . at least in 3-candidate 1-

winner elections. (Since range voting has no such prob-

lem: voting for an unlikely to win candidate C does not

hurt any favorite . unless C actually does win.)

7. RRV.s algorithmic complexities (both descriptive and

computational), although substantially worse than

range and asset voting, are simpler than most STV

schemes.

6

That is especially true of STV schemes which

allow voters to express equalities among candidates in

their preference orderings or which allow the voters to

only rank some, but not all, of the candidates.

7

It is ac-

tually rather unclear how STV systems should deal with

6

A 20-line pseudocode procedure for STV voting is given on page 7 of [11]. The present RRV procedure is 9 lines.

7

These changes would bloat STV.s line count from 20 to more like 50.

Sep 2004

4

5. 0. 0

Smith

typeset 11:37 6 Aug 2005

multiwinner

voters who refuse to rank everybody. In RRV, equalities

are trivial for voters to express, and voters could simply

be allowed to complete their votes by saying ....and I

award Z votes to each additional candidate. where Z is

some number they specify (0 . Z . 1), which would

make vote-completion easy.

8. RRV.s vulnerability to painful near-tied elections (of the

sort that keep plunging the USA into crisis) is not as bad

as STV.s since it does not have candidate.eliminations.

(which lead to additional opportunities for vote-ties).

9. Eliminations in STV schemes have been criticized by

Dummett [6] as capable of causing .chaotic. behavior

. small changes in the input votes can get amplified

to have large effects. RRV has no eliminations and all

weight-changes are multiplications by factors< 1, i.e.

the opposite of amplification. (These factors also are

. 1/2 so that there are no giant decreases either; in the

rth round all weights are between 1/r and 1 and hence

can never get either extremely small or extremely large.)

Hence RRV should largely .avoid chaos..

10. Finally, there is a certain amount of .encouragement

of voter honesty. built in to RRV: you do not desire

to exaggerate your opinion of some good candidate by

too much, since that will (when he wins) decrease your

vote-weight.

Theorem 8 (RRV proportionate representation). Sup-

pose there are disjoint kinds of people. Specifically, in a V -

voter, N-candidate, W-winner election, let the number of vot-

ers of type t be V

t

, the number of candidates of type t be N

t

,

and the number of winners of type t be W

t

. Further suppose

that each type-t voter awards each type-t candidate the maxi-

mum allowable vote 1 while giving each candidate of any other

type 0. Then:

|(W

t

+ 1)V

s

. (W

s

+ 1)V

t

| . min{V

t

, V

s

}

(4)

for each s, t with V

t

, V

s

. 1, provided enough type-s and type-

t candidates are available so that we don.t .run out of either

prematurely.. (It ought to suffice if N

k

. V

k

W/V for each

needed k.)

Proof: Let W = V

a

/V

b

be the ratio of the number of type-a

to type-b people. If J type-a candidates and K type-b can-

didates have been elected (so far), the weighted sum of the

votes for any given as-yet-unelected type-a candidate will be

ZV/(J +1) whereas the the weighted sum of the votes for any

given as-yet-unelected type-b candidate will be V/(K + 1).

Thus if J + 1 > (K + 1)Z then a type-b candidate will

be elected before a type-a one, while if J + 1 < (K + 1)Z

then a type-a candidate will be elected first next. Therefore

(assuming there are enough candidates of each type avail-

able, so that we do not run out, i.e. N

u

is sufficiently large

for each u of interest) RRV will produce W

t

.s such that

|(W

t

+ 1)V

s

/V

t

. (W

s

+ 1)| . 1 if V

s

. V

t

. 1. This proves

the theorem. Q.E.D.

The way this is worded seems to be a stronger kind of state-

ment about proportionality than in theorem 5. If anybody

should desire it,

8

P-power disproportionate representation

would also be achievable via Reweighted-Range-Vote by

changing the weight formula in line 5 to w

k

= 1/(X + 1)

P

.

6 A displeasing lack of symmetry?

The reader may have noticed that Reweighted-Range-Vote

asymmetrically concentrates on winners and not losers. Sim-

ilarly, Hare/Droop STV includes two different kinds of steps:

those that select winners (who exceed the.Droop quota.) and

losers (who are .eliminated.; RRV somewhat resembles STV

but has no eliminations). Thus both treat the two differently.

This seems peculiar. After all, a scheme for electing W win-

ners from N candidates, may equally well be thought of as a

scheme for choosing the N . W losers. One might therefore

imagine that .God.s election method. instead would treat the

two symmetrically. But in fact: doing so is impossible. We

now prove this.

Desire #1 [proportional representation]: A fraction F of the

voters (forming a .constituency.) should be able to elect a

fraction F of the seats.

Desire #2 [reversal symmetry]: Since choosing W winners

from N candidates, can equally well be regarded as choos-

ing the N . W losers, we desire that if all votes are re-

versed=negated,

9

and the value of W changed to N . W,

then the complement set should be elected.

Fact 9. These two desires are incompatible.

Remarks on the upcoming proof. One reader claimed the

proof is wrong because .candidates have only one attribute..

Yes, if we were just ordering candidates along a line, or just

associating a single real number with each, then they would

have only 1 attribute. However, we also are addressing the

desire for proportional representation (PR). The whole con-

cept of PR only has meaning at all (as in theorems 5 and 8)

if there are parties or constituencies, and there can be many

of these (in the following proof, there are 3 kinds). That is

more than 1 attribute.

Now if we want to talk about both PR and reversal symme-

try at the same time, then it would not be symmetric to con-

sider only Republican-loved and Democrat-loved candidates.

We need also to have Republican- and Democrat-hated ones.

Then if one then tries to impose both PR and reversal sym-

metry, a contradiction results, proving fact 9.

Proof: Suppose 45% of Voters are Republican, 33% Demo-

cratic, and 22% Anarchist. Suppose candidates are either

Republican-loved, Democrat-loved, or Anarchist-loved (dis-

jointly from each other) and also are either Republican-hated,

Democrat-hated, or Anarchist-hated (again disjointly from

8

Dan Keshet also suggests changing the 1 + X to r + X where r is a positive constant. In particular he suggests r = 1/2. He argues that RRV

with r = 1 is analogous to the .d.Hondt count. method of awarding seats to parties in party-list democracies. With r = 1/2 it instead would be

analogous to the .pure Sainte-Lague. method: All parties initially have 0 seats; the party with largest quotient of votes divided by 0.5 more than

its current number of seats, receives the next seat; this is repeated until the desired total number of seats has been awarded. Keshet.s r-modified

RRV still will obey proportionality theorem 4 except that the two occurrences of .+1. in EQ 4 both must be replaced by .+r..

9

More precisely: to .reverse. preference ordering votes A > B > C > D > . . . replace them with . . . > D > C > B > A. To .reverse. or negate

a range vote involving numbers x in the range [0, 1], replace them with 1 . x. (If the range instead were [.1, 1] then we instead would negate

x . .x).

Sep 2004

5

6. 0. 0

Smith

typeset 11:37 6 Aug 2005

multiwinner

each other). Nobody is both loved and hated by the same

person, but there are no further certainty-relationships, e.g.

Anarchist-loved neither implies nor is implied by Democrat-

Hated. There are thus exactly 6 possible kinds of candidates

which we could denote

10

RD, RA, DR, DA, AR, AD.

Then: There simply is not, in general, any way to partition a

given set of candidates into winners and losers with the win-

ners being 45%, 33%, and 22% Republican-, Democratic-, and

Anarchist-loved, respectively, and the losers being 45%, 33%,

and 22% Republican-, Democratic-, and Anarchist-hated, re-

spectively. Why? Because the following set of 12 simultanous

linear equations in 12 variables

RA

w

+ RD

w

= 45, DA

w

+ DR

w

= 33, AR

w

+ AD

w

= 22,

AR

.

+DR

.

= 45, AD

.

+RD

.

= 33, RA

.

+DA

.

= 22, (5)

RA

w

+RA

.

= RA, RD

w

+RD

.

= RD, DA

w

+DA

.

= DA,

DR

w

+ DR

.

= DR, AD

w

+ AD

.

= AD, AR

w

+ AR

.

= AR

(note:

I have employed 2-letter variable names) then

would have a solution no matter what 6 values

RA, RD, DA, DR, AD, AR (summing to 100) were chosen

for the right hand sides (as the percentages among the can-

didates of the 6 types of people). But this is a singular set

of equations and hence generically has no solution. In par-

ticular, Gaussian elimination shows it has no solution when

RA = 14, RD = 15, DA = 16, DR = 17, AD = 19, AR = 19.

Q.E.D.

In light of this impossibility theorem, it is entirely proper for

STV and RRV to concentrate asymmetrically on winners.

7 Conclusion

We began by re-examining some fundamental issues about

proportional representation, finding some new justifications

for it. (Actually, quite plausibly these realizations were not

so much .new. as merely .not previously expressed in a for-

mal manner..) We also found a simple, but profound, impos-

sibility theorem about multiwinner voting schemes: reversal

symmetry and proportional representation are incompatible

desires.

We then quickly pointed out the most important advantages

and defects of asset and STV voting, along the way correcting

a wrong (but unfortunately widely quoted) numerical calcu-

lation by Allard which had made STV look too good.

Reweighted Range Voting (RRV) was then proposed as a new

multiwinner voting method which is free of those defects.

We proved RRV obeys a proportionality theorem. All propor-

tionality theorems in this paper are essentially of the form: if

all voters are purely self-interested amoral racists, then they

will be able to get the representation they deserve.

RRV is simpler to describe and use than STV, it is monotonic,

and it allows voters much greater expressivity. The only clear

advantage STV has over RRV is that in small elections carried

out without computer aid, STV may be done by simply count-

ing and sorting ballot papers repeatedly, with comparatively

few real number arithmetic operations being required. That

is because in a W-winner Hare/Droop-STV election, at most

2

W.1

different weight values ever arise, because for each of

W .1 winners one either applies, or does not apply, that win-

ner.s reweighting factor to each vote. If 2

W.1

is substantially

smaller than the number of voters, one can therefore substan-

tially reduce the number of needed real arithmetic operations

by sorting the ballot papers into 2

W

different piles, each pile

labeled with its weight value. (On the other hand some fancier

STV schemes such as Meek.s [7] actually require far more real

arithmetic than RRV and definitely require a computer.)

So in my opinion these RRV advantages render STV obsolete

in all but small elections done manually.

Asset versus RRV: Asset voting is simpler than RRV and

arguably has certain further advantages (e.g.: candidates with

too few votes to be elected still get some power, as seems

.more fair.). But since.negotiation.is present in asset voting

and not in RRV, the former is inapplicable if the entities being

elected are not sentient. (It is left to the reader to determine

whether that is the case in their election.) Thus both asset

voting and RRV remain standing with neither obsoleted.

Take-home messages:

1. Proportional Representation is a good goal;

2. Our new RRV voting system is a good one that should

be preferred to STV except perhaps in small manual

elections;

3. It would be wise to recommend RRV and avoid rec-

ommending nonmonotonic systems such as STV, since

nonmonotonicity occurs much more commonly than had

been thought and would engender tremendous rage in

its victims

11

;

4. It is impossible to design a.reversal symmetric.PR vot-

ing system . explaining why neither STV nor RRV are

reversal-symmetric.

References

[1] Crispin Allard: Estimating the Probability of Monotonicity Fail-

ure in a UK General Election, Voting matters 5 (January 1996).

[2] J.J. Bartholdi III & J.B. Orlin: Single transferable Vote resists

strategic voting, Social Choice & Welfare 8,4 (1991) 341-354.

[3] Steven J. Brams & Peter C. Fishburn: Some logical defects of the

single transferable vote, Chapter 14, pp. 147-151, in Choosing an

Electoral System: Issues and Alternatives (Arend Lijphart and

Bernard Grofman, eds.) Praeger, New York 1984.

[4] G. Doron & R. Kronick: Single Transferable Vote: An Example of

a Perverse Social Choice Function, American J. Political Science

21 (May 1997) 303-311.

[5] Henry R. Droop:

On methods of electing representatives,

J.Statistical Society London 44,2 (1881) 141-196; comments 197-

202.

10

The first letter in the 2-letter name says who loves you, the second who hates you.

11

We quote [4]: .Most voters would probably be alienated and outraged upon hearing the hypothetical (but theoretically possible) election night

report: .Mr. O.Grady did not obtain a seat in today.s election, but if 5000 of his supporters had voted for him in second place instead of first place,

he would have won!... The main factor saving STV from this fate is the fact [2] that it can be painful to recognize a nonmonotonic STV election,

and perhaps, often, nobody made the effort. (This reference proved NP-completeness of the recognition problem, although not if the number of

candidates is fixed.)

Sep 2004

6

7. 0. 0

Smith

typeset 11:37 6 Aug 2005

multiwinner

[6] Michael A.E. Dummett: Principles of Electoral Reform, Oxford

Univ. Press 1997.

[7] I.D.Hill,

B.A.Wichmann,

D.R.Woodall:

Algorithm

123,

single transferable vote by Meek.s method,

Com-

puter Journal 30,3 (1987) 277-281. Available online at

http://www.bcs.org.uk/election/meek/meekm.htm.

Brian

Meek.s original work was published in French and an En-

glish translation is available in issue 1 (March 1994) of

the ERS publication Voting Matters, available online at

www.mcdougall.org.uk/VM/MAIN.HTM.

[8] Clarence G. Hoag & George H. Hallett: Proportional Represen-

tation, Macmillan, New York 1926; Johnson reprint corp. 1965.

[9] W.J.M. Mackenzie: Free elections, George Allen & Unwin Ltd.

London 1958.

[10] Warren D. Smith: Range voting, #56 at

http://math.temple.edu/.wds/homepage/works.html.

[11] Warren D. Smith: .Asset voting. scheme for multiwinner elec-

tions, #77 at

http://math.temple.edu/.wds/homepage/works.html.

[12] Nicolaus Tideman: The Single transferable Vote, J. Economic

Perspectives 9,1 (1995) 27-38. (Special issue on voting methods.)

Sep 2004

7

7. 0. 0