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

[Bart Ingles]

Craig Carey wrote:

> The problem is, find the quotas that give the best method.
> It seems to be just the sort of thing the UK electoral reform group
>  (I forget the name of it), should have done and finshed many years or
>  even decades, ago.

The use of quotas seems to be a trade-off.  From the perspective of
trying to maximize social utility, a quota would seem to improve
performance of IRV in worst-case scenarios, while reducing best-case
performance by unnecessarily eliminating consensus candidates.


Example 1: worst-case performance improved:

     Voter Utilities
     1.00                          0
     --------------------------------
499   A                          C B
250   B                          C A
251   C                          B A

Here B and C are both eliminated, so average utility is nearly 0.5 (same
as FPP).  Under IRV the average is barely 0.25.  Condorcet as bad as IRV
in this scenario (but could be much worse in others, with no minimum
utility).


Example 2: best-case performance reduced:

     Voter Utilities
     1.00                          0
     --------------------------------
499   A C                          C
250   B C                          A
251   C B                          A

Here IRV would have yielded an average utility of nearly unity.  IRV
with a quota of 1/n eliminates the consensus candidate, and again yields
an average utility of just under 0.5.


The problem in example 1 becomes more pronounced with large numbers of
candidates, since minimum average utility for IRV is 2^(1-n).  The quota
1/n becomes very small as well, but is the best that can be guaranteed
under any method.

Adding a small constant to the quota's denominator makes little
difference with large numbers of candidates, but would reduce the effect
of the quota when there are few candidates remaining.  A quota of
1/(n+1) would be nearly the same as Craig's AV1 with a large number of
candidates, but would have no effect in the three-candidate examples
above.

Still not as good as approval voting, of course, but probably an
improvement over IRV.