[EM] Fw: IBCM, Tideman, Schulze - Reply Part 2

[Norman Petry]

This is a continuation (part 2) of my response to Steve Eppley from a few
weeks ago.

N.

**********

Steve Eppley wrote:

>   But in what sense of "majority" can it be said that a
>   majority has "rejected" A, without also being able to say
>   a majority has "rejected" B?  A's only defeat is EA51,
>   which is shaky (smallest majority in a cycle).  Compare
>   that to B's CB65 defeat, which isn't counted against B.
>   (Blake Cretney made a similar analysis of this issue
>   on 1/24/2000, noting that the Schulze method neglects
>   "extra" information contained in the votes which may
>   undermine links in a beatpath chain.  Markus considers
>   this neglect a "feature" of the Schulze method, but it
>   makes sense to view it as a minor bug.)
>

I don't think this is a strong argument.  All of the candidates are beaten
by pairwise majorities, yet we must pick one.  The magnitude of B's loss to
C is of no particular consequence, unless there would be some good reason
why C could reasonably be considered a potential winner.  Otherwise, it may
well be irrelevant information.  Furthermore, candidate B is tied with
candidate E, which beats A by one vote.  Therefore, I don't see A's win
against B to be particularly convincing (and it isn't even the opinion of an
absolute majority, apparently).

>   An argument might be made that a beatpath is not just an
>   abstraction, that it is comprised of real voters too.
>   But that's a dubious argument.  Consider this simple
>   scenario to illustrate:
>      35: ABC
>      33: BCA
>      32: CAB
>      Majorities: BC68,AB67,CA65
>   The strongest beatpath of length two or more is ABC67.
>   Who are the "real voters" counted in the ABC beatpath?
>   The AB67 link includes 32 voters who rank C over A, and
>   the BC68 link includes 33 voters who rank C over A.  The
>   strength of a beatpath depends on voters who would oppose
>   the beatpath, and thus are not real voters. (This sort of
>   example is one of the concerns I have about how hard it may
>   be to convince people about the merits of the Schulze method,
>   because there's something "smelly" about counting for a
>   beatpath some voters who oppose the beatpath.)
>

I agree with you that the beatpath is an abstraction which cannot really be
justified on the basis of actual votes.  However, one way to think of
beatpaths is as part of an algorithm for resolving ties in methods like SD
and SSD, which are methods that _do_ have a rationale that is as
straightforward as Tideman.  Schulze's beatpath method is equivalent to both
these methods when there are no tied values in the matrix, and can be shown
to perform better than either of those methods when there are ties.  One can
also argue for Schulze's method simply on the basis of criteria
compliance -- some electorates might not care if the abstraction is
meaningful, so long as the method is guaranteed to give good results.

[...]

>
>Here's another criterion which might not be considered very
>important.  But it seems desirable and it distinguishes between
>MTM and Schulze:
>
>   Define the "1st place finisher" as the given method's winner.
>   Define the "Nth place finisher" as the alternative which
>   would be chosen by the given method if preferences for the
>   1st thru (N-1)th place finishers were neglected.
>
>   Immunity From Squawking criterion:  The 2nd place finisher
>   must never beat the winner pairwise.
>
>Another criterion which distinguishes between MTM and Schulze is
>the Subsequence Invariance criterion I posted in February (which
>Markus kindly informed us was not original, indicating there are
>other people who place some value on it).
>
>There is a weaker form of Subsequence Invariance which Schulze
>also fails: "The outcome must not change if preferences for the
>last place finisher are neglected."  Assuming that a candidate
>who expects to finish last has the least incentive to compete,
>it would be nice if the outcome is unaffected by his/her
>decision whether or not to compete.  Thus, this appears to be a
>desirable criterion (though it might not be considered very
>important).

