[EM] Dissimilar tie-breaker
Steve Eppley
SEppley at alumni.caltech.edu
Fri May 5 20:28:18 PDT 2000
Hi,
In a couple of recent messages I mentioned my attempt to
strengthen "independence from clones" to "independence from
similar alternatives" (ISA). I defined similar alternatives in
a message posted this morning. I haven't yet mentioned methods
which comply with ISA or which "practically" comply in large
public elections, and I haven't yet described a proposed tie-
breaker. This message addresses those questions.
Definition: A correspondence is a function which takes as
its arguments a set of voters' rankings of the alternatives
and a "feasible" set which is a non-empty subset of the
alternatives, and chooses a non-empty subset of the feasible
set, and chooses the same when alternatives not in the
feasible set are deleted from the rankings.
Definition: A correspondence is partially independent from
similar alternatives if and only if for any set of voters'
rankings, any set Y which is a similar set according to the
rankings, and any set Ys which is a strict subset of Y, the
following two conditions hold:
1. For all alternatives x not in Y, x is chosen when all
alternatives are feasible if and only if x is chosen
when all except those in Ys are feasible.
2. At least one alternative in Y is chosen when all
alternatives are feasible if and only if at least one
alternative in Y is chosen when all except those in Ys
are feasible.
I believe several of the voting procedures we've discussed here
in EM are partially independent from similar alternatives, when
suitably adjusted so they accept a feasible set as an argument:
BCM, IBCM (a.k.a. DCD), probably Schulze, probably MTM (which is
a "majoritarian", not a "margins", variation of Tideman).
(Assuming this is true of Schulze, then it would also be true of
Blake's "path voting" if the definition of similar set were
modified to use margins instead of majorities.) If these
beliefs are true, then all of those methods except BCM would be
sufficiently decisive in large public elections that one could
justifiably claim they are "practically" independent from
similar alternatives in large public elections.
While driving toward complete independence, I developed a tie-
breaking procedure which I call Dissimilar(g). It's defined
with respect to any g which is a correspondence. Here are the
definitions associated with Dissimilar(g):
Definition: For any set S, let #S denote the cardinality of S.
Definition: For any sets S1 and S2, let S1\S2 denote the set
of elements of S1 which are not in S2.
Definition: Given a set S, random(S) denotes a function which
randomly picks an element of S consistently with the lottery
which gives an equal 1/#S chance to each element in S. (Note
that when S is a singleton, random(S) picks the lone element
of S with certainty.)
Definition: A set Y of alternatives is a similar set with
respect to a set Z of alternatives if and only if Y is a
subset of Z and Y is a similar set when all alternatives
not in Z are deleted from the rankings.
Let A denote the set of alternatives.
Let R denote the set of voters' rankings.
Let Z denote the feasible set of alternatives (which may have
been reduced before the Dissimilar tie-breaker is reached).
Definition: Given any correspondence g, Dissimilar(g)(R,Z)
elects according to the following procedure:
Let D denote a variable set of alternatives.
Let L denote a variable n-tuple of real numbers, with one
component for each alternative.
Let Represent denote a variable n-tuple of alternatives,
with one component for each alternative.
Step 1: (Initialization)
1.1 Let D = Z.
1.2 For all x in Z, let L(x)=1.
1.3 For all x in A\Z, let L(x)=0.
1.4 For all x in A, let Represent(x)=x.
Step 2. Repeat while #D > 1:
2.1 Pick a set Y which is a similar set with respect
to D such that #Y > 1 and no strict subset of Y
having cardinality > 1 is a similar set with
respect to D.
2.2 Let G = g(R,D). Let x' = random(G).
2.3 For all x in Z such that Represent(x) is in Y\G,
let L(x)=0.
2.4 For all x in Z such that Represent(x) is in G,
let L(x)=L(x)/#G and let Represent(x)=x'.
2.5 Let D = (D\Y) U {x}.
Step 3. Randomly elect one alternative consistently with
the lottery L, interpreting each component of L as
the probability that its corresponding alternative
will be elected.
Remarks:
1. In step 2.1, while #D>1 there must be at least one such set Y
since D is trivially a similar set with respect to D.
2. I haven't hammered out an algorithm for finding Y in step 2.1
and in the worst case, where #Z is large, it could take a long
time to compute. This suggests that Dissimilar is useful only
as a tie-breaker.
3. Assume that g (used in step 2.2) is partially independent
from similar alternatives, and that g is "2-candidate
majoritarian." (Definition of 2-candidate majoritarian: Given
exactly 2 feasible candidates {x,y}, {x} is chosen whenever x
beats y pairwise and {x,y} is chosen whenever x ties y pairwise.
Note that most prominent single-winner methods are 2-candidate
majoritarian.)
4. Step 2.5 eliminates from D all of Y except one "g-best"
alternative of Y. Since Y is not a singleton, this must reduce
the cardinality of D by at least 1 for each repetition of step 2.
Here's an example showing the operation of Dissimilar:
3 alternatives {x, y1, y2}
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
The three pairings are all 50/50 ties so a tie-breaker is needed
if a pairwise method is employed.
Note that by changing 2 votes to produce the 25/25/25/25
scenario, y1 and y2 would be clones, and x would have a 1/2
chance of being elected, given Random Dictator or Random
Hierarchy, if at least one of the y's competes. As is, y1 and
y2 are similar alternatives but not clones, and Random Dictator
and Random Hierarchy would give x only a 49/100 chance if both
of the y's compete, but a 1/2 chance if exactly one of the y's
compete.
In step 1, Dissimilar initializes D={x,y1,y2}, L=(1,1,1), and
Represent=(x,y1,y2).
In step 2.1, Dissimilar finds Y={y1,y2}.
In step 2.2, G=g(R,Y) must be {y1} or {y2} or {y1,y2}. Since
the "y1 vs. y2" pairing is a tie, assume G={y1,y2}. Then x' is
either y1 or y2, randomly picked. Assume x'=y1.
In step 2.3, nothing happens since Y\G is empty.
In step 2.4, Dissimilar sets L=(1,.5,.5) since #G=2, and sets
Represent=(x,y1,y1). (Now y2 is represented by y1.)
In step 2.5, Dissimilar eliminates y2 from D, so D=(x,y1}.
Since #D is still greater than 1, step 2 repeats:
In step 2.1, Y={x,y1}.
In step 2.2, since the "x vs. y1" pairing is a tie, assume
G=g(R,Y)={x,y1}. Then x' is either x or y1, randomly picked.
Let's consider both cases:
Case 1: x' = x. In step 2.3, nothing happens since Y\G is empty.
In step 2.4, Dissimilar sets L=(.5,.25,.25) and sets
Represent=(x,x,x).
In step 2.5, Dissimilar sets D={x}.
Then step 2 no longer repeats, and Dissimilar elects using the
lottery (.5,.25,.25).
Case 2: x' = y1. In step 2.3, nothing happens since Y\G is
empty.
In step 2.4, Dissimilar sets L=(.5,.25,.25) and sets
Represent=(y1,y1,y1).
In step 2.5, Dissimilar sets D={y1}.
Then step 2 no longer repeats, and Dissimilar elects using the
lottery (.5,.25,.25).
One can easily verify that if g is a pairwise method, so that in
the example g(R,Y) will always choose all of Y in step 2.2, then
the lottery will be (.5,.25,.25) in all cases, and the
probability that x will be elected is 1/2 if at least one of the
y's competes. So in this example Dissimilar works as desired,
providing independence from a similar set which is not a clone
set.
The only problem I'm aware of so far (apart from the slowness of
calculating step 2.1 when #Z is large), which may be what loses
complete compliance with ISA, is related to the ambiguity in
step 2.1: there may be more than one similar set which could be
picked for Y. This won't matter if the pickable sets are
disjoint, since in this case the order they're picked won't
matter ultimately. But what if two (or more) have a non-empty
intersection? For instance, suppose that {y1,y2} and {y2,y3}
are both similar sets with respect to D. I'm not yet sure if
this can cost compliance with ISA, but my intuition is that
there's a problem.
There's a possible patch for the definition of similar set which
is analogous to the patch for the clone definition which Markus
reposted a couple of days ago. It would prevent {y1,y2} and
{y2,y3} from being similar sets when {y1,y2,y3} is a similar
set. But I don't think this would be as innocuous as the clone
patch, since would-be manipulators could have a strong
preference for two of the three over the third. Take the case
where the would-be manipulators strongly prefer y1&y2 over y3,
and assume the three are technically similar and all reach the
tie-breaker. By nominating both y1 and y2, they reduce y3's
chance of election, assuming the patch where {y1,y2} and {y2,y3}
are not similar but {y1,y2,y3} is similar. Can we do better?
---Steve (Steve Eppley seppley at alumni.caltech.edu)
More information about the Election-Methods
mailing list