[EM] Useful Propositions re: clones & tie-breaking

[Steve Eppley]

The following definitions, lemmas, and propositions may be 
generally useful in proving properties about voting methods.  
Many of the them are related to independence of clones.

I haven't provided proofs of the lemmas, due to lack of time.  
Hopefully I will find time at a later date.  Meanwhile, if you 
have time, feel free to prove or disprove them, and feel free to 
check my proofs of the propositions.

   For all sets S1 and S2,
   let S1^S2 denote the intersection of S1 and S2,
   let S1\S2 denote the set of elements in S1 not in S2,
   let S1US2 denote the union of S1 and S2, and
   let |S1| denote the number of elements in S1.

   Let A denote the finite non-empty set of alternatives.
   Let V denote the finite set of votes regarding A.

Some notation for some aggregate properties of the votes:

   For all x,y in A, let #(x,y) denote the number of
   voters who ranked x over y.

   For all x,y in A, let B(x,y) denote the boolean function
   which is true if and only if #(x,y) > #(y,x).

There are three cases where preferences for alternatives are 
neglected.
1. Alternatives (e.g., some clones) might not be competing,
   so voters' preferences regarding them won't be in V.
2. A tie-breaker may neglect preferences regarding eliminated
   alternatives when choosing from the remaining alternatives.
3. A procedure which iteratively repeats some other procedure
   may neglect, each iteration, preferences regarding
   alternatives eliminated during previous iterations,
   when choosing whether to eliminate more alternatives.
The following notation will be useful in formal expressions of 
such neglect:

   For all A, all V, and all Z such that Z is a non-empty subset
   of A, let V(Z) denote the transformation of V obtained by
   lowering all alternatives in A\Z to the bottom, below all
   alternatives in Z, preserving all relative preferences
   regarding alternatives in Z.

Clones are defined next, in a way which is more general than 
usual.  This is useful for procedures which neglect eliminated 
alternatives, such as many tie-breakers and the procedures which 
iteratively repeat some underlying procedure.

   "Clones in Z":  Given any A, any V, any Z which is a non-empty
   subset of A, and any Y which is a non-empty subset of Z,
   Y is a set of clones in Z if and only if all three of the
   following conditions hold:
      1. For all y,y' in Y and all x in Z\Y, every vote in V
         which ranks y over x also ranks y' over x.
      2. For all y,y' in Y and all x in Z\Y, every vote in V
         which ranks x over y also ranks x over y'.
      3. For all y in Y and all x in Z\Y, at least one
         vote in V ranks x over y or y over x.

Since not all voting procedures are deterministic, it is useful 
adopt a notation generalized to encompass both deterministic and 
non-deterministic voting procedures:

   A "lottery over A" is a |A|-tuple of real numbers in [0,1].
   For all L such that L is a lottery over A, and all x in A,
   let L(x) denote the component of L which corresponds to x.
   Abbreviate Lx where useful.

