[EM] Poking about Heaviside methods, again

[Forest Simmons]

On Thu, Jan 5, 2023, 9:24 AM Kristofer Munsterhjelm <km_elmet at t-online.de>
wrote:

> Happy new year!
>
> Now that it's a new year, I've done a bit more exploring around the
> low-manipulability generalizations of the contingent vote. My summary
> would be this:
>
> - I found one bug, but not all, that caused the Python vote simulator to
> give different results to quadelect. As I haven't found all, the stuff
> below still hasn't been fully verified.
>
> - There's a strange pattern where every method (if not augmented by
> Condorcet) seems to have almost all its strategy vulnerability as
> compromising. More later.
>
> - An interesting pattern seems to be: nonmonotone CV generalizations
> work by "If A and B are at the top by first preferences, then credit A
> with A>B and B with B>A". Monotone ones are about absolute comparisons
> instead: "if A and B combined are above some quota, then...".
>
> - For monotone "CW if there is one, otherwise method X", the best
> impartial culture generalization for four candidates goes like this:
>         Let A and B be two candidates. Then if for every other candidate
> C, fpA
> + fpB - 2 fpC > 0, let A's score in the (A,B) comparison be A>B and B's
> score be B>A. If they're all < 0, it's zero for both.
>         Let every candidate A's score be the maximum of any comparison
> involving A.
>         Highest score wins unless there's a CW. If there is, the CW wins.
>
> - According to quadelect, this achieves roughly 66% strategy
> vulnerability on four candidates and 97 voters. The variant with sum
> instead of max gets 70%.
>
> - The best nonmonotone method of this form is Condorcet//contingent
> vote. Its susceptibility is 60% with max and 57% with sum.
>
> - Including terms involving first preferences after elimination can
> improve the results quite a bit, but the resulting methods are
> completely incomprehensible. Here's an example for four candidates, that
> *should* be monotone although I haven't checked:
>         - Let A and B be two candidates. Then if, for every pair {C, D} of
> other candidates, if fpA\C + fpB\C - fpD\C -fpD > 0, A's score is (A>B)
> and B's is (B>A). Otherwise if all are <0, it's zero for both. fpX\Y
> here is my terminology for "X's first preference count once Y has been
> eliminated".
>         - The rest is as above (including the use of the max operator).
>
> - That method has 53% strategic susceptibility under the given conditions.
>
> ----
>
> So lots of strange things. I'm kinda understanding the limitations of
> not having a theory; the simulator can come up with some generalization
> that seems to work, but I have no idea why it works. Leaving elections
> to a black box isn't really a good idea, either :-) What's necessary
> here, I think, is some kind of explanation for just why these are
> resistant to strategy and others are not, and I don't know what that
> would look like.
>
> The pattern seems to be that if A's score is a transformation of some
> linear combination of first preferences, and the method is monotone,
> then clearly there won't be any burial incentive because lowering A's
> rank can't harm A as nobody who prefers to B as A has A as their first
> preference anyway.
>
> And obviously sums of these and maxima of these retain the property.
>
> The surprising part is that sometimes, you can include pairwise counts
> and it's still all compromise all the time. E.g. the contingent vote:
>
>         f(A) = sum over {A, B}:
>                 H(fpA - fpB) *
>                         product over C not in {A, B}:
>                                 H(fpB - fpC)
>                 * A>B.
>
> where f(A) is A's score and H is the step function.
>
> Even the weird method
>         f(A) = max over B: A>B
>
> seems to have a very low (though nonzero) rate of burial.


This weird fact suggests to me the following Banks efficient method:

Start a pairwise defeat chain A>B with the greatest strength defeat pair
A>B.

Then of all the X that defeat both A and B, let X1 be the one with the
greatest defeat against A, and then augment the chain with X1 to get X1>A>B.

Then ...

While some X defeats every member of the chain, augment the chain with the
X that has the strongest defeat against the newest member of the chain.
EndWhile

Elect the head of the resulting maximal chain.

Note that if there are only three candidates and those three are in a cycle
ABCA, then this method will elect
A=argmax f(X).

-Forest


Why? You'd
> imagine that if A is tying C, and A>B is A's max pairwise victory over
> someone else, then the buriers can benefit by burying A under B; and
> that that would happen pretty frequently.
>
> On the other hand,
>
>         f(A) = sum over B: H(A>B - B>A)
>
> is just Copeland, which has *plenty* of burial incentive. Yet it looks
> superficially like the other methods: monotone transformations of linear
> combinations of pairwise victories. How about if we only allow a single
> victory inside the monotone transformation, something like
>
>         f(A) = sum over B: (A>B)^x
>
> with x>1? Is that also only compromise?
>
> -km
> ----
> Election-Methods mailing list - see https://electorama.com/em for list
> info
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20230107/ec33ba0c/attachment.htm>