[EM] Linear methods are consistent and monotonic

[Richard Moore]

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