[EM] Equivalent definition of clone independence; more on similarity

[Steve Eppley]

Last week Markus reposted the redefinition of clone set which 
contains an innocuous technical modification permitting complete 
satisfaction of the clone independence criterion.  The added 
restriction was that no alternative outside the set is an "exact 
clone" of any alternative in the set.

There's another formulation of clones and independence which is 
equivalent but which doesn't place that restriction on clone sets, 
by instead embedding the restriction into the definition of 
independence.  To my eye, the restriction is more appropriate 
placed in the definition of independence, but this may just be a 
matter of taste.

This message provides such a reformulation.  Also, this message 
defines a weaker criterion "independence from exact clone 
alternatives" (IECA) which can be considered a consistency axiom 
even more fundamental than clone independence.  (I haven't checked 
the literature to see how old this criterion actually is.  I 
wouldn't be surprised to learn that Tideman wrote about it, or that 
it has already been discussed in EM.)  And, finally, this message 
further explores the possibility of crafting a reasonable 
"independence from similar alternatives" criterion which can be 
completely satisfied.

   Given any sets S1 and S2, let S1\S2 denote the set of
   elements in S1 but not in S2.  Given any set S, let #S
   denote the number of elements in S.

   Let A denote a finite nonempty set of alternatives {x,y,z,...}.

   Let N denote a finite nonempty set of voters {1,2,...,n}.

   For all i in N, let Ri denote voter i's ranking of the
   alternatives in A.  Let R = {R1, R2, ..., Rn} denote a set
   of rankings of the alternatives, one ranking per voter.

   Given any set Z which is a nonempty subset of A, for all v
   in V let Ri|Z denote the ranking obtained from Ri by deleting
   from Ri all alternatives NOT in Z, and let R|Z denote the set
   {R1|Z, R2|Z, ..., Rn|Z}.

   Definition (1):  A lottery is a #A-tuple, one component per
   alternative in A, such that each component is a real number
   in [0,1] and the sum of the components is 1.  Given any
   lottery L, for all x in A let L(x) denote the component of L
   which corresponds to x.

