[EM] 3 or more choices - Condorcet

[Kristofer Munsterhjelm]

On 10/01/2012 04:05 AM, robert bristow-johnson wrote:
> On 9/30/12 6:13 PM, Juho Laatu wrote:
>> On 30.9.2012, at 15.41, Kristofer Munsterhjelm wrote:

>>> As far as intrinsically Condorcet methods go, Ranked Pairs feels
>>> simple to me. The only tricky part is the indirect nature of the
>>> "unless it contradicts what you already affirmed" step.
>
> yeah, it's not immediately obvious to me how i would code up Ranked Pairs.
>
Easy to code is not necessarily the same thing as easy to understand. 
Schulze is rather easy to code once you know the trick (use a suitable 
adaptation of the Floyd-Warshall algorithm), but it's not very easy to 
understand without going into detail about beatpaths.

As for how to code Ranked Pairs, a simple way is to have a depth-first 
(or breadth-first) search routine that tries to go from, say, A to B 
when you want to affirm B to A. If it's possible to go from A to B, then 
you can't affirm B to A, so you skip it, otherwise you affirm B to A and 
go to the next one.
More complex structures can lower the time complexity to O(n^3), I 
think. For River, there are even more clever tricks (that I don't recall 
at the moment) to speed it up further by observing that one doesn't need 
a directional graph for the candidates already locked in.