[EM] Cloneproof SSD

[Markus Schulze]

Dear Mike,

Example:

   30 voters vote A > B > C.
   30 voters vote B > C > A.
   30 voters vote C > A > B.

   Suppose, that candidate C is substituted by a large number
   of clones and that the strength of a pairwise defeat
   between two clones is always below 60:30.

If pairwise defeats were dropped randomly then the probability
that one of the clones was elected would increase with the
number of clones. The same is true when the strength of the total
violation was measured in a lexicographical manner (as Steve
Eppley suggested for his MTM method).

******

Suppose that there are n pairwise defeats of equal strength.

Suppose that Tideman's Ranked Pairs method is used. The reason why
you have to check all n! ways to consider one defeat after the other
and cannot simply consider all n pairwise defeats simultaneously is
simply the fact that it could happen (1) that these pairwise defeats
lock in a cycle when you lock all them simultaneously and (2) that
the Tideman method doesn't terminate when you skip all these pairwise
defeats simultaneously.

However, when the Schwartz set heuristic is used then it is the
same whether all n! ways to drop one pairwise defeat after the
other is checked or whether all n pairwise defeats are dropped
simultaneously.

******

The winner of the Schwartz set heuristic and the winner of the
beat path heuristic can differ only when there is at least one
pairwise tie.

Example:

   A:B=50:50
   A:C=35:25
   B:C=40:60

The Schwartz set heuristic would choose candidate A because
candidate A is the unique Schwartz winner. The Schwartz set
heuristic treats all pairwise ties in the same manner.

The beat path heuristic would choose candidate C because beat
paths must be able to contain pairwise ties. Otherwise it would
be possible that there is neither a beat path from candidate X
to candidate Y nor from candidate Y to candidate X.

[However, when margins were being used then both heuristics
would always choose the same winner.]

Markus Schulze