[EM] Axioms P3, P2, Truncation Resistance, and 2 candidate solution
Craig Carey
research at ijs.co.nz
Wed Feb 9 07:08:28 PST 2000
Contents:
A derivation of the 2 candidate 1 winner method.
P2 defined.
P3 defined.
Using truncation resistance and vote spreading to discard 54 papers
in the 4 candidate problem.
A comment on the A1 meta-axiom of a preferential voting theory
At 18:17 09.02.00 , Rob Lanphier wrote:
>The truncation resistance criterion has come up a number of times on this
>list as a justification for/against some methods. Has there been any
>attempt to create a compelling mathematical formula for this, where
>someone can objectively apply the formula to a given method to determine
>if a voting method is "truncation resistant"?
Truncation resistance is rather easily defined. Let trunc(V,c) be a
function that truncates all preference lists on papers immediately
after the preference for candidate c. Here's a definition of
Truncation Resistance:
(All c)(All U,V)[(U = trunc(V,c)) => ((c in W(U)) = (c in W(V)))]
It can be converted in a REDLOG form and evaluated on a computer
(perhaps too slowly to be practical, though):
U =
uaa A ua=uaa+uab+uac
uab AB
uac AC
ub B
uc C
V =
vaa A va=vaa+vab+vac
vab AB
vac AC
vb B
vc C
ta = (U = trunc(V,A)) = (uaa=vaa+vab+vac)(uab=0)(uac=0)(ub=vb)(uc=vc)
tb = (U = trunc(V,B)) = (uaa=vaa)(uab=vab)(uac=vac)(ub=vb)(uc=vc)
= (U = trunc(V,C))
simpu = (0<=uaa)(0<=uab)(0<=uac)(0<=ub)(0<=uc)(uaa+uab+uac+ub+uc<=1)
simpv = (0<=vaa)(0<=vab)(0<=vac)(0<=vb)(0<=vc)(vaa+vab+vac+vb+vc<=1)
Let wvj = (j in W(V)) = (j is a winner of V)
TR := rlqe rlall ((simpu.simpv) => (ta => (wua = wva)))
TR is true iff truncation resistance is held.
The operator "rlqe rlall" is 2 REDLOG operators that return the Boolean
value true if and only if the RHS term is true for all values of the
10 free variables. I.e. it is a "(For All)" operator (existential
logic), that is true iff the polytope is not empty.
This STV-style "truncation resistance" can break problems into smaller
problems. Some examples ("#S" is the number of elements in set S):
Case (1 = #W)&(3 = #Candidates) :
(a in W(V)) = (not b in W(V))(not c in W(V))
= (not b in W(trunc(V,{A,B})))(not c in W(trunc(V,{A,C})))
If V was fully general with 15 papers A,AB,ABC,AC,ACB,B,BA,BAC,BC,BCA,
C,CA,CAB,CB,CBA, then trunc(V,{A,B}) has the 5 papers A,B,C,CA,CB.
So assuming truncation resistance reduces the problem to a subproblem
of solving an election with 5 papers.
Case (2 = #W)&(3 = #Candidates) :
(a in W(V)) = (not b in W(V)) or (not c in W(V))
= (not b in W(trunc(V,{A,B}))) or (not c in W(trunc(V,{A,C})))
Again there is a reduction to 5 papers.
---------------------------------------------------------------------
Case (1 = #W)&(4 = #Candidates) : "One winner four candidates"
There 64 papers (or 40 if the last preference is ignored):
A,AB,ABC,ABCD,ABD,ABDC,AC,ACB,ACBD,ACD,ACDB,AD,ADB,ADBC,ADC,ADCB;...
Write W=W(V), kWj=(k in W(trunc(V,{j})).
aW = -bW.-cW.-dW = -bWab.-cWac.-dWad
bWab = -aWab.-cWab.-dWab = -aWab.-cWabc.-dWabd
-aWab = (bWab or cWabc or dWabd). ......
It seems to be not possible to remove terms having truncation done
wrt. only 2 variables.
The term bWab is a Boolean function depending on counts for these
papers:
A, B, C, CA, CB, CD, CDA, CDB, D, DA, DB, DC, DCA, DCB
The papers C, CD, D, DC can be eliminated by making the winner set
invariant to adding papers:
(1)** (+3x:C, -x:CA, -x:CB, -x:CD)
(2) (+3x:D, -x:DA, -x:DB, -x:DC)
(3)** (+2x:CD, -x:CDA, -x:CDB)
(4) (+2x:CD, -x:DCA, -x:DCB)
Those are P2(1) and P2(2) rules.
In eqn (1), a Condorcet style pairwise comparison between candidates x
and y can be done by first truncating after preferences for x and y.
The changes in votes are:
C:any = 0:0
A:B = -x:-x
A:D = -x:-x
B:D = -x:-x
So (1) makes no difference to Condorcet pairwise relative vote sums.
In eqn (3), the changes in Condorcet sums are as follows.
C:any = 0:0
A:B = -x:-x
A:D = 0:0 (since the truncated papers = (+2x:CD, -x:CD, -x:CD)
B:D = 0:0
So, for the 4 candidates 1 winner example, eqns (1) to (4) are in a
degree of sympathy with Condorcet pairwise comparing ideas.
When the 4 constraints (1) to (4) are applied, the papers reduce to
just 10 in number (ten, not 5):
A, B, CA, CB, CDA, CDB, DA, DB, DCA, DCB
[That makes a 4 candidate solution a problem of dividing up a simplex
in 9 dimensions.]
Rules (1) to (4) are instances of a rule/axiom I call "P2". I hadn't
got around to describing it to the mailing list so I may as well do
that (although it has been glimpsed at before in other's messages).
----------------------------------------------------------------------
Axiom P2
Spreading votes equally across permuations of added preferences
leaves the set of winners unaffected.
P2(0) 0th: Adding (x:A, x:B, x:C, ...) to an election makes no
difference to the set of winners
P2(1) 1st: This the rule of which this is an instance:
If the candidates are A,B,C,D,E, then the set of
winners does not change for these alterations:
(4:A)--(1:AB,1:AC,1:AD,1:AE).
(4x:B)--(x:BA,x:BC,x:BD,x:BE).
P2(2) 2nd: Altering (3:AB) to/from (1:ABC,1:ABD,1:ABE) makes no
difference to the set of winners.
P2(2,3): 2nd & 3rd: The set of winners is unaltered when this
alteration occurs:
(6:AB)--(1:ABCD,1:ABCE,1:ABDC,1:ABDE,1:ABEC,1:ABED).
etc.
----------------------------------------------------------------------
Hopefully some check of STV against this P2 might be described.
Possible nomenclature: P1 smudges votes and P2 spreads them
Here is another axiom that allows a derivation of the winner to
the 1 winner 2 candidate problem:
Here is my Axiom P3
----------------------------------------------------------------------
Axiom P3
The number of winners and losers are both correct and their sum
equals the number of candidates.
----------------------------------------------------------------------
Condorcet is rejected by P3.
STV is failed by P1 (what of P2?).
The 2 axioms P2, P3, can allow a solution to the 1 winner 2 candidate
problem to be derived. The solution to that problem can't simply be
written down because that would be a stating of an axiom [something
in the theory that is true and not derived].
V =
A aa
AB ab
B bb
BA ba
a = aa+ab, b = bb+ba
The winners of V are, by P2(1), the winners of this:
U =
A a
B b
Case a<b: the winners of U are the winners of this, by P2(0):
A 0
B b-a
That is now a 1 candidate problem. By P3, the winner is B.
Similarly for the other case where b<a.
Hence, the solution to the 1 winner 2 candidate problem (i.e. V),
is:
bb+ba<aa+ab => Winners = {A}
aa+ab<bb+ba => Winners = {B}
This solution is founded upon axioms that may be highly controversial.
P2 and P3 appear to be able to make First Past the Post be correctly
embedded in derived solutions.
My A1 axiom, which said that the only global aim ("politicians") would
be "proportionality", would be wrong if P3 was not a corollary of
proportionality. If 12 candidates needed to be won and only 10 were
elected, then 2 may regard that voters' votes were not actually
distributed proportionally amongst the 12 leading candidates.
A point to note is that in axiom based methods, reducing the number
of papers is of interest.
The above is just a description of my IFPP, which seems to me to be
based on meta-axiom A1.
Mr G. A. Craig Carey
Auckland, New Zealand, 10 February 2000
More information about the Election-Methods
mailing list