Lx is interpreted as the probability that x will be elected.  
When Lx=1, this means x will be chosen with certainty.  When 
Lx=0, this means x will be defeated with certainty.  So the 
lottery notation is flexible enough to encompass both 
deterministic and non-deterministic voting procedures.

   A function f is a "voting rule" if and only if, for all A,
   given any V and any Z such that Z is a non-empty subset of A,
   f(Z,V) is a lottery over A and all three of the following
   conditions hold:
      1. For all x in A\Z, fx(Z,V) = 0.
      2. f(Z,V) = f(Z,V') for all V'=V.
      3. f(Z,V) = f(Z,V(Z)).

Condition 1 in the definition of voting rule implies that only 
alternatives in Z will be elected.  Condition 2 implies that the 
lottery is determined by the votes, and only by the votes, and 
in a deterministic manner. (That doesn't mean the voting rule is 
deterministic, since it doesn't imply that the lottery consists 
of only 1's and 0's.)  Condition 3 implies that voting rules 
neglect alternatives not in Z.

   A voting rule f is "deterministic" if and only if
   for all A, all V, all Z such that Z is a non-empty subset
   of A, and all x in A, fx(Z,V) is either 1 or 0.

   A voting rule f is "single-winner" if and only if
   for all A, all V, and all Z such that Z is a non-empty subset
   of A, the sum (over all x in A) of fx(Z,V) is 1.

Most of the voting methods we discuss attempt to choose exactly 
one winner, but sometimes indecisively choose more than one.  It 
is convenient to describe those voting methods using notation 
which indicates that they choose a subset of the alternatives:

   A function g is a "correspondence" if and only if,
   for all A, given any V and any Z such that Z is a non-empty
   subset of A, all three of the following conditions hold:
      1. g(Z,V) is a non-empty subset of Z.
      2. g(Z,V) = g(Z,V') for all V'=V.
      3. g(Z,V) = g(Z,V(Z)).

Condition 1 in the definition of correspondence implies that 
only alternatives in Z will be chosen, and that at least one 
alternative will be chosen.  Condition 2 implies that the chosen 
set is determined by the votes, and only by the votes, and with 
no randomness.  Condition 3 implies that correspondences neglect 
alternatives not in Z.

Complete independence of clones means that, as long as at least 
one clone of a clone set is voted on, the probability of 
election of a non-clone is unaffected by adding or removing 
clones, and the probability that some unspecified clone will be 
elected is unaffected by adding or removing clones:

   A single-winner voting rule f is "completely independent
   of clones" if and only if for all A, all V, all Y which is
   a set of clones in A, and all Y0 which is a strict subset
   of Y, both of the following conditions hold:
      1. For all x in A\Y, fx(A,V) = fx(A\Y0,V).
      2. The sum (over all y in Y) of fy(A,V) equals
         the sum (over all y in Y) of fy(A\Y0,V).

   Abbreviate "cic" to mean "completely independent of clones."

The following notation expresses the use of a voting rule as a 
tie-breaker for a correspondence:

   For all correspondences g and all voting rules f,
   let (g//f)(Z,V) denote f(g(Z,V),V).

Complete independence of clones cannot be a property of 
correspondences, but it can be a property of g//f, where g is a 
correspondence and f is a single-winner voting rule.

A lemma below will establish that, given any correspondence g 
and any voting rule f which is single-winner and completely 
independent of clones, g//f is completely independent of clones 
if g is "partially independent of clones":

   A correspondence g is "partially independent of clones",
   if and only if for all A, all V, all Y which is a set of
   clones in A, and all Y0 which is a strict subset of Y,
   both of the following conditions hold:
      1. (A\Y)^g(A,V) = (A\Y)^g(A\Y0,V).
      2. Y^g(A,V) is empty if and only if Y^g(A\Y0,V) is empty.

   Abbreviate "pic" to mean "partially independent of clones."

Some voting methods may consist of two or more correspondences 
executed in series, where each correspondence neglects 
alternatives eliminated by correspondences executed earlier in 
the series:

   For all correspondences g and g',
   let (g//g')(Z,V) denote g'(g(Z,V),V).

Some voting methods, such as Instant Runoff (a.k.a. STV), 
Nanson, and IBCM repeat some underlying method, neglecting 
eliminated alternatives.  The following notation expresses this 
concept:

   Define "repeat(g,r)" recursively:
   For all correspondences g, repeat(g,1) = g.
   For all correspondences g and all integers r>1,
      repeat(g,r) = repeat(g,r-1)//g.

The voting methods which repeat some underlying method do not go 
on repeating forever.  Typically, they stop when further 
repetition would not eliminate any more alternatives:

   For all correspondences g, all A, all V, and all Z
   such that Z is a non-empty subset of A,
   let r'(g,Z,V) denote the smallest positive integer r
   such that repeat(g,r)(Z,V) = repeat(g,r+1)(Z,V),
   if there is such an r.

   For all correspondences g, all A, all V, and
   all Z such that Z is a non-empty subset of A,
   let [g](Z,V) = repeat(g,r'(g,Z,V))(Z,V).

(The definition of [] is a bit abusive since r' is a function.  
However, since A is held fixed in the discussion, so is |A|, so 
[g] could have been formally defined as repeat(g,|A|).  This is 
because further repetition beyond r' will not eliminate any more 
alternatives.)

* * *

The rest of the definitions are about properties of certain 
prominent voting methods.

Cycles and chains (beatpaths) are defined next, in a way which 
is more general than usual.  This is useful for procedures which 
neglect eliminated alternatives (tie-breakers, etc.) and 
calculate cycles or chains.

Both cycles and chains are defined to be sequences of 
alternatives.

   "Sequence strength":  For all x1,x2,...,xn in A (n>1),
   let Strength(x1x2...xn) denote the minimum, over all k
   in {1,...,n-1}, of #(xk,xk+1).

   "Cycles in Z":  Given any A, any V, any Z which is a subset
   of A, and any x1,x2,...,xn in A (n>1), x1x2...xn is a
   "cycle in Z" if and only if x1,x2,...,xn are all in Z
   and x1 = xn and, for all k in {1,...,n-1}, B(xk,xk+1).

   Let Cycles(Z,V) denote the set of all cycles in Z.
   For all A, all V, all Z such that Z is a subset of A, and
   all x,y in A, let Cycles(x,y,Z,V) denote the set of all
   cycles in Z in which x immediately precedes y.  When V is
   fixed in the context, abbreviate Cycles(x,y,Z), and
   when Z=A also, abbreviate Cycles(x,y).

   "Cyclic Majorities":  For all A, all V, all Z such that
   Z is a subset of A, and all C in Cycles(Z,V), let
   Majorities(C) denote the set of ordered pairs of
   alternatives {(x,y) such that x immediately precedes y
   in C}.

   "Smallest Cyclic Majorities":  For all A, all V, all Z
   such that Z is a subset of A, and all C in Cycles(Z,V),
   let Smallest(C) denote the set of ordered pairs of
   alternatives {(x,y) such that (x,y) is in Majorities(C)
   and Strength(C) = #(x,y)}.

   "Chains in Z":  Given any A, any V, any Z which is a
   subset of A, and any x1,x2,...,xn in A (n>1), x1x2...xn is
   a "chain in Z from x1 to xn" if and only if x1,x2,...,xn
   are all in Z and, for all k in {1,...,n-1}, B(xk,xk+1).

   For all A, all V, all Z such that Z is a subset of A, and
   all x,y in A, let Chains(x,y,Z,V) denote the set of
   all chains in Z from x to y.  When V is fixed in the
   context, abbreviate Chains(x,y,Z), and when Z=A also,
   abbreviate Chains(x,y).

   "Strongest chain":  For all A, all V, all Z such that Z is
   a subset of A, and all x,y in A, let S(x,y,Z,V) equal,
   if Chains(x,y,Z,V) is not empty, the maximum, over all C
   in Chains(x,y,Z,V), of Strength(C), and let S(x,y,Z,V)
   equal 0 otherwise.  When V is fixed in the context,
   abbreviate S(x,y,Z), and when Z=A also, abbreviate S(x,y).

* * *

The lemmas and propositions are stated here.  Proofs of the 
propositions are appended at the bottom.  Most of the lemmas 
follow easily by inspection of definitions.

Lemma "GF1":  For all correspondences g and all single-winner 
voting rules f, g//f is a single-winner voting rule.

Lemma "GG":  For all correspondences g and g', g//g' is a 
correspondence.

Lemma "GR":  For all correspondences g and all positive integers 
r, repeat(g,r) is a correspondence.

Lemma "YUZ":  Suppose Y is a clone set in A.  For all Z such 
that Z is a subset of A, Y is a clone set in YUZ.

Lemma "Y^Z":  Suppose Y is a clone set in A.  For all Z such 
that Z is a subset of A and Y^Z is not empty, Y^Z is a clone set 
in Z.

Lemma "Y#B=":  Suppose Y is a clone set in A.  For all y,y' in Y 
and all x in A\Y, the following four statements are true:
   (.1)  #(x,y) = #(x,y').
   (.2)  #(y,x) = #(y',x).
   (.3)  B(x,y) = B(x,y').
   (.4)  B(y,x) = B(y',x).

Lemma "XY1":  Suppose Z is a subset of A and Y is a clone set in 
A.  For all y in Y, all x in A\Y, and all C in Cycles(Z,V), both 
of the following statements are true:
   (.1) (y,x) is in Smallest(C) if and only if there exists a C'
        in Cycles(Z,V), not necessarily distinct from C, such
        that (y,x) is in Smallest(C') and y is the only
        alternative in Y contained in C'.
   (.2) (x,y) is in Smallest(C) if and only if there exists a C'
        in Cycles(Z,V), not necessarily distinct from C, such
        that (y,x) is in Smallest(C') and y is the only
        alternative in Y contained in C'.

Lemma "YSm=":  Suppose Z is a subset of A and Y is a clone set 
in Z.  For all y,y' in Y, and all x in A\Y, both of the 
following statements are true:
   (.1)  There exists C in Cycles(Z) such that (x,y) is in
         Smallest(C) if and only if there exists C' in Cycles(Z)
         such that (x,y') is in Smallest(C').
   (.2)  There exists C in Cycles(Z) such that (y,x) is in
         Smallest(C) if and only if there exists C' in Cycles(Z)
         such that (y',x) is in Smallest(C').

Lemma "YS=":  Suppose Z is a subset of A and Y is a clone set in 
Z.  For all y,y' in Y, and all x in A\Y, both of the following 
statements are true:
   (.1)  S(x,y,Z,V) = S(x,y',Z,V).
   (.2)  S(y,x,Z,V) = S(y',x,Z,V).

Lemma "XX'":  Suppose Z is a subset of A, Y is a clone set in Z 
and Y0 is a strict subset of Y.  Then for all x,x' in A\Y, both 
of the following statements are true:
   (.1)  S(x,x',Z,V) = S(x,x',Z\Y0,V).
   (.2)  There exists C in Cycles(Z) such that (x,x') is
         in Smallest(C) if and only if there exists C0
         in Cycles(Z\Y0) such that (x,x') is in Smallest(C0).

Lemma "XY0":  Suppose Z is a subset of A, Y is a clone set in Z 
and Y0 is a strict subset of Y.  Then for all y in Y\Y0 and all 
x in A\Y, all four of the following statements are true:
   (.1)  S(x,y,Z,V) = S(x,y,Z\Y0,V).
   (.2)  S(y,x,Z,V) = S(y,x,Z\Y0,V).
   (.3)  There exists C in Cycles(Z) such that (x,y) is
         in Smallest(C) if and only if there exists C0
         in Cycles(Z\Y0) such that (x,y) is in Smallest(C0).
   (.4)  There exists C in Cycles(Z) such that (y,x) is
         in Smallest(C) if and only if there exists C0
         in Cycles(Z\Y0) such that (y,x) is in Smallest(C0).

Proposition "GFCIC":  For all correspondences g which are 
partially independent of clones, and all single-winner voting 
rules f which are completely independent of clones, g//f is a 
single-winner voting rule which is completely independent of 
clones.

Lemma "RVHCIC":  RandomVoterHierarchy is a single-winner voting 
rule which is completely independent of clones.

Proposition "GGPIC":  For all correspondences g and g' which are 
partially independent of clones, g//g' is a correspondence which 
is partially independent of clones.

Lemma "GRPIC":  For all correspondences g which are partially 
independent of clones, and all positive integers r, repeat(g,r) 
is partially independent of clones.

Lemma "r'|Z|":  For all correspondences g, all A, all V, and all 
Z such that Z is a non-empty subset of A, r'(g,Z,V) exists and 
is in {1,...,|Z|}.

Lemma "[]PIC":  For all correspondences g which are partially 
independent of clones, [g] is partially independent of clones.

* * *

Proofs of the propositions.

Proposition "GFCIC":  For all correspondences g which are 
partially independent of clones, and all single-winner voting 
rules f which are completely independent of clones, g//f is a 
single-winner voting rule which is completely independent of 
clones.

Proof:  Abbreviate W = g(A,V) and W0 = g(A\Y0,V).  By lemma , 
g//f is a single-winner voting rule.  So we only need to 
establish the following two statements:

   For all x in A\Y, fx(W,V) = fx(W0,V).               (1)

   The sum, over all y in Y, of fy(W,V) equals
   the sum, over all y in Y, of fy(W0,V).              (2)

There are 2 cases to consider:

Case 1: Y^W is empty.
   Since g is pic and Y^W is empty, Y^W0 is empty, and 
      W = W0.                                          (3)
   By identity, (3) implies (1) and (2).

Case 2: Y^W is not empty.
   By lemma , Y is a clone set in YUW.  Since f is cic,
   and by condition 3 of the definition of voting rule,
   the following two statements hold:
      For all x in A\Y, fx(YUW,V) = fx(W,V).           (4)
      The sum, over all y in Y, of fy(YUW,V) equals
      the sum, over all y in Y, of fy(W,V).            (5)
   Since Y^W is not empty and g is pic, Y^W0 is not empty.
   By lemma , Y is a clone set in YUW0.  Since f is cic,
   and by condition 3 of the definition of voting rule,
   the following two statements hold:
      For all x in A\Y, fx(YUW0,V) = fx(W0,V).         (6)
      The sum, over all y in Y, of fy(YUW0,V) equals
      the sum, over all y in Y, of fy(W0,V).           (7)
   Since g is pic, YUW = YUW0 and W\Y = W0\Y, so the
   left sides of (4) and (6) are equal and the left sides
   of (5) and (7) are equal.  Thus the right sides of
   (4) and (6) are equal, and the right sides of (5)
   and (7) are equal:
      For all x in A\Y, fx(W,V) = fx(W0,V).            (8)
      The sum, over all y in Y, of fy(W,V) equals
      the sum, over all y in Y, of fy(W0,V).           (9)
   Statements (8) and (9) are the same as (1) and (2),
   respectively.

Since (1) and (2) have been established in both cases, it 
follows that g//f is a single-winner voting rule which is 
completely independent of clones.                      QED
--------------------
Proposition "GGPIC":  For all correspondences g and g' which are 
partially independent of clones, g//g' is a correspondence which 
is partially independent of clones.

Proof:  (The proof parallels the proof of proposition  re: 
g//f.)  Abbreviate W = g(A,V) and W0 = g(A\Y0,V).  By lemma , 
g//g' is a correspondence.  So we only need to establish the 
following two statements:

   (A\Y)^g'(W,V) = (A\Y)^g'(W0,V).                     (1)

   Y^g'(W,V) is empty iff Y^g'(W0,V) is empty.         (2)

There are 2 cases to consider:

Case 1: Y^W is empty.
   Since g is pic, W = W0.  This implies:
      g'(W,V) = g'(W0,V).                              (3)
   By identity, (3) implies (1) and (2).

Case 2: Y^W is not empty.
   By lemma , Y is a clone set in YUW.  Since g' is pic,
   and by condition 3 of the definition of correspondence,
   the following two statements hold:
      (W\Y)^g'(YUW,V) = (W\Y)^g'(W,V).                 (4)
      Y^g'(YUW,V) is empty iff Y^g'(W,V) is empty.     (5)
   Since Y^W is not empty and g is pic, Y^W0 is not empty.
   By lemma , Y is a clone set in YUW0.  Since g' is pic,
   and by condition 3 of the definition of correspondence,
   the following two statements hold:
      (W0\Y)^g'(YUW0,V) = (W0\Y)^g'(W0,V).             (6)
      Y^g'(YUW0,V) is empty iff Y^g'(W0,V) is empty.   (7)
   Since g is pic, YUW = YUW0 and W\Y = W0\Y, so the
   left sides of (4) and (6) are equal and the left sides
   of (5) and (7) are equal.  Thus the right sides of
   (4) and (6) are equal, and the right side of (5) is
   true if and only if the right side of (7) is true:
      (W\Y)^g'(W,V) = (W0\Y)^g'(W0,V).                 (8)
      Y^g'(W,V) is empty iff Y^g'(W0,V) is empty.      (9)
   Since g' is a correspondence, condition 1 of the definition
   of correspondence implies that A^g'(Z,V) = Z^g'(Z,V) for
   any Z which is a non-empty subset of A.  So (8) implies:
      (A\Y)^g'(W,V) = (A\Y)^g'(W0,V).                 (10)
   Statements (10) and (9) are the same as (1) and (2),
   respectively.

Since (1) and (2) have been established in both cases, it 
follows that g//g' is a correspondence which is partially 
independent of clones.                                 QED
--------------------


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