[EM] A practical matter for Ranked-Pairs, among other methods

Eric Gorr ericgorr at cox.net
Tue Jan 14 13:27:57 PST 2003


(I'll return to the odd RP case I just presented soon)

Several methods for determining the winner are based on algorithms 
which for a large enough N (where N is the number of options to be 
ranked) could take longer to compute then the amount of time the 
Universe has been in existence...that N is probably not very much 
different then the N that would take an average human lifetime to 
complete.

For example, the computation on which Ranked-Pairs or Beatpath Winner 
is based, in large part, on Floyd's Algorithm, which runs in O(N^3) 
time.

I was just wondering if anyone had researched this very real problem 
of just how large N could become before it became impractical to use 
for a particular election.


----
For more information about this list (subscribe, unsubscribe, FAQ, etc), 
please see http://www.eskimo.com/~robla/em



More information about the Election-Methods mailing list