I agree that these criteria are somewhat desirable.  It is not surprising
that Tideman satisfies them and Schulze doesn't since all these criteria
have to deal with social rankings.  Since the goal of Tideman is to find a
single winner by constructing an optimal social ranking, and choosing the
candidate at the head of it, one would expect Tideman to do better than
Schulze.  However, as Markus has pointed out, the goal of single-winner
methods is to elect a single winner, not construct a social ranking, so I
don't really attach too much importance to these criteria.  With Schulze's
method, there is no 2nd-place finisher, merely 1 winner and a bunch of
losers.  One or more of the losing candidates may beat the winner pairwise,
but when this happens the 'squalking' candidate will also have been
majority-beaten, so doesn't really have much of a case, imho.

If I was choosing a method to determine a social ranking, I would definitely
prefer Tideman over Schulze, because it does have the desirable properties
you mention.  However, the applications for social rankings are quite
limited.  If a group needs to choose a single-winner, the social ranking is
irrelevant.  If a group needs to choose multiple winners, a PR system like
STV is almost always more appropriate.  The only use I've thought of so far
for social rankings is when one needs to determine in advance a list of
people from which only one person at a time will be chosen to carry out some
function.  For example, if a group had a system of elected kingship, the
citizens could create a social ranking of all the eligible citizens.  Should
the (top-ranked) king be killed or otherwise eliminated between elections,
the next in line could be chosen.  Are there any other good uses for a
social ranking?

[...]

>
>> whereas Schulze's method is the only method (that I'm aware
>> of) that has been proven to satisfy one strong formulation of
>> Clone Independence criteria. Tideman satisfies a weaker
>> definition of clone independence, SD is 'mostly' clone
>> independent, but fails in rare cases;
>
>I'm not aware that IBCM or Tideman fail to satisfy the stronger
>form of clone independence.  I do recall that a couple of years
>ago there was a discussion in EM about Tideman, which didn't use
>the RandomVoterHierarchy tie-breaker discussed later for
>Schulze's method.  Also, that discussion may have been about
>Tideman's 1987 version, not the better version defined in Zavist
>& Tideman's paper, "Complete Independence of Clones in the
>Ranked Pairs Rule." (Social Choice and Welfare, 1989).  If
>RandomVoterHierarchy is the tie-breaker, aren't IBCM and MTM
>completely independent from clones, in whatever "strong"
>formulation Norm referred to?
>
>Markus tweaked Tideman's definition of clones and demonstrated
>independence of "tweaked" clones of the Schulze method.  But
>that tweak was not a strengthening of the independence
>criterion.  It was a weakening.  It seems to me that MTM and
>Tideman and BCM and IBCM completely satisfy it (when coupled
>with a tie-breaker such as RandomVoterHierarchy which completely
>satisfies it).
>

I don't see how Markus' definition of clones weakened it.  Markus used a
definition of clones that allows for ballots which contain candidates
outside clone sets to be ranked equal to clone sets.  That is, if
{A1,A2,A3,B,C} are candidates and {A1..A3} are clones, ballots like
[A1=A2=A3=B>C], [C] are permissible, whereas under Tideman's more
restrictive definition they are not.  Therefore, Markus' definition of
clones is the stronger, more general purpose, and more useful definition.

Note that I am not saying that Tideman's method with an appropriate
tiebreaker will not also satisfy Schulze's definition of clones!  It may be
that it does, but I haven't yet seen proofs of this.  Here is what Markus
wrote about the two definitions of clone criteria on 26 Aug 1998:

*****

Quoting Tideman, Norman wrote (25 Aug 1998):
> "A proper subset of two or more candidates, S, is a set
> of clones if no voter ranks any candidate outside of S
> as either tied with any element of S or between any two
> elements of S."

To my opinion, Tideman's definition is too weak. I prefer
the following definitions (3 Oct 1997):

Definition ("clones"):

   A[1],...,A[m] are a set of m clones if & only if

   for each pair (A[i],A[j]) of two candidates
   of the set of m clones,

   for each voter V, and

   for each candidate C outside the set of m clones

   the following statements are valid:

   V prefers A[i] to C, if & only if V prefers A[j] to C.
   V prefers C to A[i], if & only if V prefers C to A[j].

