[EM] (P1) tweak up of AV meth. using random walk may fail (slow)

[Craig Carey]

---

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.