[EM] Which Condorcet completion method is best?

[Markus Schulze]

Dear Rob,

you wrote (14 Apr 2001):
> But what about the differences among the best margins methods? The
> way I see it, Path Voting's biggest advantage over Ranked Pairs is
> its efficiency of computation, even with large numbers of candidates.
> To ensure that the best Ranked Pairs winner is chosen every time,
> an exponential-time algorithm like Steve Eppley's Minimize Thwarted
> Majorities must be used, since the straightforward Ranked Pairs
> implementation can trip up on tied pairwise victories.  Path Voting
> has an efficient algorithm of order O(n^3), where n is the number of
> candidates.  I also think that my simulations clearly show that Path
> Voting consistently picks better winners than Ranked Pairs, although
> the difference isn't vast.
>
> (I hope it's obvious that I mean no disrespect to Mike or Blake.  I've
> followed their contributions to the list for quite a while and I agree
> with them most of the time.  Credit should also go to Markus for his
> excellent beatpath idea.)

I agree with you. To my opinion, in so far as the intuitiveness of
an election method is quite subjective, in so far as whether someone
can explain a given method rather depends on his didactic experience
than on the logic of this method and in so far as it can be said
whether a given reader has "understood" a given method only when he
is able to apply it, the runtime of a given method is an objective
measure for the simplicity of this method.

The fact that the beatpath approach has a runtime O(n^3) while Ranked
Pairs has a runtime O(n^4) resp. O(n!) [depending on how situations
with defeats of equal strength are handled] and the SSD heuristics have
a runtime of O(n^5) demonstrates a big advantage of the beatpath idea.

Markus Schulze