Stéphane Rouillon wrote:
Hi,
for an anti-fraud purpose, the capacity to repeat the counting operation
is a must.
Hence I recommand to use a reproductible random procedure to break ties.
This allows the use of different computers to reproduce the counting
operation, while always obtaining the same result despite ties.
This is a somewhat late reply, but here's my suggestion:
For a ranked ballot method, use Random Voter Hierarchy, as by the MAM
definition, to construct a tie-breaker ordering (ranked ballot). When
you encounter a tie, use that ordering. If it's a multiwinner method,
invalidate the tie-breaker after a candidate has been elected, and use
roulette wheel selection based on reweighted values when constructing
the random voter hierarchy.
To make the randomness reproducible, there are two methods to do so. The
first would be to use a strong cryptographic hash, say SHA-256. Each
candidate can submit a string, and those strings are all sorted and
concatenated, then fed through the hash. The result is used as a seed
for a pseudorandom RNG. In case no candidate bothers to submit a string,
the list of strings should start off with some variables, like the year
of the election, or perhaps some easily verifiable data of higher entropy.
The second is simpler. After the ballots have been gathered, but before
the election, have the candidates watch a lottery machine. Use its
output, which is made public, as a seed for the RNG.
If you really want to overdo it, you could also translate the ranked
ballots to integers, then feed all those integers through the hash. Sort
candidates alphabetically. The problem with this way of doing it is that
if there's even one miscount, then the hash will be different when the
audit's done.
As an example of why Random Candidate can't be used even with cloneproof
methods, consider this election. We'll use Schulze, which is cloneproof.
10: A > B > C
10: B > C > A
10: C > A > B
Classic three-way tie. Random candidate gives A, B, or C with 1/3
probability (as is fair). Now, let's clone A.
10: A1 = A2 = A3 = A4 > B > C
10: B > C > A1 = A2 = A3 = A4
10: C > A1 = A2 = A3 = A4 > B
Schulze returns A1 = A2 = A3 = A4 = B = C. So the tiebreaker decides.
With Random Candidate, the A group has probability 4/6, with B at
probability 1/6, and C at probability 1/6. Thus, cloning paid off for A.
There would be a slight problem here with Random Voter Hierarchy, since
it'd have to go through all the ballots in order to find out that A1 =
A2 = A3 = A4 on everybody's ballot; thus the process would be lengthy
and difficult to audit correctly.
----
Election-Methods mailing list - see http://electorama.com/em for list info
