[EM] Useful Propositions re: clones & tie-breaking
Steve Eppley
SEppley at alumni.caltech.edu
Fri Jun 2 18:12:51 PDT 2000
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)
More information about the Election-Methods
mailing list