[EM] (P1) tweak up of AV meth. using random walk may fail (slow)
Craig Carey
research at ijs.co.nz
Sat Jan 22 21:07:27 PST 2000
---
Topic: Finding Quotas for Losers in the AV method using Random Walks may
run into a slowness-of-computers problem.
I tested a method to improve the Alternative Vote method (STV with one
winner). I would have added quotas for losers that sometimes caused
more than one candidate to be rejected at each stage. This ought reduce
the weight of Lord Alexander's criticisms of the method. However, both
a symbolic and numerical-random-walk style of finding the quotas could
run into problems. Too slow. The symbolic algebra option is not ruled
out, since (P1) failures can be seen at a glance (e.g. the formula for
B-wins is under great suspicion if it contains "(a+ab<c+ac)", or:
"(a+b+c<3d)").
(This month and last), I wrote a program in REDUCE to randomly walk through
a tetrahedron, of which each corner represents the count of votes for these
papers: AB, AC, B, C. (Using 9 papers for the 3 candidate election was
too slow).
The walks were random but along directions parallel to edges, and they
were only in directions where aa (P1) failure might occur. E.g. if the
losing candidate considered (and picked randomly from the two), was B,
then the direction would be one of the 2 following changes:
1:AB-> t:AB+u:AC, 0<=t+u<=1
1:B -> p:AB+q:AC+r:B+s:C, 0<=p+q+r+s<=1
At every 4th step the 4 numbers were randomised again.
The iteration stopped when a (P1) failure was detected. An example is
below.
The method tested was the Alternative Vote (i.e. STV, 3 candidates, 1
winner)
What I found was that it took 3,289 iterations before it could find a
(P1) failure in STV.
I had intended to deduce the best quotas for the Alternative Vote
method, say for 4,5,6 candidates, by trying quotas there were a little
too small, and a little too big. But clearly as the quota for rejecting
candidates gets nearer the correct quota (if there is one), then the
number of iterations increases a lot.
It seems clear that finding what the quotas should be numerically is
going to far too slow unless the algorithm is particularly well designed
or some significant improvement is made to the random walk method.
Here's a copy of the final output.
My "P1-AV-Quotas" program found a (P1) failure after 2-4 hours (lost)
on a 166MHz Pentium machine.
> 3287 (P1) wrt. c, oldWinner=b, newWinner=b, sum=96
Sim: ---- sumwin{41} > sumv/(nc-1){48} PASS
Sim: --3, wrt.=3, vs=
[1 {a,b} 25]
[ ]
[2 {a,c} 0 ]
[ ]
[3 {b} 41]
[ ]
[4 {c} 30]
> 3288 (P1) wrt. c, oldWinner=b, newWinner=b, sum=96
<ranodmize>
-- ! Randomising again, sumwin{87} > sumv/(nc-1){76}
-- ! Randomising again, sumwin{76} > sumv/(nc-1){62.500}
-- ! Randomising again, sumwin{56} > sumv/(nc-1){29}
Sim: ---- sumwin{59} > sumv/(nc-1){96.500} PASS
Sim: --3, wrt.=2, vs=
[1 {a,b} 0 ]
[ ]
[2 {a,c} 59.905]
[ ]
[3 {b} 74.095]
[ ]
[4 {c} 59 ]
> 3289 !FAILED: (P1) wrt. b, oldWinner=c, newWinner=b, sum=193.00
119: oldvs;
[1 {a,b} 0 ]
[ ]
[2 {a,c} 52]
[ ]
[3 {b} 82]
[ ]
[4 {c} 59]
120: vs;
[1 {a,b} 0 ]
[ ]
[2 {a,c} 59.905]
[ ]
[3 {b} 74.095]
[ ]
[4 {c} 59 ]
The simulation is correct, that is an example proving that the AV method
fails (P1), since shifting votes away from candidate B makes B win
(and C lose) in the Alternative Vote.
The largeness of the number 3,289, suggests that random walks show that
(P1) failures may be a small defect in the AV.
The AV method has remains unimproved. Doesn't Java handle lists(?) like
REDUCE. (Java's arrays are a bit simple compared to Ada 95's).
I don't know if a (say) 10 candidate AV method can be made to pass a
(P1) test, just by adding quotas for losers into the method.
Mr G. A. Craig Carey.
More information about the Election-Methods
mailing list