[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