Definition ("Generalized Independence of Clones Criterion"):

   A voting method meets the "Generalized Independence
   of Clones Criterion" if & only if additional
   clones cannot change the result of the elections.
   [If one clone is elected instead of another clone of the
   same set of clones, then this is not regarded as a change
   of the result.]

The aim of clone criteria is to verify, whether a method can
be manipulated by presenting additional candidates with
absolutely identical opinions. Tideman's definition of clones
is too strong (because he supposes that clones must no be
ranked identically to non-clones by any voter), so that
his definition of clones is -to my opinion- not meaningfull
enough.

Markus Schulze

*****

>I'd like to see an example showing incompleteness of the clone
>independence of Tideman//RandomVoterHierarchy, if there is one.
>(Preferably an example for the majoritarian version of Tideman.)
>

Since Tideman proved 'complete' independence of clones based on his own,
inferior definition, I would like to see proofs that Tideman's method
satisfies Markus' definition of clones before I'd consider it equally good
in this regard.  If I have time, I'll try to construct an example of Tideman
violating Markus' version of clone independence, although I have no
particular reason to think it does.

>> IBCM and Tideman both violate Beatpath GMC, etc.
>
>Why place any importance on Beatpath GMC?  It's a criterion
>lacking a reasonable justification -- see above.  Mike Ossipoff,
>the "father" of GMC, has repudiated both GMC and Beatpath GMC,
>concluding that they are overly strong.
>

What I found appealing about the GMC criteria was that they offered
additional guarantees to the voter that seemed reasonable.  Regular GMC, for
example, sets a higher standard for majority rule -- if a method is going to
elect someone, then that candidate should not be opposed by an overall
majority unless all candidates are.  Beatpath GMC is less intuitive, but
provides a similar guarantee without requiring violation of reversal
symmetry criteria, Smith, etc.  As you say, Mike has repudiated these
criteria, and I understand that they were promoted primarily for the
strategy protections they provided (which are satisfied by BC), and not the
above benefit, per se.

[lots of math...]

>So, assuming no significant errors have been made in the lemmas
>or the propositions, it is accurate to say that IBCM is
>completely independent of clones (recognizing that a tie-breaker
>which is completely independent of clones is implied by the
>claim).
>

Sounds good.

>> 2) is IBCM monotonic? (Markus suggested that it might not be)
>
>No, IBCM is not completely monotonic. (BCM is monotonic, but no
>one is advocating BCM.  Proof of BCM monotonicity is available
>upon request.)
>

Sounds bad (for IBCM I mean).

>So it makes sense to lower IBCM and consider MTM #1.  For one
>thing, like IBCM, MTM has a significant edge over Schulze in the
>head-to-head comparison.  (See my data above.)
>

I agree with you that majoritarian Tideman is an excellent method.  I'm not
convinced it's superior to Schulze, but I currently think it is probably
about equally good.

[...]
>
>I think Norm has misjudged Tideman technically on clones. (See
>above.)  Also, I think there is no reasonable justification for
>Beatpath GMC. (See above.)  So MTM (majoritarian Tideman) is
>better than Norm has suggested.
>

You might be right about the clone issue.  I still want to see proofs or
counterexamples that Tideman satisfies (or does not satisfy) Markus'
definition of clones, in addition to Tideman's.

>I agree with Norm's conclusion that Tideman (more specifically,
>MTM) and SD might make better public proposals than Schulze.
>
>SD & SSD are not completely independent of clones, but I think
>they are practically independent in large public elections.  I
>think SD is not completely monotonic (example below) but is
>practically monotonic.  I don't know if SSD is completely
>monotonic, but below I provide an argument against proposing SSD.
>

You raise an interesting question about clone independence and SSD.  One
advantage that Mike cited for SSD being possibly better than Schulze was
that it was decisive in situations like this:

A>B>C>D 4
B>C>A>D 2
C>A>B>D 3
D>A=B=C 9

(Mike actually described an example with 2, 3-candidate cycles that are
tied, but this is simpler and illustrates the same point).

