Raph Frank wrote:
On Sun, Feb 1, 2009 at 6:04 PM, Kathy Dopp <[email protected]> wrote:
OK, to get references to how it is a problem of exponential difficulty
to count an STV election I am told to
Google "Bartholdi STV" and you'll come up with many citations.
I think the point here is that it is very hard to manipulate PR-STV.
To work out the optimal strategic vote is NP-hard.
"(Bartholdi and Orlin, 1991) Manipulation of STV for electing a single
winner is NP-complete."
This doesn't mean that the election is NP complete to actually count.
It means that people are less likely to be strategic (as it is almost
impossible to actually work out the strategically optimal vote).
A note regarding this: I think Warren said that the NP-completeness
proof only held when the number of candidates increases as quickly as
the number of voters. Also, NP-completeness regards the "hardest" cases
- many NP-complete problems (like 3SAT or integer programming) have
"regions" that are easy, and then phase transitions, at the other side
of which the problems are suddenly very hard.
Warren's post is here:
http://www.mail-archive.com/[email protected]/msg01590.html
----
Election-Methods mailing list - see http://electorama.com/em for list info
