[EM] Random and reproductible tie-breaks

[Kristofer Munsterhjelm]

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.