[EM] Borda: P2, and zero weights for truncated votes
Craig Carey
research at ijs.co.nz
Fri Mar 3 23:16:21 PST 2000
At 17:46 03.03.00 , Bart Ingles wrote:
>
>> "Is Approval Voting an 'Unmitigated Evil?' A Response to Brams,
>> Fishburn, and Merrill," by Donald G. Saari and Jill Van Newenhizen,
...
>The titles of the latter two apparently point out Saari's objection to
>allowing voters to truncate ballots. The version of Borda he favors
>actually penalizes truncators more than the "standard" version. To wit:
>
>Sincere Borda points with three candidates, for a single voter with
>preferences ABC:
>A = 2, B = 1, C = 0
>
>Points for same candidate who truncates (standard Borda):
>A = 2, B = 0.5, C = 0.5 (or A=1.5, B = 0, C = 0)
>
>Points for truncator in Saari's version:
>A = 1, B = 0, C = 0
>
>(I got this directly from Prof. Saari, in response to a question)
The definition of Standard Borda?.
>
The weights can be additively rescaled so that the very last weight
(for the last preference) is always 0. (The other weights should be
non-negative or else the method is definitely not monotonic).
--------------------------------------------------------------------
STANDARD BORDA
The definition of Standard Borda is from Bart Ingles. The Borda method
maybe is still defined wrongly by me.
Anybody an idea on why the Borda weights were wrong for so long?.
Below is a proof that Standard Borda passes P2. Below that is an attempt
to find weights for trailing zero Borda methods.
Recap.: P2 says approximately that filling in the next preference and
spreading the vote equally over the permutations where the preference
is longer by 1, causes no alteration to the set of winners.
E.g. P2({1}): adding papers 2:A, -1:AB, -1:AC to a 2 candidate election
makes no difference at all to the set of winners (or winner).
Borda is not truncation resistant, for the 1st preference:
These variant Borda methods are bad methods: adding or removing
preferences after the first, can alter the win-lose status of the
candidate named in the first preference. Certainly they do seem to
be methods that ought not be used. The powers of the weight vectors
are not normalized, which is another problem.
In the following, the number of winners can be one or more.
---------------------------------------------------------------------------
The 3 candidate 'Standard Borda' formula passes P2.
Case P2({0}): Method passes if winners are unaltered on adding (t,t,t)
to (Za0,Zb0,Zc0). In weights (2,1,0), the (1,0) is distributed.
A B C
A.. Za0 t . ( 2, 1/2, 1/2)
B.. Zb0 t . (1/2, 2, 1/2)
C.. Zc0 t . (1/2, 1/2, 2 )
Sum: 3t . ( 1, 1, 1 ) : Hence method passes P2({0})
Case P2({1}): Passes iff winners are unaltered on adding (2t,-t,-t) to
(Za0,Zab0,Zac0). Weights (2,1,0)
A.. Za0 2t . (2, 1/2, 1/2)
AB. Zab0 -t . (2, 1, 0 )
AC. Zac0 -t . (2, 0, 1 )
Sum = (0, 0, 0 ) : Hence method passes P2({1})
Case P2({2}): Passes since the weights for (AB.) and (ABC) are both (2,1,0).
---------------------------------------------------------------------------
The 4 candidate corrected 'Standard Borda' formula passes P2.
This is an example and a general treatment is below.
>> A... Za0 t . ( 3, 1/3, 1/3, 1/3)
> ^ should be (3, 1, 1, 1)
Case P2({0}): Method passes if winners are unaltered on adding (t,t,t,t)
to (Za0,Zb0,Zc0,Zd0). In weights (3,2,1,0), the (2,1,0) is distributed.
A B C D
A... Za0 t . (3, 1, 1, 1)
B... Zb0 t . (1, 3, 1, 1)
C... Zc0 t . (1, 1, 3, 1)
D... Zd0 t . (1, 1, 1, 3)
Sum: 6t.(1, 1, 1, 1) : Hence method passes P2({0})
Case P2({1}): Passes iff winners are unaltered on adding (3t,-t,-t,-t) to
(Za0,Zab0,Zac0,Zad0).
A... Za0 3t . (3, 1, 1, 1 ) # Was (3, 2/3, 2/3, 2/3)
AB.. Zab0 -t . (3, 2, 1/2, 1/2)
AC.. Zac0 -t . (3, 1/2, 2, 1/2)
AD.. Zad0 -t . (3, 1/2, 1/2, 2 )
Sum = (0, 0, 0, 0 ) # Was (0, -1, -1, -1).
So P2({1}) is held, for 4 candidates.
Case P2({2}): The 4 candidate method passes P2({2}):
AB.. 2t . (3, 2, 1/2, 1/2)
ABC. -t . (3, 2, 1, 0 )
ABD. -t . (3, 2, 0, 1 )
Sum: (0, 0, 0, 0 ) Hence P2({2}) is held
Case P2({3}): This is passed since altering (ABC.) into (ABCD) does not
change the weights.
---------------------------------------------------------------------------
General proof for problems of any size.
The Borda method passes P2. An argument for that follows:
The number of candidates = n, and the
lists are of length k, k+1. sThat tests for P2({k})
For example, a testing for no change of the set of winners on adding
(4:ABC...., -1:ABCD..., -1:ABCE..., -1:ABCF..., -1:ABCG...)
(4:123...., -1:1234..., -1:1235..., -1:1236..., -1:1237...)
Will have n=7, k=3. Let m=(n-k). Replace letters with numbers.
Examples:
case n=7,k=7: weights of (1,2,3,4,5,6,7) are (6,5,4,3,2,1,0)
case n=7,k=3: weights of (1,2,3,0,0,0,0) are (6,5,4,d,d,d,d), m = (n-k) = 4
d = [3+2+1+0]/4, d = [m(m-1)/2]/m = (m-1)/2 = (n-k-1)/2, if m >= 1
Case 1<=k<=n-1 : Let m=(n-k), (k+m)=n, 1<=m<=n-1
1st 3rd...
(1,2,3,...,k ) m.t.(n-1, n-2,... m, d, d, d,... d )
(1,2,3,...,k,k+1) -t.(n-1, n-2,... m, m-1, e, e,... e )
(1,2,3,...,k,k+2) -t.(n-1, n-2,... m, e, m-1, e,... e )
(1,2,3,...,k,k+3) -t.(n-1, n-2,... m, e, e, m-1,... e )
...
(1,2,3,...,k,k+m) -t.(n-1, n-2,... m, e, e, e,... m-1)
Sum: t.( 0, 0, 0, f, f, f,... f )
d = (m-1)/2
e = ((m-1)-1)/2 = (m-2)/2
Where f = t(m.d - (m-1) - (m-1)e)
= (t/2)(m(m-1) - 2(m-1) - (m-1)(m-2))
= (t/2)(m.m - m - 2m + 2 - (m.m - 3m + 2))
= 0
Hence 'Standard Borda' satisfied P2({k}), with k=1,2,3,...n-1.
It also satisfies P2({0}) since adding (t:A, t:B, t:C, ...) will be a sum
of all n possible rotations of the vector:
(n-1, (n-2)/2, (n-2)/2, (n-2)/2,... (n-2)/2), which will equal
(y, y, y, ..., y), where y=((n-1)+(n-1)(n-2)/2)=(2n-2+nn-3n+2)/2=n(n-1)/2
Hence Standard Borda passes P2.
///////////////////////////////////////////////////////////////////////////
D. SAARI BORDA METHOD
The Borda said to be of Donald G. Saari does Not satisfy P2.
Case 3 candidates:
A.. Za0 2t . ( 1, 0, 0) # Last time this was (2,0,0)
AB. Zab0 -t . ( 2, 1, 0)
AC. Zac0 -t . ( 2, 0, 1)
Sum = (-2t,-t,-t)
Adjust: ( 0, t, t)
Hence adding (2t:A, -t:AB, -t:AC) changes the previous sums for candidates
from (sa, sb, sc) into (sa-2t, sb-t, sc-t). If t is positive then adding
those 3 weighted papers CAN cause A to change from a winner into a loser.
Hence this Borda method fails P2({1}), and hence P2.
At 07:25 04.03.00 , Bart Ingles wrote:
>Saari's version would simply collapse unranked choices into one
>position, so the above ranking would receive (1,0,0,0) under his
>method. The ranking A(BC)D would receive (2, 1, 1, 0); under standard
>Borda it would be (3, 1.5, 1.5, 0).
>
That (2, 1, 1, 0) looks arbitrary.
---------------------------------------------------------------------------
"BORDA G" Methods & P2, Methods With Trailing Zero magnitude Weights
These methods resemble what was said to be Saari Borda.
P2 is assumed and that removes a lot of the degrees of freedom.
Free variables remain.
Case: 3 candidates Borda G:
Subcase P2({0}): Passes due to symmetry on summing rotated vectors.
Let the weight of (AB.) & (ABC) be: (K, b, 0)
Let the weight of (A..) be: (1, 0, 0)
P2({2}) is held (the weights of (AB.) and (ABC) are equal).
Subcase P2({1}):
A.. 2t . (1, 0, 0)
AB. -t . (K, b, 0)
AC. -t . (K, 0, b)
Sum: t .(2-2K, -b, -b)
If the sums for candidates were (sa, sb, sc), then adding
(-2t:A, t:AB, t:AC), would make the sums be (sa+t(2h1-2K), sb-tb, sc-tb).
The winner(s) are found on noting the largest.
P2({1}) implies 2-2K=-b : 2K=2+b : K=1+b/2
Solution:
Weight of (AB.),(ABC): (1+b/2, b, 0) : 0<=b<=2
Weight of (A..): (1, 0, 0)
Monotonicity on (AB_)-(BA_) will imply 1+b/2>=b, hence b<=2. Also 0<=b.
First preference P1: shifting votes between (A..) and (AB.) and (ABC)
should make no difference to A's win-lose status. To make the A:B
difference constant, let 1-0 = (1+b/2)-b, hence b=0, and the method
is FPTP. To make the A:C difference constant, again b=0, and FPTP
results.
Constrain Power: Power of a voter, P, is now defined as
Min((Sum over i)[max(x)-x(i)], (Sum over i)[x(i)-min(x)] )
This power-of-a-voter definition could do with a derivation.
P = min( ((1+b/2)-b)+((1+b/2)-0), ((1+b/2)-0)+(b-0) )
= min( 2, 1+3b/2 ) : when 2=1+3b/2 then b=2/3
Solution:
Weight of (AB.),(ABC): (2+b, 2b, 0)/min(4,2+3b) : 0<=b<=2
Weight of (A..): (1, 0, 0)
An approximation to classic Borda, would have 2:1=(2+b):(2b),
4b=2+b, b=2/3, and hence (AB_)'s weights = (8/3,4/3,0)/4 = (2,1,0)/3
-------------------------------------
Case: 4 candidates Borda G:
Subcase P2({0}): Passes due to symmetry on summing rotated vectors.
Let the weight of (ABCD) and (ABC.) be: (J, L, c, 0)
Let the weight of (AB..) be: (K, b, 0, 0)
Let the weight of (A...) be: (1, 0, 0, 0)
P2({3}) is held (the weights of (ABC.) and (ABCD) are equal).
Subcase P2({1}):
A... 3t . (1, 0, 0, 0)
AB.. -t . (K, b, 0, 0)
AC.. -t . (K, 0, b, 0)
AD.. -t . (K, 0, 0, b)
Sum: t .(3-3K, -b, -b, -b)
P2({1}) implies -b = 3-3K : 3K = 3+b : K = 1+b/3
Subcase P2({2}):
AB.. 2t . (K, b, 0, 0)
ABC. -t . (J, L, c, 0)
ABD. -t . (J, L, 0, c)
Sum: t .(2K-2J, 2b-2L, -c, -c)
P2({2}) implies -c = (2K-2J), -c = (2b-2L)
2J = 2K+c = 2(1+b/3)+c : J = (1 + b/3 + c/2)
2L = 2b+c : L = b + c/2
Solution:
Weight of (ABC.),(ABCD): (1+b/3+c/2, b+c/2, c, 0) : 0<=c<=2b
Weight of (AB..): (1+b/3, b, 0, 0) : 0<=b<=3/2
Weight of (A...): (1, 0, 0, 0)
Monotonicity: 1+b/3>=b : b<=3/2
b+c/2>=c : c<=2b
1+b/3+c/2>=b+c/2 : 1>=2b/3 : b<=3/2
Still can't get this method to have truncation resistance without
altering it into SNTV/FPTP.
//////////////////////////////////////////////////////////////////////////
I regard it is a minimum requirement that a method be truncation resistant
for the 1st preference (even if not truncation resistant for the 2nd).
Borda (and Approval) fails that test unless the weights make it SNTV/FPP,
so I consider FPTP to be a better method than both the Borda method and
the Approval Method (by disregarding P2 when this rule is not held).
This following text I wrote, is wrong, because of the division by (K+1).
When the Borda weights in a 2 candidate election are (K, 1), then the
power of those weights is K-1, not K+1.
:At 13:19 03.03.00 , Craig Carey wrote:
:...
:>
:>Unfortunately for Borda, there is no sequence of weights, with the
:> sequence being of any length equalling the number of preferences on
:> the voting paper, where specifying or not specifying the last
:> preference makes no difference to the winners.
:>A method is a bad method if specifying or not specifying the last
:> preference makes no difference. This means that if all the preferences
does make a difference
:> are specified, then having the last preference equal 0, is very
:> different from having it equal 1.
...
:>
:>A. a0
:>AB ab
:>B. b0
:>BA ba
:>
:>Case 1: 1 = num prefs, Weights = (1, 0)/1
:>Case 2: 2 = num prefs, Weights = (K, 1)/(K+1), K>1
...
:>Sa = a0 + ab*K/(K+1) + ba*1/(K+1)
:>Sb = b0 + ba*K/(K+1) + ab*1/(K+1)
...
:> 1 = (K-1)/(K+1). However that function approaches K=1
:> asymptotically.
There is no need to have the last weight <> 0 (i.e., in (K, 1)).
------------------------------------------
The weights of the Approval Voting method may as well be
multiplicatively normalised so as to give each voter equal
power. However that seemed to be opposed.
Regard "power", a person should be able to, as exactly as
possible, oppose the vote of a neighbour that lives over the
fence or any judge across the street.
More information about the Election-Methods
mailing list