[EM] corrctions to older psts re IRV public election data
Warren Smith
wds at math.temple.edu
Sat Nov 12 08:14:42 PST 2005
sorry, you are right that the first STV winner need not be the same as the IRV winner.
Re NP-hardness & polytime, all such results take
place in an asymptotic limit as some parameter or parameters describing
nput size tend to infinity. Say the input size is N bits; then
an algorithm is polytime if its runtime is <P(N) steps where P is a polynomial.
For the question of spotting IRV nonmonotonicty, the question of determining
your strtaegic-best IRV vote, etc, if V (#voters) is large and C (#canddts)
is fixed then the runtime is polynomial(V). However, no known method is
polynomial(V,C) and these papers give NP-hard scenarios where both V and C
are made large, e.g. V=2C and make C large, for example. I consider these
regimes to be unrealistic and the regime V=large, C=fixed to be realistic.
In the "realistic" setting, few or none of the NP-hardness results are valid and there are
easy polynomial-time algorithms. This whole area of "research" is largely a "crock."
If they were, for example, to make a semi-realisitc setting where, say,
C=log(V) and V-->infinity, and prove NP-hardness there, then I would start
to get impressed that their results had some relevance to reality.
I do not mind these results, I just mind that a lot of people get the wrong
impression that they matter, and I mind that the authors of these results
do not take care to dispel that wrong impression.
wds
More information about the Election-Methods
mailing list