L(x) is interpreted as the probability that x will be elected.  
If L(x)=1 for some x, then x will be elected with certainty.

   Definition (2):  A function f is a voting scheme if and only if
   it takes as arguments a set of voters' rankings and a nonempty
   subset of A, returns a value which is a lottery, and for all A,
   all R, and all Z such that Z is a nonempty subset of A, satisfies
   all three of the following conditions:
      (2.1) f(R,Z)(x) = 0 for x in A\Z.
      (2.2) f(R',Z)(x) = f(R,Z)(x) for all x in A and 
              all R' such that R' = R.
      (2.3) f(R|Z,Z)(x) = f(R,Z)(x) for all x in A.

Just as L(x) denotes the component of lottery L which corresponds 
to alternative x, f(x) denotes the component of f which corresponds 
to x.  When f(x)=1, this means x will be elected with certainty, 
when f(x)=0 this means x will be defeated with certainty, and when
0 < f(x) < 1 this means a random mechanism will be needed to 
determine the outcome.  A voting scheme f is deterministic if 
and only if f(R,Z)(x) is 1 or 0 for all A, all R, all Z which is
a non-empty subset of A, and all x in A.  A voting scheme is 
probabilistic if and only if it is not deterministic.

Condition 2.1 means no alternative outside Z will be elected.  
Since we are discussing the effect of attempts to manipulate by 
adding or removing alternatives, the notation needed to encompass 
the concept of neglect of alternatives so that outcomes given a 
subset of A can be compared.  This is why the definition of voting 
scheme includes as an argument the subset of alternatives which can 
be elected, which we will call the feasible subset.

Condition 2.2 expresses the requirement that the lottery must 
depend only on the rankings and the feasible subset, not on other 
things such as the phase of the moon or random mechanisms. 

Condition 2.3 is a mild restriction which simplifies the notation 
by requiring that the lottery must not depend on preferences 
regarding alternatives outside the feasible subset.  This avoids 
potential complications which may otherwise arise if voters rank 
alternatives which are not in the feasible subset, and allows us to 
more easily model attempts to manipulate outcomes by not nominating 
certain alternatives.  It's easy to generalize any voting procedure 
of interest in the appropriate way so it neglects preferences 
outside a feasible subset.

   Definition (3):  A set Y is an exact clone set of (A,R)
   if and only if both of the following conditions hold:
      (3.1) Y is a subset of A and #Y > 1.
      (3.2) For all i in N and all distinct y,y' in Y,
            Ri ranks y equal to y'.

I've added the innocuous restriction #Y > 1, here and to the 
definition of clone set below, and implicitly to the definition of 
similar set.  Obviously, singleton sets need not be considered 
clone sets, exact clone sets, or similar sets.

   Definition (4):  Independence from Exact Clone Alternatives
   (IECA):  A voting scheme f satisfies independence from
   exact clone alternatives if and only if for all A, all R,
   all Y such that Y is an exact clone set of (A,R), all Y'
   such that Y' is a strict subset of Y, and all x in A\Y
   such that {x} U Y is not an exact clone set of (A,R),
   f(R,A)(x) = f(R|(A\Y'),A\Y')(x).

IECA requires that when a strict subset of an exact clone set Y is 
deleted, the probability of election of every alternative which is 
not an exact clone of those in Y must remain unchanged.  

The innocuous technical restriction mentioned at the beginning of 
this message has been embedded in IECA, by restricting to those x 
such that {x} U Y is not an exact clone set.  Would-be manipulators 
would not gain by increasing the probability of election of one 
exact clone at the expense of another exact clone.

   Definition (5):  A set Y is a clone set of (A,R) if and only if
   both of the following conditions hold:
      (5.1) Y is subset of A and #Y > 1.
      (5.2) For all i in N, all distinct y,y' in Y, and all x
            in A\Y, Ri ranks y over x if and only if Ri ranks
            y' over x, and Ri ranks x over y if and only if
            Ri ranks x over y'.

   Definition (4):  Independence from Clone Alternatives (ICA):
   A voting scheme f satisfies independence from clone alternatives
   if and only if for all A, all R, all Y such that Y is a clone
   set of (A,R), all Y' such that Y' is a strict subset of Y, and
   all x in A\Y such that there exists no y in Y such that {x,y}
   is an exact clone set of (A,R), f(R,A)(x) = f(R|(A\Y'),A\Y')(x).

The innocuous technical restriction added to ICA is worded 
differently from the one added to IECA.  It says we are interested 
in ensuring that the probability of election of alternatives 
outside Y remains unchanged when Y' is deleted, but only for those 
alternatives outside Y which are not themselves exact clones of 
any in Y.

The wording of the restriction added to IECA could be changed so 
it's the same as the wording of the restriction added to ICA, but 
the wording as shown in IECA appears simpler.

An analogous restriction could be added to the definition of 
independence from similar alternatives (ISA), in order to make 
complete independence possible there too, but I don't think it 
would be quite as innocuous since it would have to be a broader 
restriction than the ones above.  Though less innocuous, I think a 
reasonable restriction might be crafted, by requiring that f(x) 
must be unchanged only when there exists no set nonempty subset of 
Y, call it Ys, such that {x}UYs is "more clone-like" than Y is.

To do this, we need a good way to measure the "clonishness" of a 
similar set.  The following is speculative and presumably is only a 
step in that direction:  We're trying to compare the similar set Y 
(with x outside) to a similar set {x}UYs (with Y\Ys outside).  
Score Y by the number of ballots which rank x strictly over or 
strictly under all alternatives in Y, and score {x}UYs by taking 
the maximum (or perhaps the average or minimum?), over all y in 
Y\Ys, of the number of ballots which rank y strictly over or 
strictly under all alternatives in {x}UYs.  The set having the 
larger score can be considered more clone-like.

I find it hard to construct examples to test these ideas.  Here's a 
test using the example provided in the message about the ambiguity 
in Dissimilar, showing that the proposed technique succeeds in that 
example:

   100 voters rank the alternatives as follows:
       1: y1 > x  > y2
      24: x  > y1 > y2
      25: x  > y2 > y1
      25: y1 > y2 > x
      24: y2 > y1 > x
       1: y2 > x  > y1

Given the algorithm specified above, the score for the set {y1,y2} 
(with x outside) is 98, since all but 2 voters ranked x strictly 
over or under both y1 and y2.  The score for {x,y1} (with y2 
outside) is 50, and the score for {x,y2} (with y1 outside) is 52.  
Neither {x,y1} nor {x,y2} is more clone-like than {y1,y2}, so ISA 
requires that the probability of x's election must remain unchanged 
when all three alternatives compete (i.e., 1/2, since we are 
assuming it is 1/2 when one of the y's does not compete).

If the same technique is used in Dissimilar when there's an 
ambiguity over which of two (or more) non-disjoint similar sets to 
pick in step 2.1, Dissimilar would pick {y1,y2} and x's probability 
of election would be 1/2 whether one or both alternatives in 
{y1,y2} compete against x.  So the proposed technique for scoring 
clonishness succeeds in that simple example, when Dissimilar is 
also modified to use that technique.

To complete the example, we must consider the other similar sets 
besides {y1,y2}.  We can neglect the trivially similar set 
{x,y1,y2}, but we must consider the {x,y1} and {x,y2} similar sets. 
With the modified definition of ISA, the probability of y2's 
election need not be unchanged when {x,y1} is considered as a 
similar set (because {y1,y2} is more clone-like than {x,y1}), and 
the probability of y1's election need not be unchanged when {x,y2} 
is considered as a similar set (because {y1,y2} is more clone-like 
than {x,y2}).


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