[EM] Re: Citation for immunity to strategic voting?

[Andrew Myers]

On Sat, Sep 03, 2005 at 03:04:00PM -0700, Rob LeGrand wrote:
> Andrew Myers wrote:
> > Is there any stronger statement that can be made for strategic
> > immunity of specific completion methods, ideally ones that
> > satisfy the summability criterion?
> 
> Maybe your best bet would be to show that the general problem of
> manipulating a given election method by voting insincerely is NP-
> hard.  See
> 
> Bartholdi III, John J., Craig A. Tovey and Michael A. Trick.  The
> computational difficulty of manipulating an election.  Social
> Choice and Welfare, 6(3):227-241, 1989.

Thanks for the reference, but unfortunately NP-hardness is the wrong criterion
here. Just because there are SOME elections that are hard to manipulate (which
is what NP-hard means) doesn't mean that TYPICAL elections can't be easily
manipulated by burying.

-- Andrew