Since you've replied to what I said, rather than what Bob said, let me
reply in turn. The paper also is neither mine nor Bob's, but James-Green
Armytage's.
Kathy Dopp wrote:
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.
Bob,
The use of simulations to "show" anything is usually looked at with
skepticism among degreed statisticians or mathematicians - perhaps
since each simulation can depend on assumptions which may not be
stated explicitly. I would think that your paper would be taken more
seriously if it did not entirely depend on simulations and used proofs
or mathematically-derived formulas instead. To disprove a hypothesis
is of course the easiest, since it merely requires citing one
counter-example.
James did not claim that he used simulations to show this. Rather, he
said that the simulations had a greater difficulty of manipulating IRV
than they had at manipulating (among others) Borda and Range. I
suggested the possible connection with that IRV is NP-hard in the
unlimited-candidate/unlimited-voter case.
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).
Again, the number of possible ranked ballots is a *huge* number as the
number of candidates increases.
[snip]
That's true, but NP-hardness observations rely on asymptotic
performance. If we show that manipulation by an individual is, say, n^2
* c where c is 100!, then it's still in P. It may still turn very
unwieldy if we set the number of candidates c to a parameter and then
show functions regarding the worst case complexity of manipulation as a
function of n and c.
In general, one starts with very restrictive limits (NP-hard with
constant number of candidates?) and relax the criteria, since if say,
it's found that some voting rule require superpolynomial time to
manipulate with any number of manipulators, then there's no point in
examining whether it does with weighted ballots (since any weighted
ballot situation can be reduced to a multiple number of unweighted
ballots); and if one finds out that some method is average case hard to
manipulate even with a constant number of candidates, there's no point
in considering the case with the number of candidates given as a parameter.
Or stated more briefly, by analogy: if we can have IIA, why try to prove
clone independence? But if we can't have IIA (and we can't), proving
clone independence helps us determine which methods are better than the
others.
----
Election-Methods mailing list - see http://electorama.com/em for list info
