[EM] corrctions to older psts re IRV public election data

Paul Kislanko kislanko at airmail.net
Sat Nov 12 11:13:59 PST 2005

Warren is quite correct about:
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

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
and I would make a stronger statement.

In any ranked ballot method the input size is #voters times #alternatives,
and any COUNTING method will necessarily be a polynomial function of that
value or a smaller value. Even iterative methods for which the number of
rounds is indeterminate are upper-bounded by the number of alternatives,
which as long as it is finite is always "small".

The NP-completeness of the "determine best strategy" derives from the fact
that as the alternatives increases, the number of possible ballots exceeds
the number of voters. So in general, it is "hard" to determine the effect of
changing votes "strategically". But that's a theoretical problem that is
completely different from the vote-counting problem.

For instance, if there are 10 alternatives there are 9,865,123 possible
ranked-ballots (allowing equal rankings and truncation). If there are fewer
voters, then pretty much for any method the task of analyzing changes in
voters ballots is essentially impossible, but the process of counting the
votes cast is something I could do on my laptop in about a second.

More information about the Election-Methods mailing list