[EM] Axioms P3, P2, Truncation Resistance, and 2 candidate solution

[Craig Carey]

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