[EM] Equivalent definition of clone independence; more on similarity
Steve Eppley
SEppley at alumni.caltech.edu
Tue May 9 20:38:46 PDT 2000
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)
More information about the Election-Methods
mailing list