Clone Independence Criteria

[Markus Schulze]

Dear Norman,

you wrote (26 Aug 1998):
> Thanks for bringing this difference in clone independence criteria to
> our attention.  I had assumed that Tideman's "Independence of Clones"
> criterion was the same as what we've been calling GITC ("Generalised
> Independence of Twins Criterion"), and which you've redefined below
> as "Generalised Independence of Clones Criterion".  I like the term
> "clones" better than "twins", as twins implies only pairs of two (and
> there _are_ twin-independence criteria which some methods satisfy,
> although they fail clone independence), so I'd suggest we use the
> following shorthand nomenclature when referring to these two variants
> in future:
>
> "TICC" - Tideman's Independence of Clones Criterion (Tideman's
> definition)
> "GICC" - Generalised Independence of Clones Criterion (Schulze's
> definition).
>
> Since any method which satisfies TICC also satisfies GICC, but not
> vice-versa, GICC is obviously more useful in practice as a means of
> differentiating voting methods.  One consequence of this difference in
> definitions is that Tideman's method (even the improved form) is
> inferior to Schulze's method in yet another respect -- Tideman's method
> probably doesn't satisfy GICC (to say nothing of GMC!).

To my opinion, there is _no_ need for more than one clone criterion.

Let me explain:

Mike Ossipoff uses a different version of the "Generalized Majority
Criterion" (GMC) like I use. Mike Ossipoff says:

   An election method meets the "Generalized Majority Criterion" (GMC)
   if & only if it never elects a candidate that has a majority against
   him unless every candidate has a majority against him.

I say:

   "X >> Y" means, that a majority of the voters strictly prefers
   X to Y.

   "There is a majority beat-path from X to Y," means,
   that X >> Y or there is a set of candidates
   C[1], ..., C[n] with X >> C[1] >> ... >> C[n] >> Y.

   A method meets the "Generalized Majority Criterion" (GMC)
   if and only if:
   If there is a majority beat-path from A to B,
   but no majority beat-path from B to A, then B must not
   be elected.

The only reason, why I use a different version of the "Generalized
Majority Criterion," is the fact, that Mike Ossipoff's version
is _not_ compatible with the "Local Independence of Irrelevant
Alternatives Criterion" and with any version of the "Complete
Independence of Clones Criterion."

The problem with the "Generalized Majority Criterion" is identical
to the problem of the "Complete Independence of Clones Criterion":

   As long as it can be met and there is no need to relax it
   to get compatibility with a more important criterion, the
   strongest possible version of a criterion should be used.

The only reason -why I mentioned, that my definition of clones differs
from Tideman's definition of clones- is the fact, that Blake considers
situations, where the voters are not decisive about some
candidates (i.e. there are some candidates, such that every voter
ranks all those candidates identically).

My answer: If the voters have absolutely no opinion about the different
alternatives (i.e. every voter ranks every alternative identically),
then the only neutral way to choose the winner is to choose him
randomly. But this means, that it is always advantageous for a party to
present as many alternatives as possible.

If Blake hadn't considered this situation, I wouldn't have bothered you
with this detail. But if you want to relax my version of
"Complete Independence of Clones Criterion," so that it doesn't
suppose implicitely, that the voters are decisive, I want to propose
the following relaxation:

Definition ("clones"):

   A[1],...,A[m] are a set of m clones if & only if the following
   two statements are valid:

   (1) For every pair (A[i],A[j]) of two candidates of this set,

       for every voter V, and

       for every candidate C outside this set

       the following two statements are valid:

       (a) V strictly prefers A[i] to C,
           if & only if V strictly prefers A[j] to C.
       (b) V strictly prefers C to A[i],
           if & only if V strictly prefers C to A[j].

   (2) For every candidate A[k] of this set and
       for every candidate D outside this set
       there is at least one voter W, who either
       strictly prefers A[k] to D or strictly prefers D to A[k].


Definition ("Generalized Independence of Clones Criterion"):

   Suppose, that every candidate of the same set of clones
   is substituted by a single "makro-candidate" A with the following
   properties:

      For every voter V and for every candidate C outside this set
      of clones the following statements are valid:

      (a) V strictly prefers A to C, if & only if V strictly prefers
          the candidates of this set of clones to C.
      (b) V strictly prefers C to A, if & only if V strictly prefers
          C to the candidates of this set of clones.

   An election method meets the "Generalized Independence of Clones
   Criterion" if & only if:

      (a) If a candidate of a set of clones is elected, then,
          if this set of clones is substituted by a makro-candidate,
          this makro-candidate must be elected.

      (b) If _no_ candidate of a set of clones is elected, then,
          if this set of clones is substituted by a makro-candidate,
          this makro-candidate must _not_ be elected.

You wrote (26 Aug 1998):
> One of the problems I have with any of these clone-independence criteria
> is that the situations they are designed to cope with are somewhat
> artificial. While clone sets of a sort definitely exist in the real
> world (call them "party members" or "factions"), they're "fuzzy", in the
> sense that there usually won't be perfectly clean divisions between the
> sets in the minds of all voters.  In most elections, there will be a few
> voters who don't vote along party/faction lines (picking and choosing
> from multiple parties), thereby destroying the perfect clone sets which
> are probably needed for these criteria to work their magic.
>
> So, in the real world, we're usually faced with the problem of near-clone
> sets, rather than true clone sets.  The question is: does compliance with
> GICC or TICC help to correctly resolve these types of problems?  Obviously
> TICC compliance is certain to be less useful than GICC, since the possible
> ballot configurations it allows are fewer than what GICC would permit,
> while still identifying clone sets.  Still, I'd be interested to know if
> anyone's done analysis on whether GICC is at least sometimes helpful with
> the near-clone set problem.

Of course, an election method should meet clone criteria implicitely.
It doesn't make any sense to search for clones in a given ballot
configuration and substitute them by a makro-candidate explicitely.
[Pareto criteria have the same problem.]

You are invited to find stronger "clone criteria." As long as the proposed
criterion is compatible with other desired properties, the proposed
criterion should be as strong as possible. But you should always
remember, that IIAC cannot be met by any reasonable election method.

Markus Schulze