[EM] Poking about Heaviside methods, again

[Kristofer Munsterhjelm]

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. 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