[EM] Burial examples

[Kristofer Munsterhjelm]

First of all, I'm not sure if it's "dominant mutual third" or "mutual
dominant third". If I got it wrong, I apologize :-)

I was reading through some past posts here and got the impression that
some were considering Smith,Plurality to be resistant to burial. Then I
found a counterexample. In case it's of use to others, I'll put it here:

10: A>B>C
11: B>A>C
3: C>A>B

A is the CW. Now let the B voters bury A:

10: A>B>C
11: B>C>A
3: C>A>B

There's now an ABCA cycle and B wins.

If I've understood the criterion correctly, this example shows that
Smith,Plurality fails weak burial resistance/unburiable DMT, because if
we let the DMT set be {A}, then

A is ranked above A_comp = {B, C} on more than a third = 8 ballots
A beats B and C pairwise (since A is the CW)
but the example shows we can alter B-first ballots to change the winner
from A to B.

==

I then thought I'd find other burial examples.

Smith,Plurality and Smith, Antiplurality both fail weak burial resistance:

10: A>B>C
6: B>A>C
5: B>C>A
3: C>A>B

A is the CW. Bury A on 5 BAC ballots:

10: A>B>C
1: B>A>C
10: B>C>A
3: C>A>B

we have an ABCA cycle and B is both the Plurality and Antiplurality winner.

-

Smith, Coombs:

6: A>B>C
5: A>C>B
2: B>A>C
10: B>C>A
2: C>A>B

A is the CW. Bury A on the two B>A>C ballots:

6: A>B>C
5: A>C>B
12: B>C>A
2: C>A>B

ABCA cycle. A has the greatest number of last place votes and so is
eliminated first by Coombs, then B beats C pairwise, so B wins.

-

Baldwin:

10: A>B>C
4: B>A>C
3: C>A>B
7: C>B>A

Bury A on the BAC ballots:

10: A>B>C
4: B>C>A
3: C>A>B
7: C>B>A

A is eliminated first, then B beats C pairwise. According to
http://www.cs.wustl.edu/~legrand/rbvote/calc.html, Raynaud also elects B
with positive probability.

-

Passing dominant mutual quarter burial resistance is really hard, if
even possible:

7: A>B>C
9: B>A>C
6: C>A>B
2: C>B>A

A is the CW. Now bury A on the BAC ballots:

7: A>B>C
9: B>C>A
6: C>A>B
2: C>B>A

Pretty much every method elects B here.

==

Some thoughts: I've been investigating a particular type of Condorcet
methods on and off. These are three-candidate methods where the CW wins
if there is one, otherwise I relabel all the candidates so there's an
ABCA cycle and the candidate I want to find the score of is A. Then that
candidate's score is f(ABC, ACB, ..., CBA) for a custom function f. I've
run some tests (using a combination of IC and Gaussian models) to see
what sort of strategic susceptibility the different choices of f give.

