[Election-Methods] voting research

[Kristofer Munsterhjelm]

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.