[EM] Question about a criterion for ballot counting

bql at bolson.org bql at bolson.org
Tue Jun 6 15:06:48 PDT 2006

This discussion sounds like what I encountered in Computer Science under 
the topics of computability and computational complexity.

I think we can safely say that a good election method is an algorithm that 
executes in bounded time. An election method should not be an exercise in 
solving the Halting Problem.

Almost all election methods I've seen have compuational complexity linear 
in proportion to the number of voters. The Gini Welfare function recently 
discussed here is O(n^2) with the number of voters.

I wrote this up for worst-case asymptotic algorithmic complexity for 
various election methods:

It could be argued that to truly scale up, an election method must be 
linear with votes. It could also be argued that any laptop computer is 
good enough to run an election of a million votes, and a $10,000 computer 
could run a billion votes.

Anyway, that's just what I thought of. Maybe it's still not the direction 
you were trying to go.

Brian Olson

More information about the Election-Methods mailing list