I've been noticing that methods that pass both monotonicity and reversal
symmetry can't seem to go below 45-50% strategy susceptibility (meaning
half of the randomly chosen elections let one of the losers alter their
ballots so that the loser wins). In contrast, the best methods that pass
only one of the two can get down to around 10%. (Minmax gets around 70%,
and the best I've seen so far from methods that are neither is 5%)

Perhaps DMTBR/UDMT is the thing that separates the good performers of
the second category from those of the first; and perhaps it's impossible
to have all of Condorcet, monotonicity, reversal symmetry, and
DMTBR/UDMT. If I find more time, I might try to devise a proof of
that... if the "perhaps" is true.
----
Election-Methods mailing list - see http://electorama.com/em for list info

[Chris Benham]

Post by Kristofer Munsterhjelm
Passing dominant mutual quarter burial resistance is really hard, if

I am sure that for a Condorcet method it isn't possible.

Meeting dominant mutual third burial resistance isn't so easy.  I don't
know of any Condorcet method
that does that is better than the "Hare-Condorcet hybrid".

The version I like: voters strictly rank from the top as many or as few
candidates as they wish. If there is
a CW (or single pairwise-undefeated candidate?) x then elect x.
Otherwise eliminate the candidate that (among remaining candidates) is
voted top-most on the fewest
ballots and if among remaining candidates there is pairwise-beats all
candidate (or single pairwise-undefeated
candidate?) x then elect x.  If not, repeat and so on.

But it fails mono-raise and can fail to elect a positionally dominant
uncovered candidate, unlike my other
favourite Condorcet methods.

It comfortably handles your four burial scenario examples. In the first
three the burying has no effect and in
the fourth it backfires.

My other favourite Chicken Dilemma criterion complying Condorcet method,
MMLV(erw) Margins-Sort Elimination,
also easily elects the sincere CW in the first 3 examples but the burial
succeeds in the fourth.

https://wiki.electorama.com/wiki/Chicken_Dilemma_Criterion

I first suggested that method in a post to EM on 18 April 2015.
http://lists.electorama.com/pipermail/election-methods-electorama.com/2015-April/000007.html

*Voters rank the however many candidates they wish, equal-ranking
allowed.  In determining pairwise scores
a ballot that equal-ranks above bottom candidates A and B gives a whole
vote to each, a ballot that votes
them equal-bottom (i.e. above no other candidate/s) give no vote to
either and a ballot that votes A above B
gives 1 vote to A and nothing to B.

Give every candidate a score equal to her/his smallest losing pairwise
score.  List them in order of score.
If the list is in "pairwise order" (i.e. the candidate with the highest
score pairwise beats the candidate with
the second highest score who in turn pairwise beats the candidate with
the third highest and so on) then
elect the candidate at the top of the list.

If not, then swap the places in the list between the two adjacent
candidates who are pairwise out of order by
the smallest margin.  If two or more are out of order by the same
margin, then swap the pair that is lowest on
the list.  Repeat until the whole list is in pairwise order.

If no more than 3 candidates are on the list, elect the candidate on top
of the list. Otherwise eliminate the
candidate on the bottom of the list and repeat (ignoring eliminated
candidates) as many times as needed.*

Taking your first example:

10: A>B
11: B>C (sincere is B>A)
03: C>A

C>A 14-10,   A>B 13-11,  B>C 21-3.

Scores:  B11   A10   C3

Both BA and AC are pairwise out of order.  The score margin between B
and A  is 1 (11-10)  and the score margin
between A and C is 7 (10-3).   So the pair with the smallest margin swap
places and now no adjacent pair is pairwise
out of order and only 3 candidates are on the list  (A>B>C) so A (the
sincere CW) now being on top of the list, wins.

Chris Benham

Post by Kristofer Munsterhjelm
First of all, I'm not sure if it's "dominant mutual third" or "mutual
dominant third". If I got it wrong, I apologize :-)
I was reading through some past posts here and got the impression that
some were considering Smith,Plurality to be resistant to burial. Then
I found a counterexample. In case it's of use to others, I'll put it
10: A>B>C
11: B>A>C
3: C>A>B
10: A>B>C
11: B>C>A
3: C>A>B
There's now an ABCA cycle and B wins.
If I've understood the criterion correctly, this example shows that
Smith,Plurality fails weak burial resistance/unburiable DMT, because
if we let the DMT set be {A}, then
A is ranked above A_comp = {B, C} on more than a third = 8 ballots
A beats B and C pairwise (since A is the CW)
but the example shows we can alter B-first ballots to change the
winner from A to B.
==
I then thought I'd find other burial examples.
Smith,Plurality and Smith, Antiplurality both fail weak burial
10: A>B>C
6: B>A>C
5: B>C>A
3: C>A>B
10: A>B>C
1: B>A>C
10: B>C>A
3: C>A>B
we have an ABCA cycle and B is both the Plurality and Antiplurality winner.
-
6: A>B>C
5: A>C>B
2: B>A>C
10: B>C>A
2: C>A>B
6: A>B>C
5: A>C>B
12: B>C>A
2: C>A>B
ABCA cycle. A has the greatest number of last place votes and so is
eliminated first by Coombs, then B beats C pairwise, so B wins.
-
10: A>B>C
4: B>A>C
3: C>A>B
7: C>B>A
10: A>B>C
4: B>C>A
3: C>A>B
7: C>B>A
A is eliminated first, then B beats C pairwise. According to
http://www.cs.wustl.edu/~legrand/rbvote/calc.html, Raynaud also elects
B with positive probability.
-
Passing dominant mutual quarter burial resistance is really hard, if
7: A>B>C
9: B>A>C
6: C>A>B
2: C>B>A
7: A>B>C
9: B>C>A
6: C>A>B
2: C>B>A
Pretty much every method elects B here.
==
Some thoughts: I've been investigating a particular type of Condorcet
methods on and off. These are three-candidate methods where the CW
wins if there is one, otherwise I relabel all the candidates so
there's an ABCA cycle and the candidate I want to find the score of is
A. Then that candidate's score is f(ABC, ACB, ..., CBA) for a custom
function f. I've run some tests (using a combination of IC and
Gaussian models) to see what sort of strategic susceptibility the
different choices of f give.
I've been noticing that methods that pass both monotonicity and
reversal symmetry can't seem to go below 45-50% strategy
susceptibility (meaning half of the randomly chosen elections let one
of the losers alter their ballots so that the loser wins). In
contrast, the best methods that pass only one of the two can get down
to around 10%. (Minmax gets around 70%, and the best I've seen so far
from methods that are neither is 5%)
Perhaps DMTBR/UDMT is the thing that separates the good performers of
the second category from those of the first; and perhaps it's
impossible to have all of Condorcet, monotonicity, reversal symmetry,
and DMTBR/UDMT. If I find more time, I might try to devise a proof of
that... if the "perhaps" is true.
----
Election-Methods mailing list - see http://electorama.com/em for list info

