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.
----
Election-Methods mailing list - see http://electorama.com/em for list info
