[Election-Methods] voting research

[Kristofer Munsterhjelm]

Warren Smith wrote:
> The whole thing about optimal strategy in IRV
> being NP-complete, is a crock of shit.
> 
> 1. USUALLY it is EASY to find a BETTER-than-honesty
> strategy in IRV.  This is not just me ranting.
> It is in fact a published theorem.

I'm not familiar with that. Are you referring to some single-winner 
equivalent of vote management, or to your rangeVirv and TarrIrv pages?

> 2. The NPC proof does not matter since it is about
> not the usual case, but the hardest-to-strategize case.
> And it is not about finding a good strategy, it is about
> finding the best strategy.
> This theorem is utterly irrelevant to reality
> and discussing it in the manner you (K.M.) just did
> is an abomination.

I suggested that since the simulations showed that IRV was hard to 
manipulate, the usual cases were close to the phase transition where 
things get hard in the average case.

But since the paper only holds for extreme numbers of voters and 
candidates, I have to withdraw that.

> 3. The NPC proof also does not matter since it is about the
> case where the #candidates goes to infinity at the same rate as the #voters.
> That is utterly irrelevant to reality. There is a P-time
> algorithm for best strategy if C grows like O(logV) or
> slower.  That is reality.

Oh well, so much for that. What can be salvaged from the strategy 
hardness idea is this:

Under certainty, with individual voters, manipulation is easy (because 
with the number of candidates given, the number of possible ranked 
ballots turns into a constant).

With individual voters and uncertainty, or groups of voters, weighted 
ballots, and certainty, the following holds:

It's NP-hard to force a candidate to win, under the constraints given, 
with Borda, Antiplurality, and STV for 3 candidates or more, or with 
Copeland and minmax for 4 candidates or more.

It's NP-hard to keep a candidate from winning, under the constraints 
given, with STV for 3 candidates or more. (In the other systems, that 
can be done in polynomial time)

The relevant papers are:  "Complexity of manipulating elections with few 
candidates" and "How Many Candidates Are Needed to Make Elections Hard 
To Manipulate", both by Conitzer and Sandholm.

C&S wrote a paper, "Nonexistence of Voting Rules That Are Usually Hard 
to Manipulate", stating that in the unbounded candidate-unbounded voter 
case, it's impossible to make a monotonic deterministic rule that is 
hard to manipulate in the average case. I do not know of any such result 
for the bounded incomplete information/weighted coalition case, though.

Even if it turns out that it's impossible to make an average case 
nonmanipulable rule for the incomplete/coalition case, presumably having 
worst-case NP-completeness is better than nothing, and if a simple rule 
like Copeland can satisfy it, it might be an easy criterion to pass.