[EM] Dissimilar tie-breaker

[Steve Eppley]

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)