In this example, SSD will decisively choose D, whereas Schulze can only
reduce the winner to {A,D} before having to rely on a random ballot
tiebreaker.  However, it appears to me that this is a stochastic violation
of clone independence. {A,B,C} are clones, and are tied 9:9 with a
non-clone.  The only solution which preserves clone independence is to
choose between A (or a clone of A) and D with equal probability.  Therefore,
I think that SSD is inferior to beatpath Schulze precisely because it is
decisive when it shouldn't be, and violates clone criteria as a result.

>It would also be useful to know whether [Schulze] & [MTM] are
>monotonic, since [MTM] is more decisive than MTM, and [Schulze]
>is more decisive than Schulze.  (The [] notation is defined in
>the accompanying message "Useful Propositions...")
>
>Here's an example which, if I haven't erred, shows that SD is
>not completely monotonic:
>
>   Definition of SD:
>   Repeat while no alternative is unbeaten:
>      Discard the non-discarded defeat(s) which is smallest
>      in some unbroken cycle.
>   Elect the unbeaten alternative(s).
>
>   Example of SD non-monotonicity:
>   Small majorities:  AC51,CB52,BA53,DB53,GA54
>   Larger majorities: AD,FC,CE,EF,AH,HG
>   (All other pairings are pairties.)
>
>   First AC51 is dropped.  Then BA53 and DB53 are dropped.
>   (CB52 is not dropped because the cycle it is in was broken
>   by the dropping of AC51.)  Then GA54 is dropped and A has
>   become unbeaten, so SD chooses A.
>
>   Assume that at least 3 voters ranked A just below C.
>   Suppose 3 of them uprank A over C, giving AC54.
>   Now AC is not the smallest majority of any cycle;
>   CB52 is the smallest majority of the A>C>B>A cycle.
>   First CB52 is dropped.  Then BA53 and DB53 are dropped
>   and B has become unbeaten, so SD chooses B.
>
>   (I didn't attempt to find an example having fewer
>   alternatives or fewer pairties.)
>

In my implementation of Sequential Dropping, I always assume that defeats
within cycles are broken one at a time.  If there are multiple defeats of
the same strength (such as your BA53, DB53 in the example above), a tbrc is
used to select only one of the defeats at a time for removal.  This is
needed anyway in order to eliminate the possibility of more than one
candidate being elected.  If this is done, then depending on the tiebreaker,
the SD winner in the above example will either be:

1) A before *and* A after, or
2) C before and B after.

In neither case is there a violation of monotonicity.  I also checked a
variety of other methods with this example, and came up with the following
results:

Tideman: C->B, or A->A == monotonic
SSD: C->B always == monotonic
Goldfish: C->A, or C->B == monotonic
Schulze: C->B always == monotonic
IBCM: A->B always == not monotonic!

Schulze and SSD produce the most consistent results with this example, but
only IBCM violates monotonicity.  This example illustrates how the Schulze
method has an advantage over the alternatives, in that the tiebreaker is
applied very sparingly, and only once after the beatpath calculation is
complete.  In most cases, it won't be needed at all despite the presence of
pairties in the matrix.  In contrast, Tideman, SSD, SD, and Goldfish may all
require the tiebreaker to be repeatedly applied at various points as a
solution is sought, and the result is less consistency in outcomes.
Particularly in small-scale elections where pairties will be common, the
results will be more dependent on the tiebreaker and less dependent on the
core of the method, and this seems undesirable to me.  I think this is a
potential problem for Tideman, SD, and SSD, because although it may be easy
to get voters to agree with the base method, they may balk at using a
particular tiebreaker.  For example, is it going to be easy to explain the
rationale for using a random ballot tiebreaker?  If anything else is used,
then Tideman is no longer clone independent.  Schulze on the other hand is
inherently clone independent *and* very decisive, so that the tiebreaker
chosen is relatively unimportant.  A random ballot tiebreaker is still
desirable (for perfect, stochastic clone independence), but not strictly
necessary.  This may make the Schulze method more easy to promote.