---
This email has been checked for viruses by AVG.
http://www.avg.com

----
Election-Methods mailing list -

[Kristofer Munsterhjelm]

Post by Chris Benham

Post by Kristofer Munsterhjelm
Passing dominant mutual quarter burial resistance is really hard, if

I am sure that for a Condorcet method it isn't possible.
Meeting dominant mutual third burial resistance isn't so easy.  I don't
know of any Condorcet method
that does that is better than the "Hare-Condorcet hybrid".
The version I like: voters strictly rank from the top as many or as few
candidates as they wish. If there is
a CW (or single pairwise-undefeated candidate?) x then elect x.
Otherwise eliminate the candidate that (among remaining candidates) is
voted top-most on the fewest
ballots and if among remaining candidates there is pairwise-beats all
candidate (or single pairwise-undefeated
candidate?) x then elect x.  If not, repeat and so on.
But it fails mono-raise and can fail to elect a positionally dominant
uncovered candidate, unlike my other
favourite Condorcet methods.

My investigations seem to suggest that we can have mono-raise without
affecting strategic susceptibility too much; or rather, without doing so
as long as the Smith set is of three candidates or fewer.

Because of a combinatorial explosion, it's very hard to use the approach
I am using to go beyond three-candidate methods, however, which limits
what I can do.

I would ultimately want to find a method that is as strategically robust
as a Hare-Condorcet hybrid while retaining clone independence and
without having to give up mono-raise, and beyond that pass as many
criteria as possible. (I'd also like to find out if Smith and
mono-add-top are compatible.) Finding out if reversal symmetry is
compatible with DMTBR and Condorcet would help narrow down the criteria
such a "better method" could have.

My approach so far has been to look at what three-candidate methods my
programs find, and then try to extend them. However, they are often hard
to understand. Suppose the simulator finds out that a method where A's
score in an ABCA cycle is (2 * fpA + fpB - 2 * fpC) is a good one (where
fpX is the number of ballots ranking X first). What's going on here and
how would it be generalized? There's no obvious answer. It gets even
worse with nonlinear methods, as the methods may seem stranger still.
E.g. the simulator might say that a method where A's score in an ABCA
cycle is (max(C>A, B>C)/C>A) is a good one, but why?

Thus my attempt to find a criterion or criteria to distinguish good
methods from bad ones. And thus my interest in DMTBR.

Would Uncovered,IRV be a better method? Or "eliminate and stop when one
candidate covers everybody else"?

Post by Chris Benham
It comfortably handles your four burial scenario examples. In the first
three the burying has no effect and in
the fourth it backfires.
My other favourite Chicken Dilemma criterion complying Condorcet method,
MMLV(erw) Margins-Sort Elimination,
also easily elects the sincere CW in the first 3 examples but the burial
succeeds in the fourt
https://wiki.electorama.com/wiki/Chicken_Dilemma_Criterion

Chicken Dilemma doesn't seem to be that criterion, at least not on its
own, because as far as I understand it, Smith,Plurality passes it. And
Smith,Plurality's performance is even worse than that of the methods
that reduce to minmax.

Of course, it's possible to argue against my simulations by saying it
counts what can be measured rather than measures what counts; more
specifically, that CD violation is a far more serious problem as it
induces a more destructive form of strategy. But that'd be more a reason
to want both CD and DMTBR than to say CD is the criterion that
distinguishes strategy-resistant methods from methods that aren't.

Post by Chris Benham
10: A>B
11: B>C (sincere is B>A)
03: C>A
C>A 14-10,   A>B 13-11,  B>C 21-3.
Scores:  B11   A10   C3
Both BA and AC are pairwise out of order.  The score margin between B
and A  is 1 (11-10)  and the score margin
between A and C is 7 (10-3).   So the pair with the smallest margin swap
places and now no adjacent pair is pairwise
out of order and only 3 candidates are on the list  (A>B>C) so A (the
sincere CW) now being on top of the list, wins.

That's interesting. Maybe I should try to make DMTBR failure examples
for maximal sets of the voting methods implemented by LeGrand's voting
calculator. In particular, Raynaud and Baldwin seem to have different
enough logic that examples that work on the Plurality-like methods don't
work on them.

Copeland and Small don't allow for any decisive (B wins with certainty)
three-candidate examples, but arguably fail outright because B has a
nonzero chance of winning as soon as the cycle is established.
----
Election-Methods mailing list - see http://electorama.com/em for list i