# [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