For example, the Debian Project (http://www.debian.org) has a pairwise
voting method which includes a constitutional rule that states:

"In the case of ties the elector with a casting vote will decide. The
casting vote does not count as a normal vote; however that elector will
usually also get a normal vote."

(the 'elector with a casting vote' is usually the Debian Project Leader).

If they were to consider adopting one of our best methods (Tideman,
Schulze), I wouldn't feel the need to press them to replace this rule with a
random ballot tiebreaker if Schulze was proposed, but I would be reluctant
to recommend Tideman without scrapping this rule, due to the importance of
the random ballot in making Tideman a high-quality method.  I think this is
a serious concern with groups like Debian, since their elections normally
have 100-200 voters (or less), so there is a reasonable probability of ties.
In committee work it would be absolutely essential.

>SD's definition says that cyclicity is recalculated each
>iteration, to identify the "unbroken" cycles.  Another method
>can be defined which is similar to SD, except that it calculates
>cyclicity only once, at the beginning:
>
>   Definition of SD2:
>   Repeat while no alternative is unbeaten:
>      Discard the non-discarded defeat(s) which is smallest
>      in some broken or unbroken cycle.
>   Elect the unbeaten alternative(s).
>
>SD2 may be worth examining.  I expect it will behave similarly,
>but not identically, to TopCycle//PC(wv), and it is probably
>monotonic.  It clearly satisfies top cycle, and perhaps it
>performs as well as SD on clones (practical independence of
>clones in large public elections.)
>

I'll try adding this one to my simulator when I find some free time, and let
you know how it performs.

>It would be advantageous if the method proposed for large public
>elections is also the method proposed for small groups.  It will
>probably be the case that some private groups would choose to
>adopt a good method before it's adopted by the public, and would
>then spread knowledge about their experiences with it.  So there
>may be useful synergies if the same method is proposed for both.
>This consideration implies that IBCM & SD, which are not as good
>for small groups, should not be the public proposal.  This
>leaves MTM, Schulze, and perhaps SSD.  (Also [MTM] and [Schulze]
>since they are more decisive, assuming they are monotonic, and
>maybe even if they're not completely monotonic since the extra
>decisiveness may be more important in small groups.)
>

I agree that there is some advantage to promoting the same method for all
uses.  However, Schulze can be seen as simply a refined form of SD or SSD,
so I think if it is presented that way, there wouldn't be that much problem
extending support from using Schulze on the small scale to SD for public
uses.  Schulze can be seen as a way to resolve ties in SD which preserves
clone independence.  In the same way, the random-ballot tiebreaker needed
for Tideman probably wouldn't be discussed as part of the public proposal,
one could ignore the Schulze refinement when discussing SD.  All that needs
to be said is that SD elects the same winner as Schulze when there aren't
any ties.  I do concede that this is a (perhaps small) advantage of
Tideman's method.

>SSD's definition doesn't seem nearly as simple as other methods,
>since it refers to the (dynamically recalculated) Schwartz set.
>Given that plus its iteration, people may find SSD hard to
>understand, maybe even harder than Schulze, and if that's true
>then SSD offers nothing Schulze doesn't offer.  Mike said that
>he found a person who liked SSD's definition more than SD's, but
>that's not a large enough sample to reach a conclusion.
>

I agree that SSD isn't simple enough for a public proposal, and isn't quite
good enough (compared to Schulze) for committee work.  It does offer an
alternate way of understanding the Schulze method, however so is still
useful as a tool for explanation.  Mike could be right about SSD being more
appealing than SD, but as you say, we would need more test cases.  I think
that SSD is perhaps easier to understand visually, but is quite difficult to
understand when described on paper.  Because it is defined in terms of sets
rather than cycles, that may make it easier to understand.  However, I do
not see how you can explain the Schwartz or Smith sets without explaining
beatpaths, and once you've done that, the possibility of cycles needs to be
considered anyway.  At this point, SD offers the easiest solution.


Norm Petry


>
>---Steve     (Steve Eppley    seppley at alumni.caltech.edu)
>
>
>
>