[EM] Linear methods are consistent and monotonic
Richard Moore
rmoore4 at home.com
Mon Oct 1 18:07:38 PDT 2001
In my previous post I gave a definition for linear methods.
I don't recall any previous discussions of linearity on this
list, though it seems like a natural enough topic, so I
thought I'd post a couple of theorems on the topic.
Linear methods (i.e., those with linear scoring) are always
consistent, except when a tie is settled using an
inconsistent tie-breaker.
Given a linear method, that is, one for which
S(B3) = S(B1) + S(B2)
for B3 = B1 v B2 (B1, B2 are disjoint), and if Ci wins both
the B1 election and the B2 election, then M(S(B1)) = i, so
si(B1) >= sj(B1) for all j != i.
Likewise for B2:
si(B2) >= sj(B2) for all j != i.
Therefore,
si(B3) = si(B1) + si(B2) >= sj(B1) + sj(B2) = sj(B3)
for all j != i. This implies that M(S(B3)) = i, except in
the case where both the B1 and B2 elections had ties (which
results in a tie in the B3 election). Therefore the only way
for a linear method to be inconsistent is to use an
inconsistent tie-breaker.
Note that random ballot is inconsistent. I don't think
inconsistency in tie-breakers is a significant problem,
especially in large voting populations where ties will be rare.
Monotonicity for linear methods can be proven by a similar
argument. However, since most of the definitions of
monotonicity that I've seen seem to be written with
positional voting methods in mind, we need a definition
useful for non-positional voting. The following definition
should work for methods, positional or non-positional, that
generate a scalar score for each candidate:
MONOTONICITY CRITERION FOR SCALAR SCORING METHODS:
If X is any subset of all ballots that were cast in an
N-candidate election, and si(X) is candidate Ci's score for
subset X (i varies from 1 to N), and if candidate Cw wins
the election, and if subset X is replaced with a new subset
X' such that,
sw(X') > sw(X)
and, for each i != w,
si(X') <= si(X)
then Cw will also win the new election.
PROOF THAT LINEAR METHODS ARE MONOTONIC:
Given a linear method, and given ballot sets B1, X, X',
(where B1, X are disjoint and B1, X' are disjoint), B2 = B1
v X, B3 = B1 v X':
S(B2) = S(B1) + S(X)
S(B3) = S(B1) + S(X')
then if Cw is the winner chosen with ballot set B2 (i.e.,
sw(B2) >= si(B2) for i from 1 to N), and if
sw(X') > sw(X)
and
si(X') <= si(X) (i != w),
then, since the method is linear,
sw(B3) = sw(B1) + sw(X') > sw(B1) + sw(X) = sw(B2)
and, for i != w,
si(B3) = si(B1) + si(X') <= si(B1) + si(X) = si(B2).
This means that
sw(B3) > sw(B2) >= si(B2) >= si(B3)
or
sw(B3) > si(B3).
This inequality holds for every i != w, so Cw still wins
with ballot set B3. Therefore the method is monotonic.
Richard
More information about the Election-Methods
mailing list