[EM] Cloneproof SSD

[Norman Petry]

On January 15th, Mike Ossipoff proposed the following method ('Cloneproof
SSD'):

>
>Drop the weakest defeat that's among the Schwartz set. Repeat till
>there are no cycles in the Schwartz set. Whoever is unbeaten at that
>time wins.
>
>[end of definition]
>
>This avoids the problem of a clone set being cheated out of its
>opportunity to be in a randomly-solved tie, due to cyclic defeats
>among the clone set.
>

When I first read this description, the idea of breaking *all* the cycles,
rather than doing it one at a time seemed familiar.  Doing a little digging
in the EM archives, I discovered that the *core* of Mike's new method
(ignoring the Schwartz set computation) has been proposed a number of times:

1. On August 3, 1998 I proposed a method I called 'Reverse-Tideman':

>From: "Norman Petry" <npetry at sk.sympatico.ca>
>To: <election-methods-list at eskimo.com>
>Subject: Re: Tideman Problem
>Date: Mon, 3 Aug 1998 19:53:25 -0600
[...]
>Your bad example just gave me an idea though -- what would happen if we
>turned Tideman on it's (his?) head to create a "Reverse-Tideman"?  By this
I
>mean: basically, Tideman's method is to begin with the strongest
>propositions and ignore contradictions.  Your example shows that this might
>result in an important, strong proposition being ignored.  What would
happen
>if we instead started with the weakest propositions, and reversed our
>earlier judgements as often as necessary as we worked our way up to the
>strongest?  That might break your bad example, and we might not need to
>resort to the "Improved Tideman" which needs to backtrack over the
>previously skipped propositions to be (potentially) as good as Schulze.

2. On February 15, 2000, Mike proposed a similar method, called 'Drop
Contradicted Defeats' (DCD):

>From: DEMOREP1 at aol.com
>Message-ID: <c.165da24.25db6683 at aol.com>
>Date: Tue, 15 Feb 2000 21:33:39 EST
>To: election-methods-list at eskimo.com, nkklrp at hotmail.com
[...]
>Forwarded from Mike Ossipoff <nkklrp at hotmail.com>--
>-------
[...]
>That meets your obviousness standard. What's an obvious rule, then,
>when there's a circular tie? How's this for obvious?:
>
>"Get rid of cycles by dropping the weakest defeat in each cycle".
>
>This extremely obvious & simple rule could be called:
>"Drop Contradicted Defeats" ("DCD").
>

3. Steve Eppley has also proposed an equivalent method he called the
'Beatpath Criterion Method' ('BCM'):

>From: "Steve Eppley" <SEppley at alumni.caltech.edu>
>To: election-methods-list at eskimo.com
>Date: Wed, 23 Feb 2000 12:37:29 -0800
>Subject: Beatpath criterion, Tideman, and BCM (was Re: [EM] Tideman and
GMC)
[...]
>
>   Beatpath Criterion (BC)
>   -----------------------
>   Let Vij denote the number of voters who ranked i ahead of j,
>   for any pair of alternatives i&j.
>
>   Let Bji denote the strength of the strongest beatpath
>   from j to i, for any pair of alternatives i&j.
>
>   If Vij > Vji and Vij > Bji then j must not finish ahead of i.
>
[...]
>
>   Beatpath Criterion Method (BCM)
>   -------------------------------
>   For all pairs i&j,
>      if Vij > Vji and Vij > Bji then eliminate j.
>

As Markus Schulze pointed out in a private message to me on August 4, 1998,
this method has been also proposed many times in the academic literature:

4. Young's Method:

>From: "Norman Petry" <npetry at sk.sympatico.ca>
>To: "Markus Schulze" <schulze at sol.physik.tu-berlin.de>
>Cc: <election-methods-list at eskimo.com>
>Subject: "Reverse-Tideman" Idea Explained
>Date: Tue, 4 Aug 1998 10:37:34 -0600
[...]
>>From: Markus Schulze <schulze at sol.physik.tu-berlin.de>
>>To: npetry at sk.sympatico.ca <npetry at sk.sympatico.ca>
>>Date: August 4, 1998 6:31 AM
>>Subject: Re: Tideman Problem
>>
[...]
>>> proposition being ignored. What would happen if we instead started
>>> with the weakest propositions, and reversed our earlier judgements
>>> as often as necessary as we worked our way up to the strongest?
>>> That might break your bad example, and we might not need to resort
>>> to the "Improved Tideman" which needs to backtrack over the
>>> previously skipped propositions to be (potentially) as good as
>>> Schulze.
>>
>>As far as I understand you correctly, you propose
>>that the weakest pairwise defeats should be ignored successively
>>until there are no cycles anymore.
>>
>>In literature, this has been proposed many times (especially by
>>Peyton Young). Unfortunately, it doesn't work as expected.
>>
>>Example:
>>
>>  19 voters vote A > D > B > C.
>>  17 voters vote B > C > A > D.
>>  16 voters vote C > A > D > B.
>>  16 voters vote D > A > B > C.
>>  16 voters vote C > D > A > B.
>>  10 voters vote D > B > C > A.
>>  06 voters vote B > C > D > A.
>>
>>  A:B=67:33
>>  A:C=35:65
>>  A:D=52:48
>>  B:C=68:32
>>  B:D=23:77
>>  C:D=53:47
>>
>>  There are still cycles (e.g. A > B > C > A,
>>  D > B > C > D, A > D > B > C > A).
>>  A:D=52:48 is the lowest defeat in a cycle,
>>  thus A > D is ignored.
>>
>>  Now, we have:
>>
>>  A:B=67:33
>>  A:C=35:65
>>  B:C=68:32
>>  B:D=23:77
>>  C:D=53:47
>>
>>  There are still cycles (e.g. A > B > C > A,
>>  D > B > C > D).
>>  C:D=53:47 is the lowest defeat in a cycle,
>>  thus C > D is ignored.
>>
>>  Now, we have:
>>
>>  A:B=67:33
>>  A:C=35:65
>>  B:C=68:32
>>  B:D=23:77
>>
>>  There is still a cycle (A > B > C > A).
>>  A:C=35:65 is the lowest defeat in a cycle,
>>  thus A < C is ignored.
>>
>>  Now, we have:
>>
>>  A:B=67:33
>>  B:C=68:32
>>  B:D=23:77
>>
>>  Now, we have no cycles anymore.
>>  But there are two candidates (A and D), who
>>  each wins every not-ignored head-to-head pairing.
>>  Who should win?
>>

As Markus, Mike, and Steve all observed, the problem with Peyton Young's
method (I'll refer to it as "Young's Method" from now on) is that it is not
sufficiently decisive.  Breaking all cyclic ties, rather than just breaking
one cycle at a time (the way SD and SSD do) will usually result in more than
one undefeated candidate when there are more than 3 candidates in the Smith
set.  Up to now, all the proposals for dealing with this problem have
suggested that the way to resolve it would be to reduce the set of eligible
candidates to only those which are unbeaten once all the cycles have been
broken, and repeating the process until a single-winner is found.  Here is
Steve Eppley's description of this 'Iterated' version of Young's Method:

>By itself, BCM isn't as decisive as we'd like.  But here's a
>variation which is quite decisive:
>
>   Iterated Beatpath Criterion Method (IBCM)
>   -----------------------------------------
>   Repeat BCM, neglecting preferences regarding eliminated
>   alternatives, until decisive or until further repetition
>   won't eliminate more alternatives.
>

Mike's 'Cloneproof SSD' proposal is very similar to this 'Iterated Young'
method (Steve Eppley's 'IBCM'), except that rather than breaking cycles
involving *all* the candidates, we first restrict the set of eligible
candidates to the members of the Schwartz set, and then apply Young's
method.  If there is more than 1 winning candidate, the set of eligible
candidates is reduced and the overall procedure repeated until a single
winner is found.

Note regarding compound methods (for newcomers):

Long ago on this list, a notation was developed to represent compound
methods.  The way this works is that a voting method can be regarded as a
type of filter, which takes as inputs a set of ballots and a set of
candidates, and produces as an output a (hopefully smaller) set of 'winning'
candidates.  These filters can then be chained to produce any sort of
compound method (provided they use the same ballot type).  The symbol '//'
is used to represent the 'pipe' connecting these filter stages.  Using this
notation, Mike's new method could also be called:

"Iterated Schwartz//Young"


*****

Here's my initial analysis of "Cloneproof SSD":

1. CLONE INDEPENDENCE:

The first thing I thought should be checked about this new method was
whether or not it satisfied the Independence of Clones Criterion (ICC).  If
it didn't, there would be nothing to recommend it over the simpler SSD,
which is *nearly* clone independent.

The good news is that Cloneproof SSD does appear to be fully Clone
Independent, and it should be possible to prove that it satisfies ICC.  I
used the voting methods simulator I had developed ('VoteSim') to check for
clone independence failures with this method (using a ballot-based
tiebreaker, as is required with Tideman's method), and could not discover
any over a great many trials with a large number of candidates.  Of course,
simulations can only yield examples which *disprove* compliance with a
criterion, so a proof would be better.  Nevertheless, I no longer have no
doubt that ICC is fully met by this method.


2. MONOTONICITY:

The bad news about Cloneproof SSD is that the method is not monotonic.  I
had suspicions that this might be the case, since it was known that
'Iterated Young' (IBCM) was not monotonic, and the two methods are very
similar (refer to Steve's Eppley's message, "Fw: IBCM, Tideman, Schulze",
Fri, 2 Jun 2000 17:12:51 -0800 for the example).

Here is an example showing Cloneproof SSD's monotonicity failure:

(in this example, the notation  AC34 would mean that A has a pairwise
victory over C with 34 votes; only the pairwins are shown, not the pairloss
totals)

***

5 Candidates: {A,B,C,D,E}

Pairwise Matrix: AC2, AE7, BA1, BD8, CB3, CD9, CE10, DA4, DE11, EB5

Note that there are no pairties or equal defeats.  All candidates have at
least one defeat.  Therefore, the Schwartz set and the Smith sets are equal,
and consist of all 5 candidates {A..E}.

The Schwartz filter doesn't change the set of eligible candidates, so
Young's method is used to break the cycles until none remain (lowest
pairwins involved in a cycle are eliminated first; cycles are shown in
parentheses).

BA  1 Break (ACB)
AC  2 Break (CDA) - C is now undefeated.
CB  3 Skip
DA  4 Break (AEBD) - A is now undefeated.
EB  5 Break (BDE)
AE  7 Skip
BD  8 Skip
CD  9 Skip
CD 10 Skip
DE 11 Skip

The undefeated options are {A,C}.  Since there is more than one, the
Schwartz set of these options is computed, which consists of {A} only, since
A>C 2.

The Cloneproof SSD winner is A.

***

Now suppose that 4 voters uprank A with respect to C.  That is, AC2 becomes
AC6.  All other pairwins remain unchanged.  Now we have:

5 Candidates: {A,B,C,D,E}

Pairwise Matrix: AC6, AE7, BA1, BD8, CB3, CD9, CE10, DA4, DE11, EB5

Note that again there are no pairties or equal defeats.  All candidates have
at least one defeat.  Therefore, the Schwartz set and the Smith sets are
equal, and consist of all 5 candidates {A..E}.

The Schwartz filter doesn't change the set of eligible candidates, so
Young's method is used to break the cycles until none remain (lowest
pairwins involved in a cycle are eliminated first; cycles are shown in
parentheses).

BA  1 Break (ACB)
CB  3 Break (BDAC)
DA  4 Break (ACD) - A is now undefeated.
EB  5 Break (BDE) - B is now undefeated.
AC  6 Skip
AE  7 Skip
BD  8 Skip
CD  9 Skip
CD 10 Skip
DE 11 Skip

The undefeated options are {A,B}.  Since there is more than one, the
Schwartz set of these options is computed, which consists of {B} only, since
B>A 1.

The Cloneproof SSD winner is now B.

***

Cloneproof SSD therefore violates the Monotonicity Criterion, since a change
in which a handful of voters expressed a stronger preference for one
candidate (A) caused that candidate to lose an election it would have won
otherwise.

Here is a summary of how some other methods perform with this example:

Method        Before    After    Monotonic
Tideman         C         A         Yes
Schulze         C         A         Yes
IBCM            A         B         No
Cloneproof SSD  A         B         No
SD              C         A         Yes*
SSD             C         A         Yes
Young         {A,C}     {A,B}       Yes

*SD is not monotonic, but doesn't fail this particular example.


3. OTHER COMMENTS:

As the above example demonstrates, Cloneproof SSD has more in common with
IBCM than with SSD or Schulze's method.  This is because the performance of
the overall method is largely governed by its 'inner loop' (Young's method)
rather than by the surrounding Schwartz set computation, which is usually
just window-dressing.  I have carried out other some other tests which I
will post shortly that compare a variety of voting methods according to a
measure I call 'dissatisfaction', which is simply the maximum percentage of
voters who would prefer the election of a different candidate in an
election.  By that measure, it becomes obvious that Cloneproof SSD is
actually quite different from SD, SSD, or Schulze, and is much more like
IBCM or Tideman.  As shown above, it also shares IBCM's primary defect of
non-monotonicity.

One of they key advantages cited for SSD is that it may be more readily
understood by a lay-person than either Schulze's method or SD.  This is
because (at least with sufficient hand-waving) it is possible to give a
general idea of SSD without reference to the issue of voting cycles, because
Schwartz is defined in terms of sets of candidates, rather than cycles or
'beatpaths'.  When described graphically, the method appears fairly
intuitive because sets are easy to represent that way.  However, Cloneproof
SSD doesn't share this advantage, since it is impossible to break the cycles
within these sets without recognising their existence.  Therefore, it seems
to me that the only significant advantage of SSD over Schulze's method is
lost in the (admittedly successful) attempt to make the method fully clone
independent.  For this reason, but primarily because the method is not
monotonic, I do not consider Cloneproof SSD to be an acceptable voting
method -- the tradeoff between quality and complexity is simply not good.
If a non-monotonic voting method is acceptable (and it may be for some
uses), "Sequential Dropping" is a much better proposal because:

1) It is much simpler to describe and implement than Cloneproof SSD.
2) Its monotonicity failures are extremely rare (unlike Cloneproof SSD,
IBCM)
3) It does a much better job of minimising 'dissatisfaction'
4) It is one of the Marquis de Condorcet's own proposals, so can rightfully
be called "Condorcet's Method"
5) It yields the same winner as either SSD or Schulze when there are 5 or
fewer candidates in the Smith set, and there are no pairties or equal
defeats*.  This means that it would be practically equivalent to either of
those methods in public elections.

Regular SSD is of course also a very good method, and is even closer to
Schulze's beatpath method in terms of results**.


--
Norman Petry

* This is a result I discovered based on recent testing (today, actually).
** As Mike has pointed out, SSD is equivalent to Schulze for *any number of
candidates* provided there are no pairties or equal defeats.  It is also
completely monotonic.