[EM] No luck with simple monotone Heaviside methods, but a surprising idea

[Kristofer Munsterhjelm]

So I was trying to find some methods that would have impartial culture 
manipulability less than 100% of the time for four candidates as the 
number of voters approaches infinity. (I should strictly speaking say 
that I don't know if any methods stay below 100% here, but I had the 
impression that IRV does.)

I did some brute forcing of methods of the type

A's score = f(A) = sum over other candidates B != A:
	A>B *
	product over other candidates C, D not A nor B:
		H(x_1 * [fpA fpB fpC fpD]) *
		H(x_2 * [fpA fpB fpC fpD]) *
		H(x_3 * [fpA fpB fpC fpD])

highest score wins, with x_1, x_2, x_3 being vectors, and fpX being the 
first preference count of candidate X. This is a generalization of the 
Contingent vote,

f(A) = sum over B
	A>B *
	product over C:
		H(fpA - fpB) * H(fpB - fpC)

where H(x) as usual is the function
	H(x) = 0   if x < 0
                1/2 if x = 0
                1   otherwise

As a simple monotonicity check I used the possibly too generous 
assumption that if we write the first term
	H(x_1 * [fpA fpB fpC fpD])
as
	H(x_11 fpA + x_12 fpB + x_13 fpC + x_14 fpD)
then if x_11 >= max(x_12, x_13, x_14), then a voter who ranks say C 
first, can't harm A by raising A to top, because the benefit to the term 
inside the H can never decrease by doing so. So the method must be 
monotone since the A>B term is also monotone, hence the check x_11 >= 
max(x) is sufficient (but probably not necessary) for monotonicity.

The results show a big nope: every such method (with the values of x 
integer between 2 and -2 inclusive) seem to be 100% manipulable in the 
limit. However, it did come up with this, which seemed to converge less 
quickly, and might be an interesting idea on its own:

f(a) = sum (or max) over B:
	A>B * H(fpA + fpB - fpC - fpD)

I.e. for four candidates, there'll always exist at least one pair of 
candidates who have more than majority combined first preference support 
(unless there's a four-way tie). Give each candidate in this pair his 
pairwise defeat strength against the other.

(In the case where there are multiple, e.g. a single candidate has 
majority, using sum would give a different method than using max.)

-km