[EM] (P1) tweak up of AV meth. using random walk may fail

[Blake Cretney]

Craig Carey wrote:

> >It's almost always easier to prove that a method fails a criterion
> >than that it passes one.  It makes sense to try to find a
> >counter-example before trying to find a proof.
> 
> I could be given an estimate of a metric of the complexity of the
> program
>  that numerically found the result, if any.

I just tried some examples.  I had an idea of the kind of thing that
would cause a monotonicity violation, so I just modified the example
until I got it right.  It was fairly easy.  Much simpler than writing
a program or finding a proof.

> It is my contention, backed up by the evidence I gave
> >previously, that AVQ meets P1.
> 
> I am sure that would be wrong if AVQ was defined in a way that was
>  an actual definition. 

In what way is it not an "actual definition".  It is a procedure
which you can carry out for any example you like.
 
1.  Check to see if any candidates get more than 1/3 of the 1st
preferences.  If not, the winner is the candidate with the most 1st
preferences (like FPP).  Otherwise, go to step 2.
2.  Eliminate all candidates with 1/3 or under of the 1st
preferences.  These candidates are eliminated from ballots in the same
way candidates are eliminated in AV.
3.  Hold an AV election between the remaining candidates.
 
Is there any part of that procedure that you do not view as
sufficiently defined?

> A method won't pass (P1) if all the surfaces do not meet properly and 
> form a gentle piecewise-flat surface.  Any method with an "if then else" 
> in it, comes under more suspicion of failing (P1). Your AVQ has this 
> feature: "if all are rejected at any stage then one will be picked".

Are these assertions based on anything other than intuition?  Isn't
it possible that P1 does not relate to a smooth graph?  Isn't it
possible that a smooth graph is totally meaningless?

If not, just graph AVQ.  The rough spots you predict must then
correspond to P1 violations.  Just pull one out, and prove that AVQ
violates P1.  Otherwise, you will have to face the possibility that
your intuition is incorrect, and that either AVQ gives a smooth graph
or P1 does not imply a smooth graph.

> >That's why I favour Condorcet-type methods.  Let me point out that
> >both AV1 and AVQ suffer from vote-splitting, and therefore may be
> >considered to waste votes.
> 
> What's the reason why. 

You snipped it out, but originally, you said 

> Ideally the 100th preference should if possible,
> have the same power and influence as a first preference, contrary
> to the nature of STV.

Methods that consider candidates two-by-two (pairwise) have this
property.  I'm going to describe such a method further down.

> Condorcet is a method that returns the wrong
>  number of winners. As far as it goes (which isn't far) , it satisfies
>  (P1).

When I said Condorcet-type methods, I meant methods that meet the
Condorcet criterion.  There are lots of suggested methods along these
lines, however, I am going to describe one of the better ones,
Tideman's method.

Compare every candidate to every other to get one-on-one (pairwise)
majority decisions.  That is, if there are candidates X and Y, you
would find out how many people rank X over Y, and how many rank Y over
X.  Then, the candidate with more votes is said to have a majority
over the other, with a margin of whatever the difference is.

For example, if 30 people vote X over Y, and 20 vote Y over X, I will
say that X has a majority over Y with a margin of 10.  

Next, find the majority with the greatest margin.  This decision
becomes locked, so that if it says that X has a majority over Y, we
resolve to rank X over Y in our final result.

The process continues, locking majority after majority, in order of
their margins.  It is possible, that we will get to a majority that
cannot be locked because this would create a contradiction.  For
example, if we have resolved to rank X over Y and Y over Z, we cannot
lock a majority that would have us rank Z over X.  A majority of this
type is skipped.  That is, we ignore it and proceed to the next one.

Once all the majorities have been processed in this way, a complete
ranking from first to last will have been made.  This process is no
more likely to tie than other methods, like AV.

Here is an example

18 A B C D
17 B C A D
16 C A B D
49 D

Now, even though there is no Condorcet Winner, Tideman's method has
no problem.

A vs B 34-17=17
B vs C 35-16=19
C vs A 33-18=15
A,B,C vs D 51-49=2

So, we 
lock B over C [19]
lock A over B [17]
skip C over A [15] as this would cause a contradiction
lock D over A, B, and C [2], it doesn't matter what order we do this
in, the result is the same.

So, A>B>C>D

> Vote splitting (of some sort) is an ineradicable feature of the very
> best
>  methods, to the approx detriment of the populace that has to vote in
>  such methods.

It may well be ineradicable in methods that meet P1.  However, I can
see no reason to believe that these methods are the best, or even
good.

> >As a criterion for excluding spoilers, I prefer the Local
> >Independence from Irrelevant Alternatives Criterion (LIIAC).  I have
> >no idea what they mean by "Local".  But in any case, this criterion
> >says that you should find the smallest non-empty set of candidates
> >such that no candidate outside the set is majority preferred to any
> 
> This is pairwise comparing idea, an idea of much reduced credibility
>  (ref. Condorcet) due to the failure to remain plausible in any
> idiot's
>  opinion when applied to extremely large problems.
>
 
I think I have made clear with my example of Tideman's method that it
is possible to have a pairwise method, meeting the Condorcet
Criterion, which is not overly prone to ties.  Is that what you are
referring to?

> Is there a dispute over whether is it essential to make it an axiom,
> that
>  the method return the right number of winners?.
> 
> I regard it as vital that the method get the right number of winners.
>  That simplifies derivations from rules.

Just because LIIAC says that certain candidates should not effect the
result (and should not win), does not mean that all the remaining
candidates must be declared co-winners.  In my example for Tideman's
method, only D was excluded from having an influence by LIIAC, but a
single winner was still chosen.  Tideman passes LIIAC, but without any
indecision as a result.
 
> >However we define "dead loser", we would not expect that a dead loser
> >would be preferred by a majority to a viable candidate.  LIIAC
> >guarantees that if you have a bunch of "dead" candidates, none of
> whom
> >are preferred to any of the viable candidates, none of the dead
> >candidates can affect the election outcome.
> 
> What are the winners?. The price of getting any sized winner set the
>  method feels in the mood for, is just too high. A 2nd election could
> be
>  done, but it is, is it not, that a LIIAC method could fail to find
> even
>  one loser?.
> 

LIIAC is not a method.  It is a criterion.  It differentiates between
methods.  It is not itself a method.  Methods like Tideman can both
pass criteria like LIIAC and be unlikely to tie.

> STV's SPC should not be lost, since it is a tremendous simplifier of
> the
>  mathematics. Once SPC is imposed, STV ends up being the only known
>  choice ?, for 20 or more candidates, and when there are less.
> 

Some methods that pass SPC are FPP, AV, and AVQ.  Are you really
saying that you favour SPC just because it excludes lots of methods,
and therefore simplifies your choice?  I feel that you must have some
other justification for defending a criterion that you yourself admit
results in significant problems.  All known methods that pass it
either violate monotonicity or have vote-splitting.

---
Blake Cretney