[EM] Cheering for simplicity/Orphan

Joe Mason jnc at notcharles.ca
Sun Aug 24 22:47:01 PDT 2003


On Fri, Aug 22, 2003 at 07:10:47PM -0400, John B. Hodges wrote:
> Some further comments. Most Condorcet-methods are "brute force" 
> computationally. The first thing they do is do all possible pairwise 
> comparisons. The multiseat method CPO-STV is likewise a "brute force" 
> method; for an N-seat race, it first enumerates all possible 
> n-candidate ensembles, then makes all possible pairwise comparisons 
> between them. (It somehow deduces from the voter's ballots ranking 
> individual candidates which of each pair of ensembles would be 
> preferred; I'm sure it also has some method of breaking ties and 
> cycles.)

I'm new here, so forgive me if I'm missing something obvious... 

The computational complexity of the methods shouldn't be an issue in a
real-world election, since the bottleneck is the entry of data rather
than the crunching of the numbers.  The computational complexity comes
into play for large data sets, on the order of thousands or tens of
thousands.  I can't see a real-world election getting above a few
hundred candidates.  As long as the computation is quadratic and not
exponential, a computer can easily handle that size.  Even an
exponential calculation is fine for elections with under a dozen or so
candidates.

(Of course, this is assuming a political election - if the election's
being used as part of a computer process, to manage resources say, the
computational complexity obviously becomes more important because the
number of candidates might be unbounded and the election might be run
many times a second instead of less than once a year.)

Joe



More information about the Election-Methods mailing list